Sichtbarkeitsdiagramm auf Kugel berechnen

9

Ich habe eine PostGIS-Tabelle mit einigen Polygonen (gespeichert unter Verwendung des Geografiedatentyps). Sie repräsentieren Regionen auf einer kugelförmigen Erde.

Für jedes Scheitelpunktpaar, das aus allen Polygonen ausgewählt wurde, möchte ich berechnen, ob diese beiden Scheitelpunkte für einander "sichtbar" sind. (Es gibt n * ( n -1) / 2 solcher Paare, wobei n die Gesamtzahl der eindeutigen Eckpunkte über alle Polygone in der Tabelle ist.) Mit "für einander sichtbar" meine ich, dass der Großkreispfad zwischen dem Zwei Eckpunkte schneiden keines der Polygone in der Tabelle.

Was ist der schnellste Weg, um diese Berechnung durchzuführen, vorzugsweise in PostgreSQL / PostGIS?

Ich habe etwas, das funktioniert, aber es ist langsam. Ich iteriere nur naiv über alle Paare und sehe, ob der LineString zwischen ihnen Polygone schneidet. (Der Geografiedatentyp von PostGIS erledigt für mich die ganze harte Mathematik auf der Kugel.) Ich frage mich also, ob es eine clevere Datenstruktur oder einen cleveren Algorithmus gibt, der die Dinge beschleunigen könnte.

postgis postgresql spherical-geometry csd
quelle
6
Relevante Konzepte: Sichtbarkeitsdiagramme und, wenn Sie diese Arbeit in 2D anstelle von 3D ausführen möchten, die gnomonische Projektion .
whuber
Bedeutet "über alle Paare iterieren", dass Sie eine FOR-Schleife in der Prozedur haben, die prüft, ob eine Linie alle Polygone schneidet?. Wenn ja, ist es (wahrscheinlich) schneller, erstellen Sie einfach eine Linestring-Tabelle mit allen möglichen Kombinationen und führen Sie eine Abfrage durch, bei der Sie testen, ob die Linie die Polygontabelle schneidet
Simplexio
Könnten Sie eine Illustration des Problems teilen.
Addcolor
Sie können alles jenseits des sphärischen Horizonts ausschließen (plus Bit für große Objekte in der Nähe des Randes), was mit einem ungefähren Koordinatenbegrenzungsrahmen schnell erledigt werden kann. Ansonsten denke ich, dass es grundsätzlich NP schwer ist.
AnserGIS

Antworten:

1

Leiten Sie ab, was nicht sichtbar ist. Angenommen, Sie stehen an einem Scheitelpunkt am Strand und betrachten zwei entfernte Scheitelpunkte eines benachbarten Polygons. Dann können Sie davon ausgehen, dass jeder Scheitelpunkt im gesamten Sektor hinter diesen Scheitelpunkten von diesem Scheitelpunkt aus unsichtbar ist.

Peter
quelle