imported>SigmaB: Anzahl angepasst

2024-11-23T17:06:01Z

Anzahl angepasst

Neue Seite

Der '''Punkt-in-Polygon-Test nach Jordan''' prüft, ob ein bestimmter [[Punkt (Geometrie)|Punkt]] in der [[Ebene (Mathematik)|Ebene]] innerhalb, außerhalb oder an der Grenze eines [[Polygon|Polygons]] liegt.

Nach dem [[Jordanscher Kurvensatz|Jordanschen Kurvensatz]] teilen, vereinfacht gesagt, die Ränder eines [[Polygon|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 ==
[[Datei:RecursiveEvenPolygon.svg|mini|Die Anzahl der [[Schnittpunkt|Schnittpunkte]] für einen [[Strahl (Geometrie)|Strahl]], der von der Außenseite des [[Polygon|Polygons]] bis zu einem beliebigen [[Punkt (Geometrie)|Punkt]] verläuft.]]
Bei der Strahl-Methode wird von dem zu testenden [[Punkt (Geometrie)|Punkt]] ein [[Strahl (Geometrie)|Strahl]] in eine beliebige Richtung versendet. Dabei wird gezählt, wie oft der Strahl die Kanten des [[Polygon|Polygons]] schneidet. Es können drei Fälle unterschieden werden:
# eine gerade Anzahl von [[Schnittpunkt]]en
# eine ungerade Anzahl von Schnittpunkten
# 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 [[Kollinearität|kollinearen]] Fall kann jedoch auf solch eine Wiederholung mit einem anderen Winkel verzichtet werden.

== Pseudocode ==
Der folgende [[Pseudocode]]<ref>vgl.
{{Literatur |Autor=Jeff Erickson |Titel=The Jordan Polygon Theorem |Sammelwerk=Computational Topology |WerkErg=Vorlesungsskript |Datum=2009 |Kommentar=S. 3 – dort fehlt der Fall eines Testpunkts auf einer horizontalen Kante |Online=[http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/jordan-polygon-theorem.pdf online] |Format=PDF |KBytes=144 |Abruf=2018-02-13}}</ref> zählt die [[Schnittpunkt|Schnittpunkte]] entlang dem horizontal nach rechts gerichteten [[Strahl (Geometrie)|Strahl]] mit besonderer Beachtung der auf dem Strahl liegenden [[Ecke|Ecken]]:

<syntaxhighlight lang="cpp">
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, ..., n−1
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, 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: 0
</syntaxhighlight>

'''Hinweis''': Gemäß der Beschreibung des Rückgabewertes der [[Funktion (Programmierung)|Funktion]] KreuzProdTest wird bei Delta > 0 der Wert <math>-1</math> zurückgegeben. Wenn stattdessen das [[Vorzeichen (Zahl)|Vorzeichen]] von Delta zurückgegeben wird, liefert die Funktion PunktInPolygon auch das korrekte Ergebnis. In diesem Fall werden die [[Schnittpunkt|Schnittpunkte]] der Kanten mit einem von <math>A</math> nach links verlaufenden Strahl gezählt.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung des [[Algorithmus]]. Die Punkte und die [[konvexe Hülle]] werden auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere [[Klasse (Objektorientierung)|Klassen]]. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die das Ergebnis auf der Konsole ausgibt.<ref>Stack Exchange Inc: [https://stackoverflow.com/questions/4243042/c-sharp-point-in-polygon C# Point in polygon]</ref><ref>GeeksforGeeks: [https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/ How to check if a given point lies inside or outside a polygon?]</ref>
<syntaxhighlight lang="c#">
using System;
using System.Drawing;

// Diese Methode gibt true zurück, wenn der Punkt innerhalb des Polygons liegt, sonst false
private 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 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;
}
}
}
return isInside;
}

// Hauptmethode, die das Programm ausführt
public static void Main(String[] args)
{
int x1 = 0, y1 = 0, x2 = 100, y2 = 100; // Setzt die Koordinaten der Eckpunkte der quadratischen Fläche
Random random = new Random(); // Initialisiert den Zufallsgenerator
int numberOfVertices = 10;
Point[] polygon = new Point[numberOfVertices]; // Deklariert ein Array für die Ecken des Polygons
for (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äche
Point 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 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();
}
</syntaxhighlight>

== Anwendungsgebiete ==
Diese Methode findet vor allem in [[Geoinformationssystem|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.

== Einzelnachweise ==
<references />

[[Kategorie:Geoinformatik]]
[[Kategorie:Geoinformationssystem]]
[[Kategorie:Algorithmische Geometrie]]

Punkt-in-Polygon-Test nach Jordan - Versionsgeschichte

imported>SigmaB: Anzahl angepasst