Punkt im Polygonalgorithmus für mehrere Polygone

Ich habe eine Google-Karte mit einer Reihe von Polygonen.

Hier ist ein Problem, das mich interessiert: Wie kann man bei einem Lat-Lng-Punkt am besten alle Polygone bestimmen, in denen dieser Punkt liegt?

Der naheliegende Weg besteht darin, für jedes Polygon iterativ einen "Punkt im Polygon" -Algorithmus auszuführen, aber ich habe mich gefragt, ob es einen effizienten Algorithmus gibt, um solche Fragen zu beantworten, insbesondere wenn Sie Tausende von Polygonen haben.

Wie bei fast allen derartigen Fragen hängt der optimale Ansatz von den "Anwendungsfällen" und der Darstellung der Funktionen ab. Die Anwendungsfälle unterscheiden sich typischerweise durch (a) ob sich in jeder Schicht viele oder wenige Objekte befinden und (b) ob eine (oder beide) Schichten die Vorberechnung einiger Datenstrukturen ermöglichen; das heißt, ob einer oder beide ausreichend statisch und unveränderlich sind, um die Investition in die Vorberechnung lohnenswert zu machen.

Im vorliegenden Fall ergeben sich folgende Szenarien. Normalerweise sind die Punkte dynamisch, dh sie werden nicht vorher vergeben. (Wenn sie im Voraus oder in sehr großen Gruppen verfügbar sind, sind einige Optimierungen verfügbar, die auf ihrer Sortierung basieren.) Q sei die Anzahl der Abfragepunkte und P die Anzahl der Polygonscheitelpunkte .

Vektorpolygondaten

(1) einige Punkte, wenig Polygon - Scheitel in toto . Verwenden Sie ein Brute-Force-Verfahren wie den klassischen Linienstich-Algorithmus . Für jede anständige Methode betragen die Kosten O (P * Q), da der Vergleich eines Punktes mit einer Polygonkante O (1) Zeit kostet und alle derartigen Vergleiche durchgeführt werden müssen.

(2) Möglicherweise viele Polygonscheitelpunkte, aber sie sind dynamisch: Jedes Mal, wenn ein Punkt in der Abfrage verwendet wird, haben sich möglicherweise alle Polygone geändert. Verwenden Sie erneut einen Brute-Force-Algorithmus. Die Kosten sind immer noch O (P * Q), was groß sein wird, weil P groß sein wird, aber das hilft nichts. Wenn die Änderungen klein oder kontrolliert sind ( z. B. wenn sich die Form der Polygone geringfügig ändert oder sich nur langsam bewegt), können Sie möglicherweise eine Version der nächsten Lösung verwenden und einen effizienten Weg finden, um die Datenstrukturen zu aktualisieren, wenn sich die Polygone ändern. Das wäre wahrscheinlich eine Frage der ursprünglichen Forschung.

(3) Viele Polygonscheitelpunkte und statische Polygone ( dh die Polygonebene ändert sich selten). Berechnen Sie eine Datenstruktur vor, um die Suche zu unterstützen (die auf einem Zeilenumbruch oder einem Quadtree- Algorithmus basieren kann). Die Kosten für die Vorberechnung für diese Algorithmen betragen O (P * log (P)), aber die Kosten für die Abfragen werden zu O (Q * log (P)), sodass die Gesamtkosten O ((P + Q) * log () sind. P)).

In besonderen Fällen sind einige Verbesserungen verfügbar , z

(a) Alle Polygone sind konvex (die Vorverarbeitung der Polygone kann schneller erfolgen ),

