Algoritmos espaciales

Algoritmo "punto en polígono"

Los cruces espaciales entre capas geográficas es una operación que está presente en todos los SIG. Para llevarlo a cabo, uno de los procesos más comunes es el denominado "point-in-polygon" (Preparata and Shamos, 1991), que consiste en determinar si un punto en el espacio esta contenido, intersecta o esta fuera de un polígono dado. Para resolver este problema existen diversas aproximaciones expresados en forma de algoritmos (Huang and Shih, 1997). Estos algoritmos abordan distintos aspectos, sin embargo, los orientados a trabajar en forma vectorial suelen ser los que más tiempo de cálculo necesitan cuando las capas geográficas están constituidas por centenas de miles de elementos. Esta circunstancia hace que no resulte fácil llevar a cabo estos cruces espaciales en computadores personales.

Pese a lo anterior, aprovechando las capacidades de los computadores actuales, se ha desarrollado una variante del método propuesto por Nordbeck (1967), implementada en el lenguaje de programación C. Este método utiliza como aproximación el raster y presenta un compromiso entre tiempo de cálculo, eficacia y validez de resultados. El método nos permite procesar archivos muy grandes, de millones de elementos, en segundos, haciendo viable el análisis constante del área de estudio, en nuestro caso, el DMQ. El limitante actual, en realidad, está relacionado con la cantidad de memoria RAM disponible en el computador en el que opere, dado que la aproximación utilizada carga toda la información en este recurso. Estas técnicas ya fueron inicialmente probadas por el grupo de trabajo en el GAD de Portoviejo tras el terremoto del 16 de Abril de 2016 (Marrero et al., 2019), especialmente centradas en mejorar la geolocalización de los datos relacionados con el impacto causado en edificaciones.

La incertidumbre del algoritmo está generada por la conversión al pasar de vector a raster, o sea, cómo un polígono vectorial puede ser dibujado a nivel de mosaicos (Imagen 1). Hace años, las capacidades de los computadores obligaba a trabajar con resoluciones bajas, lo que generaba un gran nivel de incertidumbre debido a que los límites poligonales quedaban representados muy groseros, en forma de sierra, a la hora de convertirlos en una malla o cuadrícula. La Imagen 1 muestra claramente como se incrementa la precisión en el dibujo a medida que aumentamos la resolución del raster (para un mismo espacio lo dividimos en un mayor número de celdas de tamaño más reducido). Cuanto peor es la resolución, más probabilidades hay que muchos puntos situados en el límite poligonal queden definidos fuera del mismo.

En líneas generales, el algoritmo implementado opera siguiendo estas fases:

1. Considera si el punto está en el raster o no.

2. Evalúa en que celda del raster esta situado el punto

3. Determina si esa celda pertenece a un polígono o no.

4. Si está en zona límite, busca una posible relocalización, solo para casos específicos que requieren un mayor detalle.

5. Transfiere la cuenta numérica o bien el valor del punto al polígono en determinados modos de análisis.

6. Transfiere los atributos del polígono al punto en determinados modos de análisis.

Los tiempos necesarios para realizar estas operaciones están en función del numero de elementos vectoriales que se desean analizar, no es lo mismo una capa que contenga unas pocas decenas que otra que implique algunos millones. De la misma forma, el tamaño de los archivos, tanto de datos vectoriales como de raster, implica unos requerimientos mínimos computacionales, como es la disponibilidad de memoria RAM.

Algoritmo por proximidad

Este algoritmo se aplica cuando solo intervienen datos de tipo vectorial. En este caso la aproximación es sencilla, para cada punto de una capa calculamos todos aquellos de la otra que están situados a una distancia de búsqueda establecida o bien considerando solo al que se encuentre mas próximo. Para ello recurrimos a la fórmula que nos permite calcular dicha distancia lineal:

Distancia = sqrt ( ( x1 - x2 )² + ( y1 - y2 )²) 

Donde x1 e y1 son las coordenadas del punto 1, x2 e y2 las del punto 2 y sqrt la raíz cuadrada del resultado. Lo más importante a considerar en este caso es que usamos distancia lineal en 2D, por lo que radios de búsquedas grandes pueden no tener sentido en el contexto real de una ciudad: dos puntos pueden estar relativamente próximos en distancia pero totalmente desconectados desde el punto de vista del entramado viario o por obstáculos naturales. Importante indicar que se opera siempre en metros.

Para los casos donde ambas capas tienen muchos elementos, podemos reducir el tiempo de cálculo poniendo la variable CON_EXIT a 1, en cuyo caso, en el momento que encontremos un acierto, terminaremos el bucle de cálculo.

Bibliografía

Huang, C.W. and Shih, T.Y., 1997. On the complexity of point-in-polygon algorithms. Computers & geosciences, 23(1), pp.109 – 118. Available from: https://doi.org/10.1016/S0098-3004(96)00071-4.

Marrero, JM., Yepes, H., Pastor, J., Palacios, P.B., Erazo, C., Ramón, P. and Estrella, C., 2019. Integrating and geolocating post earthquake building damage surveys: The 7.8 mw jama-pedernales earthquake, ecuador. Spatial information research. Available from: https://doi.org/10.1007/s41324-018-0230-y. 

Nordbeck, S. and  Rystedt, B. 1967. Computer cartography point-in-polygon programs. BIT Numerical Mathematics , Vol. 7, p. 39-64. Available from: https://doi.org/10.1007/BF01934125. 

Preparata, F. and Shamos, M., 1991. Computational geometry: An introduction. Springer.