Punkt-in-Polygon-Test nach Jordan
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
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:
- keinen Schnittpunkt
- eine gerade Anzahl von Schnittpunkten
- eine ungerade Anzahl von Schnittpunkten
- 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.
Pseudocode
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: PunktInPolygonParameter: Ecken P[1], ...,P[n] eines ebenen Polygons P, Testpunkt QRü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, ..., n−1 Setze t = t * KreuzProdTest(Q,P[i],P[i+1]) Wenn t = 0 Abbruch der Schleife Ergebnis: tFunktion: KreuzProdTestParameter: Punkte A = (x_A,y_A), B = (x_B,y_B), C = (x_C,y_C)Rückgabe: −1, wenn der Strahl von A nach rechts die Kante [BC] schneidet (außer im unteren Endpunkt); 0, wenn A auf [BC] liegt; sonst +1 Wenn y_A = y_B = y_C Wenn x_B ≤ x_A ≤ x_C oder x_C ≤ x_A ≤ x_B Ergebnis: 0 sonst Ergebnis: +1 Wenn y_A = y_B und x_A = x_B Ergebnis: 0 Wenn y_B > y_C Vertausche B und C Wenn y_A ≤ y_B oder y_A > y_C Ergebnis: +1 Setze Delta = (x_B−x_A) * (y_C−y_A) − (y_B−y_A) * (x_C−x_A) Wenn Delta > 0 Ergebnis: −1 sonst wenn Delta < 0 Ergebnis: +1 sonst Ergebnis: 0Hinweis: Gemäß der Beschreibung des Rückgabewertes der Funktion KreuzProdTest wird bei Delta > 0 der Wert 
Programmierung
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]
using System;using System.Drawing;// Diese Methode gibt true zurück, wenn der Punkt innerhalb des Polygons liegt, sonst falseprivate static bool IsInside(Point[] polygon, Point point){bool isInside = false;for (int i = 0; i < polygon.Length; i++) // Diese for-Schleife durchläuft alle Ecken des Polygons{int j = (i + 1) % polygon.Length; // Index der nächsten Eckeif (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;}}}return isInside;}// Hauptmethode, die das Programm ausführtpublic static void Main(String[] args){int x1 = 0, y1 = 0, x2 = 100, y2 = 100; // Setzt die Koordinaten der Eckpunkte der quadratischen FlächeRandom random = new Random(); // Initialisiert den Zufallsgeneratorint numberOfVertices = 10;Point[] polygon = new Point[numberOfVertices]; // Deklariert ein Array für die Ecken des Polygonsfor (int i = 0; i < numberOfVertices; i++) // Diese for-Schleife erzeugt 10 zufällige Ecken innerhalb der quadratischen Fläche{Point point = new Point();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ächePoint randomPoint = new Point();randomPoint.X = (int)(random.NextDouble() * (x2 - x1) + x1);randomPoint.Y = (int)(random.NextDouble() * (y2 - y1) + y1);string text = "Liegt der Punkt (" + randomPoint.X + ", " + randomPoint.Y + ") innerhalb des Polygons mit den Ecken ";for (int i = 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 Konsoleif (IsInside(polygon, randomPoint)) // Aufruf der Methode{Console.WriteLine("Ja"); // Ausgabe auf der Konsole}else{Console.WriteLine("Nein"); // Ausgabe auf der Konsole}Console.ReadLine();}Anwendungsgebiete
Diese Methode findet vor allem in Geoinformationssystemen Anwendung.
Literatur
- Günter Hake, Dietmar Grünreich, Liqiu Meng: Kartographie de Gruyter, 2001, ISBN 3-11-016404-3, S. 306ff.
- Norbert Bartelme: Geoinformatik: Modelle, Strukturen, Funktionen. 2005, ISBN 3-540-20254-4, S. 103.