(b) Alle Polygon-Innenräume sind disjunkt . In diesem Fall können Sie sich ihre Vereinigung als ein einzelnes Polygon vorstellen (was einfache, effiziente Algorithmen ermöglicht, z. B. solche, die auf Triangulation basieren, und

(c) Die meisten Polygone sind nicht sehr gewunden - das heißt, sie nehmen große Teile ihrer Begrenzungsrahmen ein. In diesem Fall können Sie einen ersten Test nur auf der Grundlage der Begrenzungsrahmen durchführen und diese Lösung dann verfeinern. Dies ist eine beliebte Optimierung.

(d) Die Anzahl der Punkte ist groß. Das Sortieren kann das Timing verbessern. Wenn Sie beispielsweise einen Punkt-in-Polygon-Algorithmus für den Linien-Sweep von links nach rechts implementieren, sortieren Sie die Punkte nach ihrer ersten Koordinate, sodass Sie die Punkte gleichzeitig mit dem Sweep über die Polygonkanten streichen können. Mir ist nicht bekannt, dass eine solche Optimierung veröffentlicht wurde. Eine Veröffentlichung wurde jedoch durchgeführt, um eine eingeschränkte Triangulation der Vereinigung aller Punkte und Polygonscheitelpunkte durchzuführen : Sobald diese Triangulation abgeschlossen ist, sollte die Identifizierung der inneren Punkte schnell erfolgen. Die Berechnungskosten werden als O (Q * log (Q) + (P + Q) * log (P + Q)) skaliert.

Rasterpolygondaten

Dies ist unglaublich einfach: Zeigen Sie die Polygonebene als Raster für binäre Indikatoren an (1 = innerhalb eines Polygons, 0 = außerhalb). (Dies könnte eine Nachschlagetabelle erfordern, um Rasterwerte in Innen- / Außenindikatoren umzuwandeln.) Jede Punktsonde erfordert jetzt O (1) Aufwand, um die Rasterzelle zu indizieren und ihren Wert zu lesen. Der Gesamtaufwand beträgt O (Q).

Allgemein

Eine schöne HybridlösungIm Fall vieler statischer Vektorpolygone (Vektorfall 3 oben) werden die Polygone zunächst gerastert, möglicherweise sogar mit einer groben Auflösung, wobei diesmal alle Zellen unterschieden werden, die einen Teil einer Polygongrenze schneiden (geben Sie ihnen beispielsweise den Wert 2). . Die Verwendung einer Rastersonde (Kosten: O (1)) führt normalerweise zu einer eindeutigen Antwort (der Punkt befindet sich bekanntermaßen innerhalb oder außerhalb), führt jedoch gelegentlich zu einer unbestimmten Antwort (der Punkt fällt in eine Zelle, durch die mindestens eine Kante fällt bestanden), in welchem ​​Fall die teurere O (log (P)) - Vektorabfrage durchgeführt wird. Diese Methode verursacht einige zusätzliche Speicherkosten für das Raster, aber in vielen Fällen kann selbst ein kleines Raster (ein MB ermöglicht ein Raster von 2000 x 2000, in dem {0,1,2, null} -Werte gespeichert sind) enorme Vorteile in der Rechenzeit bringen . Asymptotisch,

Wenn Sie die Polygon-Begrenzungsrahmen in einem Quad-Baum gespeichert hätten, könnten Sie damit schnell bestimmen, welche Polygone überprüft werden sollen. Zumindest konnte man sehen, ob sich der Punkt innerhalb jedes Polygonbegrenzungsrahmens befindet, anstatt für jedes Polygon einen vollständigen Punkt im Polygon zu erstellen. Persönlich würde ich einen Webdienst einrichten, der die Polygone im Speicher zwischenspeichert und so etwas wie JTS oder NetTopology Suite verwendet, um die Schnittpunktabfrage für mich durchzuführen.

In postgis ermittelt ST_Intersects anhand von Indizes zunächst, ob sich der Punkt innerhalb des Begrenzungsrahmens des Polygons befindet, und überprüft dann erneut, ob er sich tatsächlich innerhalb des Polygons befindet. Das ist schnell, oft sehr schnell.

Wenn Sie Ihre Daten in PostGIS gespeichert haben, sollte kein Zweifel daran bestehen, dass die Datenbank der richtige Ort für die Berechnung ist. In anderen Fällen müssen Sie Ihre Polygone an ein mittleres oder Client-Programm senden. Das an sich wird viel mehr Zeit in Anspruch nehmen als die Berechnungen durchzuführen und nur die relevanten Polygone zu erhalten.

/ Nicklas