¿Cómo puedo optimizar una consulta Punto en Polígono para millones de puntos cuando la mayoría de los puntos se encuentran dentro del polígono?

8

Tengo 150 millones de puntos en una tabla de puntos y me gustaría encontrar los pocos puntos que se encuentran fuera de una geometría de polígono dada. Sé que el 99.9% de los puntos están dentro de la geometría del polígono. Estoy interesado en encontrar los pocos puntos que se encuentran fuera del polígono.

Mi mejor consulta actual usando tablas PostGIS indexadas tarda unos 30 minutos en completarse. ¿Hay alguna manera de optimizar la siguiente consulta sabiendo que la mayoría de los puntos están dentro del polígono (borde)?

SELECT COUNT(*) 
FROM italy_points pt
JOIN borders poly
ON ST_WITHIN (pt.the_geom, poly.geom)
WHERE poly.iso3 = 'ITA'; 

El polígono es básicamente la frontera administrativa de Italia. Vértices - 405,000. Partes - 510. El sobre es mucho más grande que el polígono (el polígono cubre el 24% del sobre)

Prithvi
fuente
2
Por favor Editar la pregunta para dar una indicación de la complejidad del polígono - ¿Cuántas partes? Cuantos vértices Qué porcentaje de la envoltura del polígono está dentro del polígono. Descubrí que particionar polígonos complejos puede mejorar la evaluación de polígonos de punto en , pero debe manejar la condición en la que un solo punto intersecta más de una partición.
Vince
La primera optimización para este tipo de operación es comúnmente verificar si el punto está en el cuadro delimitador del polígono antes de continuar con la operación completa de punto en el polígono. Point-in-box es una operación muy eficiente en comparación.
WhiteboxDev
@Vince Si hay duplicados posibles (creo que el único caso en el que pienso es cuando cae exactamente en el borde de dos particiones), esto se maneja trivialmente en PostGIS. Solo necesita GROUP BYla clave principal de los puntos. (PostgreSQL convenientemente le permite hacer referencia a cualquier columna de la SELECTcláusula que provenga de una tabla donde se incluye la clave primaria en la GROUP BYcláusula).
jpmc26
@WhiteboxDev ST_Withinya hace una verificación de cuadro de límite que permite usar el índice. (Casi todas las funciones de PostGIS incluyen esta optimización.) Si aún es lenta, entonces claramente el problema es con la complejidad del polígono.
jpmc26
@ jpmc26 Ciertamente, pero la consulta SQL también debería modificarse para su uso ST_Intersects, ya ST_Withinque no coincidiría de manera confiable con las condiciones de contorno internas.
Vince

Respuestas:

10

Use ST_Subdivide para cortar su polígono en polígonos más pequeños, guárdelos en una tabla y cree un índice espacial. Luego haga su consulta sobre los polígonos cuadriculados.

Sin eso, la indexación espacial no proporciona ninguna ventaja en su caso (solo 1 polígono de interés).

Colina baja
fuente
44
Además del comentario ST_Subdivide (), puede encontrar que el uso de un número de vértices menor que el predeterminado produce mayores ganancias al aumentar el apalancamiento del índice y disminuir el tiempo de recuperación de la geometría. Trate de 64 o incluso 32.
Paul Ramsey
¡La consulta ahora se completa en 5 minutos en lugar de 30! Gracias por la sugerencia.
Prithvi
Wow, este fue un grito increíblemente bueno. Mi consulta estaba bloqueando una máquina con 62 Gb de RAM en menos de 2 minutos y luego este ST_Subdivide hizo que no solo no se bloqueara sino que se ejecutara en segundos. ¡Acabo de encontrar a mi nuevo mejor amigo!
Momchill