Das PIP-Problem (Punkt-in-Polygon) ist das Problem, zu bestimmen, ob ein Punkt ein beliebiges Polygon ist. Dies mag für ein einfaches Polygon wie ein Quadrat oder ein Dreieck trivial klingen, wird jedoch mit komplexeren Polygonen wie dem im folgenden Beispiel komplexer. In diesem Beitrag wird der gerade-ungerade Algorithmus, auch Kreuzungsnummernalgorithmus oder Jordan-Algorithmus genannt (da er mit dem Jordan-Kurvensatz bewiesen werden kann) eingeführt.

Beschreibung des Algorithmus

Das Grundprinzip hinter dem Even-Odd aka. Jordan aka. Der Kreuzzahlalgorithmus besteht darin, zu zählen, wie oft eine Linie vom betreffenden Punkt (in einer beliebigen Richtung) eine Kante des Polygons kreuzt. Diese Linie befindet sich immer außerhalb des Polygons an ihrem “Ende” im Unendlichen. Wenn sie sich also am Anfang (dem fraglichen Punkt) innerhalb des Polygons befindet, muss sie das Polygon irgendwann verlassen und eine Kante überqueren. Es kann das Polygon erneut eingeben (siehe Beispiel unten), muss jedoch immer wieder verlassen werden, wodurch die Gesamtzahl der Kreuzungen ungerade wird, wenn sich der Punkt im Polygon befindet. Das Gegenteil ist auch wahr; Wenn die Anzahl der Kreuzungen gerade ist, liegt der Punkt immer außerhalb des Polygons. Dies ist der oben erwähnte Jordan-Kurvensatz.

Der Algorithmus überprüft jede Kante des Polygons in einer Schleife, um festzustellen, ob die Linie vom Punkt bis zur Unendlichkeit diese kreuzt. Im folgenden Beispiel wird diese Linie vom Punkt bis unendlich nach rechts gezeichnet, kann jedoch eine beliebige Richtung haben.

Die Schritte sind:

1. Für jede Kante im Polygon:
2. Wenn die Kante die imaginäre Linie vom Punkt bis unendlich kreuzt, erhöhen Sie einen Zähler.
3. Wenn der Zähler am Ende ungleichmäßig ist, geben Sie true zurück. Andernfalls geben Sie false zurück.

Eine einfache boolesche Variable, die jedes Mal invertiert wird, wenn eine Kreuzung gefunden wird, ist ebenfalls möglich.

Beispiel des Algorithmus

Betrachten Sie das folgende Polygon mit 8 Kanten und zwei Punkten, für die wir bestimmen möchten, ob sie sich im Polygon befinden:

Die Schritte, die der Algorithmus für dieses Polygon ausführt, um zu bestimmen, ob sich der erste (grüne) Punkt im Polygon befindet, beginnen an der ersten Kante:

1. Grüner Punkt kreuzt Kante 8
2. Der grüne Punkt kreuzt nicht die Kante 1
3. Grüner Punkt kreuzt Kante 2
4. Der grüne Punkt kreuzt nicht die Kante 3
5. Grüner Punkt kreuzt Kante 4
6. Grüner Punkt kreuzt Kante 5
7. Grüner Punkt kreuzt nicht die Kante 6
8. Der grüne Punkt kreuzt nicht die Kante 7
9. Gesamtzahl der Überfahrten: 4
10. Gerade Anzahl von Kantenübergängen, daher befindet sich der Punkt nicht im Polygon

Die Schritte, die der Algorithmus für dieses Polygon ausführt, um zu bestimmen, ob sich der zweite (rote) Punkt im Polygon befindet, beginnen an der ersten Kante:

1. Der rote Punkt kreuzt nicht die Kante 8
2. Der rote Punkt kreuzt nicht die Kante 1
3. Der rote Punkt kreuzt nicht die Kante 2
4. Der rote Punkt kreuzt nicht die Kante 3
5. Roter Punkt kreuzt nicht die Kante 4
6. Roter Punkt kreuzt Kante 5
7. Der rote Punkt kreuzt nicht die Kante 6
8. Der rote Punkt kreuzt nicht die Kante 7
9. Gesamtzahl der Überfahrten: 1
10. Ungleichmäßige Anzahl von Kantenübergängen, daher befindet sich der Punkt im Polygon

Laufzeitkomplexität des Algorithmus

Die Laufzeitkomplexität des Jordan-Algorithmus aka. Crossing Number Algorithmus aka. Der geradzahlige Algorithmus zur Lösung des Punkt-in-Polygon-Problems für einen einzelnen Punkt ist in Bezug auf die Anzahl der Kanten linear. Dies wird deutlich, wenn man sich den Code ansieht, der eine einzelne Schleife über den Kanten enthält, ohne Rekursion oder weitere Funktionsaufrufe oder Schleifen.

Formal ist die Laufzeit *O(| V |), | V |: = Anzahl der Kanten im Polygon *.

Speicherkomplexität des Algorithmus

Die Speicherkomplexität ist auch linear w.r.t. die Anzahl der Kanten, da zusätzlich zum Polygon nur Variablen mit fester Größe gespeichert werden müssen. Darüber hinaus kann der Algorithmus online implementiert werden, sodass keine vergangenen Kanten während der Schleife betrachtet werden müssen, sodass sie aus dem Speicher entfernt werden können (oder vergleichbare Maßnahmen zur Leistungsverbesserung).