Tengo un fichero CSV de 1.000 millones de puntos y un shapefile con unos 5.000 polígonos. ¿Cuál sería la forma más rápida de unir espacialmente puntos y polígonos? Para cada punto, necesito obtener el id del polígono que lo contiene. (Los polígonos no se solapan.)
Normalmente, cargaría ambos conjuntos de datos en PostGIS. ¿Hay alguna manera más rápida de hacer el trabajo?
Busco una solución de código abierto.
Si "más rápido" incluye la cantidad de su tiempo que se emplea, la solución dependerá del software con el que se sienta cómodo y pueda utilizar de forma expeditiva. En consecuencia, las siguientes observaciones se centran en ideas para conseguir lo más rápido posible informática veces.
Si utilizas un programa enlatado, casi seguro que lo mejor que puedes hacer es preprocesar los polígonos para configurar una estructura de datos punto-en-polígono, como un árbol K-D o un quadtree, cuyo rendimiento será típicamente O(log(V)*(N+V)) donde V es el número total de vértices en los polígonos y N es el número de puntos, porque la estructura de datos tomará al menos O(log(V)*V) esfuerzo para crear y luego tendrá que ser sondeada para cada punto a un coste por punto O(log(V)).
Se puede hacer mucho mejor cuadriculando primero los polígonos, aprovechando la suposición de que no hay solapamientos. Cada celda de la cuadrícula se encuentra completamente en el interior de un polígono (incluido el interior del "polígono universal"), en cuyo caso se etiqueta la celda con el id del polígono, o bien contiene uno o más bordes de polígono. El coste de esta rasterización, igual al número de celdas de la cuadrícula referenciadas mientras se rasterizan todos los bordes, es O(V/c) donde c es el tamaño de una celda, pero la constante implícita en la notación big-O es pequeña.
(Una de las ventajas de este método es que permite utilizar rutinas gráficas estándar. Por ejemplo, si tienes un sistema que (a) dibujará los polígonos en una pantalla virtual utilizando (b) un color distinto para cada polígono y (c) te permite leer el color de cualquier píxel al que quieras dirigirte, lo tienes hecho).
Con esta rejilla en su lugar, pre-selecciona los puntos calculando la celda que contiene cada punto (una operación O(1) que requiere sólo unos pocos relojes). A menos que los puntos estén agrupados en torno a los límites del polígono, sólo quedarán unos O(c) puntos con resultados ambiguos. El coste total de la construcción de la malla y la preselección es, por tanto, O(V/c + 1/c^2) + O(N). Para procesar los puntos restantes (es decir, los que están cerca de los límites de los polígonos) hay que utilizar algún otro método (como cualquiera de los recomendados hasta ahora), con un coste de O(log(V) * N * c).
A medida que c se hace más pequeño, cada vez menos puntos estarán en la misma celda de la cuadrícula con un borde y, por tanto, cada vez menos requerirán el subsiguiente procesamiento O(log(V)). En contra está la necesidad de almacenar O(1/c^2) celdas de cuadrícula y de emplear O(V/c + 1/c^2) de tiempo en rasterizar los polígonos. Por lo tanto, habrá un tamaño de cuadrícula óptimo c. Utilizándolo, el coste computacional total es O(log(V) * N), pero la constante implícita suele ser camino menor que utilizando los procedimientos enlatados, debido a la velocidad O(N) de la preselección.
Hace 20 años probé este método (utilizando puntos espaciados uniformemente por toda Inglaterra y en alta mar y explotando una cuadrícula relativamente rudimentaria de unas 400.000 celdas que ofrecían los búferes de vídeo de la época) y obtuve dos órdenes de magnitud de aceleración en comparación con el mejor algoritmo publicado que pude encontrar. Incluso cuando los polígonos son pequeños y sencillos (como los triángulos), está prácticamente garantizado un aumento de la velocidad de un orden de magnitud.
En mi experiencia, el cálculo era tan rápido que toda la operación estaba limitada por las velocidades de E/S de los datos, no por la CPU. Anticipando que la E/S podría ser el cuello de botella, conseguirías los resultados más rápidos almacenando los puntos en un formato lo más comprimido posible para minimizar los tiempos de lectura de los datos. Piense también en cómo almacenar los resultados para limitar las escrituras en disco.
Por mi parte, probablemente cargaría los datos CSV en un shp y luego escribir un script python utilizando archivo shape y bien formado para obtener el id del polígono contenedor y actualizar el valor del campo.
No sé si geotools y JTS es más rápido que shapefile/shapely ... ¡No tengo tiempo para probarlo!
editar : Por cierto, la conversión de csv a formato shapefile probablemente no sea necesaria, ya que los valores podrían ser fácilmente formateados para ser probados con objetos espaciales de su shapefile de polígonos.
Acabé convirtiendo los polígonos en una trama y muestreándola en las posiciones de los puntos. Como mis polígonos no se solapaban y no era necesaria una gran precisión (los polígonos representaban clases de uso del suelo y, de todos modos, sus límites se consideraban bastante inciertos), esta fue la solución más eficiente en términos de tiempo que se me ocurrió.
Escribiría rápidamente un pequeño programa java basado en el lector de shapefiles de geotools y la operación contiene de STC . No sé lo rápido que puede ser...
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
