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 )
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.
quelle
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
quelle
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
quelle