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 ]
Die Anzahl der Schnittpunkte für einen Strahl, der von der Außenseite des Polygons bis zu einem beliebigen Punkt verläuft.

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 drei Fälle unterschieden werden:

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

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.

Der folgende Pseudocode [1] zählt die Schnittpunkte entlang dem horizontal nach rechts gerichteten Strahl mit besonderer Beachtung der auf dem Strahl liegenden Ecken: 

Funktion:PunktInPolygon
Parameter:EckenP[1],...,P[n]einesebenenPolygonsP,TestpunktQ
Rückgabe:+1,wennQinnerhalbPliegt;
−1,wennQaußerhalbPliegt;
0,wennQaufPliegt
SetzeP[0]=P[n]undt=−1
Füri=0,...,n−1
Setzet=t*KreuzProdTest(Q,P[i],P[i+1])
Wennt=0
AbbruchderSchleife
Ergebnis:t
Funktion:KreuzProdTest
Parameter:PunkteA=(x_A,y_A),B=(x_B,y_B),C=(x_C,y_C)
Rückgabe:−1,wennderStrahlvonAnachrechtsdieKante[BC]schneidet(außerimunterenEndpunkt);
0,wennAauf[BC]liegt;
sonst+1
Wenny_A=y_B=y_C
Wennx_B≤x_A≤x_Coderx_C≤x_A≤x_B
Ergebnis:0
sonst
Ergebnis:+1
Wenny_A=y_Bundx_A=x_B
Ergebnis:0
Wenny_B>y_C
VertauscheBundC
Wenny_A≤y_Bodery_A>y_C
Ergebnis:+1
SetzeDelta=(x_B−x_A)*(y_C−y_A)−(y_B−y_A)*(x_C−x_A)
WennDelta>0
Ergebnis:−1
sonstwennDelta<0
Ergebnis:+1
sonst
Ergebnis:0

Hinweis: Gemäß der Beschreibung des Rückgabewertes der Funktion KreuzProdTest wird bei Delta > 0 der Wert − 1 {\displaystyle -1} {\displaystyle -1} 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 A {\displaystyle A} {\displaystyle A} nach links verlaufenden Strahl gezählt.

Programmierung

[Bearbeiten | Quelltext bearbeiten ]

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Algorithmus. Die Punkte und die konvexe Hülle werden auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere Klassen. Bei der Ausführung des Programms wird die Methode Main verwendet, die das Ergebnis auf der Konsole ausgibt.[2] [3] 

usingSystem;
usingSystem.Drawing;
// Diese Methode gibt true zurück, wenn der Punkt innerhalb des Polygons liegt, sonst false
privatestaticboolIsInside(Point[]polygon,Pointpoint)
{
boolisInside=false;
for(inti=0;i<polygon.Length;i++)// Diese for-Schleife durchläuft alle Ecken des Polygons
{
intj=(i+1)%polygon.Length;// Index der nächsten Ecke
if(polygon[i].Y<point.Y&&polygon[j].Y>=point.Y||polygon[j].Y<point.Y&&polygon[i].Y>=point.Y)
{
if((point.Y-polygon[i].Y)*(polygon[j].X-polygon[i].X)<(point.X-polygon[i].X)*(polygon[j].Y-polygon[i].Y))// Wenn der Strahl die Kante schneidet, Rückgabewert zwischen true und false wechseln
{
isInside=!isInside;
}
}
}
returnisInside;
}
// Hauptmethode, die das Programm ausführt
publicstaticvoidMain(String[]args)
{
intx1=0,y1=0,x2=100,y2=100;// Setzt die Koordinaten der Eckpunkte der quadratischen Fläche
Randomrandom=newRandom();// Initialisiert den Zufallsgenerator
intnumberOfVertices=10;
Point[]polygon=newPoint[numberOfVertices];// Deklariert ein Array für die Ecken des Polygons
for(inti=0;i<numberOfVertices;i++)// Diese for-Schleife erzeugt 10 zufällige Ecken innerhalb der quadratischen Fläche
{
Pointpoint=newPoint();
point.X=(int)(random.NextDouble()*(x2-x1)+x1);
point.Y=(int)(random.NextDouble()*(y2-y1)+y1);
polygon[i]=point;// Fügt die Ecke dem Polygon hinzu
}
// Erzeugt einen zufälligen Punkt innerhalb der quadratischen Fläche
PointrandomPoint=newPoint();
randomPoint.X=(int)(random.NextDouble()*(x2-x1)+x1);
randomPoint.Y=(int)(random.NextDouble()*(y2-y1)+y1);
stringtext="Liegt der Punkt ("+randomPoint.X+", "+randomPoint.Y+") innerhalb des Polygons mit den Ecken ";
for(inti=0;i<numberOfVertices-1;i++)
{
text+="("+polygon[i].X+", "+polygon[i].Y+"), ";
}
text+="("+polygon[numberOfVertices-1].X+", "+polygon[numberOfVertices-1].Y+") ?";
Console.WriteLine(text);// Ausgabe der Koordinaten auf der Konsole
if(IsInside(polygon,randomPoint))// Aufruf der Methode
{
Console.WriteLine("Ja");// Ausgabe auf der Konsole
}
else
{
Console.WriteLine("Nein");// Ausgabe auf der Konsole
}

Console.ReadLine();
}

Anwendungsgebiete

[Bearbeiten | Quelltext bearbeiten ]

Diese Methode findet vor allem in Geoinformationssystemen Anwendung.

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). 
  2. ↑ Stack Exchange Inc: C# Point in polygon
  3. ↑ GeeksforGeeks: How to check if a given point lies inside or outside a polygon?
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Punkt-in-Polygon-Test_nach_Jordan&oldid=250615967"