Mit OGR durch Linien gekreuzte Polygone finden?

8

Ich versuche, alle Polygone zu finden, die von einer einzelnen Linie (einer GPS-Spur) gekreuzt werden. Ich verwende die OGR-Bibliothek (von Python), um dies zu berechnen, aber es ist derzeit ein bisschen "Brute-Force" (und langsam). Für jeden Punkt meiner Spur rufe ich die Schnittmethode mit allen Polygonen auf. Die offensichtliche Optimierung besteht darin, nur mit benachbarten Polygonen zu prüfen. Aber ich denke, dies ist ein klassisches Problem mit einer bereits bekannten Lösung (die ich nicht finden kann ...).

Ich möchte die Verwendung einer dedizierten Datenbank vermeiden, da ich versuche, eine eigenständige Software zu schreiben (Spatialite ist eine Option, wenn die Datenbank der richtige Weg ist).

(Zu Ihrer Information, der aktuelle Quellcode ist hier verfügbar: https://github.com/dkm/airspace-checker )

Marc
quelle

Antworten:

7

Eine Python-Lösung finden Sie unter Shapely http://gispython.org/shapely/docs/1.2/ und RTree http://pypi.python.org/pypi/Rtree/.

Mit Rtree können Sie räumliche Indizes erstellen.

DavidF
quelle
Ich habe schon formschön gesehen, wusste aber nichts über rtree! Vielen Dank!
Marc
Ok, ich konnte rtree (endlich) testen. Es funktioniert gut, da ich den Testsatz von 1096 auf 19 reduzieren kann :). Ich denke darüber nach, Shapely zu verwenden, aber ich muss am besten verstehen, was es bedeutet (Shapely verarbeitet keine Projektionen, ich möchte dabei nichts verlieren).
Marc
5

Anstelle eines expansiven Schnittpunkts können Sie eine Vorauswahl von Polygonen basierend auf dem Vergleich von Begrenzungsrahmen durchführen. Mit anderen Worten, finden Sie alle Polygone, die sich überlappen / an den MBR von Segmenten Ihrer Spur angrenzen. Führen Sie dann einen detaillierten Test für die Teilmenge der Polygone durch.

Mloskot
quelle
3

Die Vorschläge von Mloskot und Nicklas zum Vergleich der Begrenzungsrahmen sind in der Tat richtig.

Wenn Sie Shapefiles verwenden, können Sie auch dieses Saga-Modul aufrufen: http://www.saga-gis.org/saga_modules_doc/shapes_transect/index.html

johanvdw
quelle
Ich denke, ich werde Lösungen mit BBoxes überprüfen. Meine Daten sind nicht zufällig: Tracks sind Paraglider / Hangglider-Flüge und die Polygone sind die Lufträume. Ich werde nachsehen, ob ich einen einfachen Filter für die bbox finden kann. Ich verwende Shapefiles nicht direkt, aber ich habe ein Skript geschrieben, das das OpenAIR-Format ("Standard" -Luftraumdeskriptoren) in OGR liest (von dem ich direkt nach shp exportieren kann)
Marc
2

Um dies zu beschleunigen, führt eine Datenbank wie PostGIS zunächst einen Index- und Begrenzungsrahmenvergleich durch. Zunächst werden alle Polygone gefunden, deren Begrenzungsrahmen sich mit dem Begrenzungsrahmen der Linie überschneiden. Das Problem in Ihrem Fall könnte sein, dass der Linienstreifen lang ist und einen sehr großen Begrenzungsrahmen aufweist, der viele Polygone schneidet, was nicht von Interesse ist.

Wenn die Linien sehr lang sind, müssen Sie wahrscheinlich auch mit geodätischen Funktionen arbeiten, die viel komplexer und langsamer sind als planare Funktionen.

Es kann ziemlich komplex sein, einen reibungslosen Ablauf zu gewährleisten.

Warum möchten Sie sich nicht auf eine Datenbank verlassen? Das wird nicht alle Ihre Probleme lösen, aber es gibt zum Beispiel viele eingebaute Optimierungen in PostGIS. Dort haben Sie auch die geodätischen Schnittberechnungen, wenn Sie diese benötigen.

Update: Ich habe Ihre Frage erneut gelesen und festgestellt, dass Sie nicht den Linestring der Trac-Formulare verwenden, sondern jeden Scheitelpunkt.

Ich denke, Sie befinden sich auf der falschen Spur;)
Sowohl, weil Sie nicht prüfen können, ob die Kante zwischen den Scheitelpunkten das Polygon schneidet, als auch weil Sie die Iteration zwischen den Scheitelpunkten nach Python verschieben, anstatt nach einer C-Implementierung, die meiner Meinung nach viel schneller ist . Dann haben Sie dieses Problem mit Indizes. Um die Dinge schneller zu machen, müssen Sie eine Art räumlichen Index erstellen und verarbeiten.

Auf der anderen Seite, wenn Sie so viel Arbeit in Ihrem eigenen Code erledigen, warum machen Sie nicht auch den Kreuzungstest? Dieser Test ist nur ein Punkt im Polygontest, wenn Sie sich mit den Scheitelpunkten befassen. Google für "Punkt im Polygon" und Sie finden mehrere Algorithmen.

Aber ich würde mich für einen datenbankgesteuerten Ansatz entscheiden. Dadurch haben Sie die Möglichkeit, räumliche Indizes zu verwenden.

/ Nicklas

Nicklas Avén
quelle
Ich dachte das Gleiche auf der Linie. Ich bin mit GIS und Python nicht so vertraut, aber es sollte eine Möglichkeit geben, räumliche Indizes im Speicher zu erstellen (ich weiß, dass es verschiedene .net-Optionen dafür gibt). Dies könnte eine weitere gute Frage für gis.se sein.
Jay Cummins
Danke für die Antwort. Ich verwende keine DB für die einfache Einrichtung. Aber wenn das Vermeiden von DB zu viel Codekomplexität impliziert, werde ich meine Meinung ändern :). Was die "räumlichen Indizes" betrifft, muss ich ein bisschen googeln, um genau zu verstehen, was es ist.
Marc
Was "Ich habe Ihre Frage noch einmal gelesen und festgestellt, dass Sie nicht den Linestring der Trac-Formulare verwenden, sondern jeden Scheitelpunkt." Ich denke, ich könnte auch die Schnittmenge aus dem Linestring-Objekt testen, aber dann muss ich den Schnittpunkt extrahieren. Aber das kann schneller gehen, Sie haben absolut Recht!
Marc
Über räumliche Indizes sollten Sie Google Gist und mehrdimensionale Indizes googeln. Die Idee ist, einen mehrdimensionalen Index der Begrenzungsrahmen zu erstellen. In db-evironment entscheidet der Planer dann, ob es sich lohnt, zuerst den Index zu durchsuchen, um die sich überschneidenden Begrenzungsrahmen zu finden, bevor der eigentliche Schnittpunkttest durchgeführt wird.
Nicklas Avén