Wie kann ich eine Punkt-in-Polygon-Abfrage für Millionen von Punkten optimieren, wenn die meisten Punkte innerhalb des Polygons liegen?

8

Ich habe 150 Millionen Punkte in einer Punktetabelle und möchte die wenigen Punkte finden, die außerhalb einer bestimmten Polygongeometrie liegen. Ich weiß, dass 99,9% der Punkte innerhalb der Polygongeometrie liegen. Ich bin daran interessiert, die wenigen Punkte zu finden, die außerhalb des Polygons liegen.

Meine derzeit beste Abfrage mit indizierten PostGIS-Tabellen dauert etwa 30 Minuten. Gibt es eine Möglichkeit, die folgende Abfrage zu optimieren, wenn Sie wissen, dass sich die meisten Punkte innerhalb des Polygons (Rahmens) befinden?

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

Das Polygon ist im Grunde die Admin 0-Grenze Italiens. Eckpunkte - 405.000. Teile - 510. Der Umschlag ist viel größer als das Polygon (das Polygon bedeckt 24% des Umschlags)

postgis postgresql Prithvi
quelle
2
Bitte bearbeiten Sie die Frage, um einen Hinweis auf die Komplexität des Polygons zu geben - Wie viele Teile? Wie viele Eckpunkte? Wie viel Prozent der Hüllkurve des Polygons befindet sich innerhalb des Polygons? Ich habe festgestellt, dass das Partitionieren komplexer Polygone die Punkt-in-Polygon-Bewertung verbessern kann , aber Sie müssen die Bedingung behandeln, dass ein einzelner Punkt mehr als eine Partition schneidet.
Vince
Die erste Optimierung für diese Art von Operation besteht üblicherweise darin, zu überprüfen, ob sich der Punkt im Begrenzungsrahmen des Polygons befindet, bevor mit der vollständigen Punkt-in-Polygon-Operation fortgefahren wird. Point-in-Box ist im Vergleich dazu eine sehr effiziente Operation.
WhiteboxDev
@Vince Wenn Duplikate möglich sind (der einzige Fall, an den ich denke, ist, wenn er genau an die Grenze zweier Partitionen fällt ), wird dies in PostGIS trivial behandelt. Sie benötigen nur GROUP BYden Primärschlüssel der Punkte. (Mit PostgreSQL können Sie bequem auf alle Spalten in der SELECTKlausel verweisen , die aus einer Tabelle stammen, in der der Primärschlüssel in der GROUP BYKlausel enthalten ist.)
jpmc26
@WhiteboxDev führt ST_Withinbereits ein Grenzfeld-Check durch, mit dem der Index verwendet werden kann. (Fast alle Funktionen von PostGIS beinhalten diese Optimierung.) Wenn sie immer noch langsam ist, liegt das Problem eindeutig in der Komplexität des Polygons.
jpmc26
@ jpmc26 Sicher, aber die SQL-Abfrage müsste auch geändert werden, um verwendet zu werden ST_Intersects, da ST_Withinsie nicht zuverlässig mit internen Randbedingungen übereinstimmt.
Vince

Antworten:

10

Verwenden Sie ST_Subdivide , um Ihr Polygon in kleinere Polygone zu schneiden, diese in einer Tabelle zu speichern und einen räumlichen Index zu erstellen. Stellen Sie dann Ihre Abfrage für die gerasterten Polygone.

Ohne dies bietet die räumliche Indizierung in Ihrem Fall keine Vorteile (nur 1 Polygon von Interesse).

Mesa
quelle
4
Neben dem Kommentar ST_Subdivide () können Sie feststellen, dass die Verwendung von weniger als der Standardanzahl von Scheitelpunkten weitere Gewinne bringt, indem die Hebelwirkung des Index erhöht und die Wiederherstellungszeit der Geometrie verkürzt wird. Versuchen Sie 64 oder sogar 32.
Paul Ramsey
Die Abfrage ist jetzt in 5 Minuten abgeschlossen, anstatt in 30! Danke für den Vorschlag.
Prithvi
Wow, das war ein wahnsinnig guter Schrei. Meine Abfrage stürzte einen Computer mit 62 GB RAM in weniger als 2 Minuten ab, und dann ließ dieser ST_Subdivide ihn nicht nur nicht abstürzen, sondern in Sekunden ausführen. Habe gerade meinen neuen besten Freund gefunden!
Momchill