Punkt-in-Polygon-Test nach Jordan

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Punkt-in-Polygon-Test nach Jordan prüft, ob ein bestimmter Punkt in der Ebene innerhalb, außerhalb oder an der Grenze eines Polygons liegt.

Nach dem Jordanschen Kurvensatz teilen, vereinfacht gesagt, die Ränder eines Polygons den Datenraum in eine Innen- und eine Außenseite. Für viele Anwendungen ist es nötig, herauszufinden, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt.

Strahl-Methode[Bearbeiten | Quelltext bearbeiten]

Beispiel des Tests

Bei der Strahl-Methode wird von dem zu testenden Punkt ein Strahl in eine beliebige Richtung versendet. Dabei wird gezählt, wie oft der Strahl die Kanten des Polygons schneidet. Es können vier Fälle unterschieden werden:

  1. keinen Schnittpunkt
  2. eine gerade Anzahl von Schnittpunkten
  3. eine ungerade Anzahl von Schnittpunkten
  4. unendlich viele Schnittpunkte

Ist die Anzahl Null, liegt der Punkt außerhalb des Polygons. Ist die Anzahl ungerade, liegt der Punkt innerhalb des Polygons, ist sie gerade, liegt er außerhalb. Im Fall von unendlich vielen Schnittpunkten verlief der Strahl direkt auf einer Kante. Der Test muss dann mit einem anderen Winkel wiederholt werden. Durch eine verfeinerte Betrachtung der relativen Lage des Testpunktes und der Kantenenden im kollinearen Fall kann jedoch auf solch eine Wiederholung mit einem anderen Winkel verzichtet werden. So zählt der folgende Pseudocode[1] entlang dem horizontal nach rechts gerichteten Strahl mit besonderer Beachtung von auf dem Strahl liegenden Ecken:

Funktion:  PunktInPolygon
Parameter: Ecken P[1], ...,P[n] eines ebenen Polygons P, Testpunkt Q
Rückgabe:  +1, wenn Q innerhalb P liegt;
           1, wenn Q außerhalb P liegt;
           0, wenn Q auf P liegt
  Setze P[0] = P[n] und t = 1
  Für i = 0, ..., n1
    Setze t = t * KreuzProdTest(Q,P[i],P[i+1])
    Wenn t = 0
      Abbruch der Schleife
  Ergebnis: t

Funktion:  KreuzProdTest
Parameter: Punkte A = (x_A,y_A), B = (x_B,y_B), C = (x_C,y_C)
Rückgabe:  1, nicht im Polygon;
           0, Punkt auf Kante liegt;
           sonst +1
  Wenn y_B > y_C
    Vertausche B und C
  Wenn y_A  y_B oder y_A > y_C
    Ergebnis: +1
  Setze Delta = (x_Bx_A) * (y_Cy_A)  (y_By_A) * (x_Cx_A)  
  Wenn Delta > 0
    Ergebnis: 1
  sonst wenn Delta < 0
    Ergebnis: -1
  sonst
    Ergebnis: 0

Hinweis: Gemäß der Beschreibung des Rückgabewertes der Funktion KreuzProdTest wird bei Delta > 0 der Wert zurückgegeben. Wenn stattdessen das Vorzeichen von Delta zurückgegeben wird, liefert die Funktion PunktInPolygon auch das korrekte Ergebnis. In diesem Fall werden die Schnittpunkte der Kanten mit einem von nach links verlaufenden Strahl gezählt.

Anwendungsgebiete[Bearbeiten | Quelltext bearbeiten]

Diese Methode findet vor allem in Geoinformationssystemen Anwendung.

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. vgl. Jeff Erickson: The Jordan Polygon Theorem. In: Computational Topology. Vorlesungsskript. 2009 (online (PDF; 144 kB) [abgerufen am 13. Februar 2018] S. 3 – dort fehlt der Fall eines Testpunkts auf einer horizontalen Kante).