Prüfung Punkt in Polygon

Um ein Polygon zu finden, das der Benutzer mit der Maus auf dem Bildschirm angeklickt hat, um es dann z.B. zu füllen, benötigt man die Prüfung auf einen Punkt im Polygon.

Eine einfache geschlossene Kurve teilt die 2D-Ebene in genau zwei durch die Kurve verbundene Gebiete, das beschränkte Innere und ein unbeschränktes Äußeres (Jordanscher Kurvensatz). Darum bedeutet eine Kreuzung mit der Kurve einen Wechsel von einem Gebiet in das andere.

Ein Punkt liegt daher dann im Inneren des Polygons, wenn ein von ihm in eine beliebige Richtung ausgehender Strahl ungeradzahlig viele Polygonkanten kreuzt. Diese Gerade-Ungerade-Test hat eine Ausnahme: Wird ein Knoten geschnitten, zählt dieser doppelt, da das Polygon betreten und gleich wieder verlassen wird!

Mathematisch aufwändiger ist die Windungszahl-Methode: Hier werden die gerichteten Kanten gezählt und eine Richtungszahl von 1 oder -1 addiert. Ist das Ergebnis ungleich 0 liegt der Punkt im Polygon.