Wie bestimmen verschiedene GIS-Systeme das Innere eines Polygons?

11

Ich bin daran interessiert zu verstehen, wie reale GIS-Systeme und ihre Daten Polygone codieren.

Wie lösen sie insbesondere die Mehrdeutigkeit des Inneren eines Polygons auf einer Kugel auf?

Hintergrund: In 2D ist es trivial, die Seite der Grenze auszuwählen, die eine endliche Fläche hat, da die 2D-Ebene unendlich ist. Eine Kugel ist jedoch endlich, so dass es unmöglich ist zu wissen, welche Seite sich im Inneren befindet, ohne zusätzliche Annahmen zu treffen.

Mögliche Ansätze, die ich kenne:

  1. Rechte Regel : Außengrenzen werden immer im Uhrzeigersinn und Löcher gegen den Uhrzeigersinn angegeben. (Es gibt natürlich auch die Regel für die linke Hand).
  2. Kleinster Bereich : Wählen Sie für einen bestimmten Ring immer die Seite mit dem kleinsten Bereich aus. Ich bin mir nicht sicher, wie Sie ein Polygon mit großer Reichweite angeben würden: Vielleicht einen leeren Außenring, gefolgt von Löchern?
  3. Gleichwinklig : Betrachten Sie einfach die gleichwinklige Projektion auf einer unendlichen 2D-Ebene. Dies setzt jedoch voraus, dass Merkmale am Antemeridian zerhackt werden, andernfalls wäre ein Fallback auf eine der beiden oben genannten Methoden erforderlich.

Meine persönliche Präferenz ist der erste Ansatz, aber ich bin daran interessiert zu verstehen, ob dies in Standard-GIS-Systemen üblich ist.

Jason Davies
quelle

Antworten:

3

Wichtige GIS-Systeme und ihre Methoden zur Lösung der inhärenten Mehrdeutigkeit:

  • ESRI : Rechtsfußregel.
  • ArcGIS : Rechtsfußregel.
  • SQL Server 2012 : Regel für den linken Fuß. Vor SQL Server 2012 haben Polygone, die größer als die Hemisphäre sind, einen Fehler ausgelöst.

GeoJSON gibt keine Bestellung an.

Jason Davies
quelle
1
Die überarbeitete GeoJSON-Spezifikation ( tools.ietf.org/html/rfc7946 ) gibt an, dass " Polygonringe zur Orientierung der rechten Regel folgen müssen ( Außenringe gegen den Uhrzeigersinn, Innenringe im Uhrzeigersinn)."
Perrygeo
1

Wenn ich Ihre Frage richtig verstehe, möchten Sie wissen, wie GIS einen Punkt im sphärischen Polygontest ausführt. Hier ist ein Algorithmus, den ich bei geospatialmethods.org gefunden habe :

  1. Verbinden Sie den Punkt mit einem großen Kreisbogen mit dem bekannten externen Punkt.
  2. Für jeden Großkreisbogen, der eine Seite des sphärischen Polygontests ist, wenn er den in Schritt 1 konstruierten Bogen schneidet und die Anzahl der Schnittpunkte zählt.
  3. Wenn die Gesamtzahl der Schnittpunkte ungerade ist, befindet sich der angegebene Punkt innerhalb des sphärischen Polygons. Wenn die Gesamtzahl der Schnittpunkte gerade ist, liegt der Punkt außerhalb des sphärischen Polygons.

Ich denke, es basiert immer noch auf dem planaren Algorithmus, einen Teststrahl vom fraglichen Punkt bis zu einem Punkt außerhalb des Polygons zu konstruieren, gefolgt von der Zählung, wie viele Kanten der Strahl kreuzt, die Sie erwähnt haben.

Es wird auch in einem JPL-Artikel der NASA über Algorithmen für Polygone auf einer Kugel ausführlich erörtert . Es ist auf Seite 11. Es gibt natürlich einige Optimierungen:

Vermeiden Sie es nach Möglichkeit, die rechenintensiven Berechnungen der sphärischen Trigonometrie durchzuführen, indem Sie den Teststrahl gegen einen vorberechneten Begrenzungsrahmen prüfen, bevor Sie sich die Kanten des Polygons ansehen. Wenn der Teststrahl den Begrenzungsrahmen schneidet, wird Q gegen jeden der Eckpunkte des Polygons geprüft. Es macht keinen Sinn zu testen, ob sich Q zu diesem Zeitpunkt an einer Kante befindet, da dies angezeigt wird, wenn die Schnittpunkttests durchgeführt werden und der Rest der Kanten zu diesem Zeitpunkt übersprungen werden kann.

Ich denke, Sie werden das Papier am interessantesten finden :)

RK
quelle
Dies scheint eine andere Frage zu beantworten. Eine nicht sich selbst schneidende, geschlossene Polylinie unterteilt eine Kugel in zwei verbundene Komponenten. Das OP fragt, wie das GIS bestimmt - oder wie es gesagt wird - welche dieser Komponenten als "innen" und welche "außen" zu betrachten sind. Auf der von Ihnen zitierten Website wird dieses Problem unter der Überschrift "Externen Punkt erraten " behandelt, wobei betont wird, dass lediglich erraten wird, welche Komponente darin enthalten sein soll.
whuber
Oh ... Trottel. Seine Frage falsch verstanden. Ich habe es mit der sphärischen Version des Punktes im Polygontest zusammengeführt. Ich werde es überarbeiten, sobald ich eine Antwort finde.
RK
Nun, ich habe die Referenzen, die Sie gefunden haben, sehr geschätzt und hoffe, dass Sie es schaffen, sie in Ihre überarbeitete Antwort aufzunehmen :-).
whuber
Ich hoffe es auch. Oder vielleicht stelle ich einfach eine Frage und beantworte sie selbst ;-) Es wäre eine Schande, sie zu verschwenden.
RK
1
Danke für die ausführliche Antwort! Leider beantwortet dies, wie @whuber betont, meine spezifische Frage nicht. :) Ich habe mögliche Ansätze skizziert, um die inhärente Unklarheit zu lösen, wo sich das Innere eines Polygons befindet, aber ich bin daran interessiert zu wissen, welche Ansätze reale GIS-Software verfolgt.
Jason Davies