Alternative Indizierungsmethoden für Punktmengenoperationen

17

Es ist üblich, einen räumlichen Bounding-Box-Index zu verwenden, um die Leistung bei der Arbeit mit einer großen Anzahl von Features zu verbessern. Gibt es bei Operationen an einzelnen Geometrien mit einer großen Anzahl von Eckpunkten ähnliche Optimierungsstrategien?

Gibt es zum Beispiel Datenstrukturen, die Punkte in Polygonen oder Vereinigungsoperationen beschleunigen können?

algorithm optimization indexing Matthew Snape
quelle
1
Unter der Haube verwenden GIS viele spezialisierte Datenstrukturen, einschließlich verschiedener Formen von Quadtrees, DCELs usw., die in Lehrbüchern zur Computergeometrie beschrieben werden. Fragen Sie nach diesen Implementierungsdetails oder nach Methoden, die von Benutzern in Skriptsprachen verwendet werden könnten?
Whuber
Danke, ich denke ich muss die Lehrbücher lesen. Der Punkt meiner Frage war, wie diese Datenstrukturen vorab berechnet werden können. Gibt es vorberechnete Implementierungen?
Matthew Snape
Matthew, das ist eine großartige Frage. Ein wirklich leistungsorientiertes GIS bietet Benutzern die Möglichkeit, Datenstrukturen für wiederholte Anwendungen vorab zu berechnen. Derzeit bietet die Software-Werbung selbst als "GIS" in der Regel eine solche Vorberechnung nur in Form von "räumlichen Indizes", wohingegen allgemeinere Software, die auch GIS-Analysen durchführen kann, wie Mathematica (oder in gewissem Umfang R), dem Benutzer dies bietet viel mehr Kontrolle über solche Dinge.
Whuber
Ich denke, das Problem beruht auf der "fraktalen Natur" von 2D-Objekten und der unsicheren und unausgeglichenen Verteilungsinformationsdichte.
Huckfinn

Antworten:

2

OK nur für Punkt im Polygon:

Ich denke, das Problem beruht auf der "fraktalen Natur" von 2D-Objekten und der unsicheren und unausgewogenen Verteilung von räumlichen Informationen. Wenn Sie ein reguläres Gitter haben, ist es einfach, eine Position oder Beziehung einer Zelle zu berechnen. Aber eine Isolinie eines Geländemodells kann unkomplizierte Teile auf der einen Seite und mathematisch komplizierte Teile auf der anderen Seite haben (morphologisch aktive Teile wie Grate, Täler ...).

Die Indizierung versucht, zwei Dinge zu handhaben:

  1. Eine schnelle Routine, die Ihnen einen Satz von Eimern gibt, in dem Sie Objekte sammeln, die Sie räumlich unterscheiden können (die Eimer!). Und BBoxen sind einfach zu berechnen und zu handhaben.

  2. Eine Reihe von Beziehungen (Überlappung, Berührung), um das räumliche Material (die Objekte) zu unterscheiden oder in Beziehung zu setzen.

Leider geben BBoxes keinen Hinweis darauf, wie viele Punkte in jeder BBox enthalten sind, wie die Objekte geformt sind (Löcher, konvex, ...) und wie die Informationen lokal verteilt sind (90% der Punkte in der oberen linken Ecke der BBox) BBox). So finden Sie möglicherweise schnelle Operationsmitglieder auf Objektebene und verlieren viel Zeit im Beziehungsaufbau des Tests.

Um einen unregelmäßigeren Ansatz zu verwenden, gehört die IMO-Triangulation in Kombination mit und Quadtrees zu den Strategien, bei denen Sie den Teil des Bucketing und den Teil des Beziehungsaufbaus eines Index näher zusammenrücken können (Bucketing == Beziehungsaufbau).

Für das Beispiel Point-in-Polygon-Test können Sie einen unregelmäßigen Cache erstellen, indem Sie Folgendes verwenden:

  1. Eingeschränkte Delaunay-Triangulation Ihrer Polyhülle mit zusätzlichen Randmaschenpunkten für die Erkennung außerhalb der Hülle
  2. Setzen Sie dies in ein Quadtree-Indexierungsschema mit nicht mehr als N Dreiecken pro Kästchen (fraktale Eimer).
  3. Finden Sie die Dreiecksmenge, zu der der Punkt gehört - das Blatt im Quadtree
  4. finde das Dreieck, in dem der Punkt liegt (der Prüfling über max. N Dreiecken)
  5. und fragen Sie nach den Polygon-IDs der Eckpunkte des Dreiecks
  6. Wenn die ID eindeutig ist, gehört der Punkt zum Polygon, wenn nicht, liegt er außerhalb

Die Kosten für den Bau der Dose und der Quadtrees sind sehr hoch und schwer zu berechnen, und der Quadtree muss große und kleine Dreiecke ausgleichen (Dreiecke, die nicht in kleinere Subtree-Boxen passen).

Einige Tools und Links:

Dreieck - Beschränkungspolygon-Triangulation

Quadtrees - Mit Quellbeispielen

Stony Brook Repository - Datenstrukturen und diskrete Geometrie

huckfinn
quelle