Bei dieser Methode wird gezählt, wie oft die Begrenzungskurve den Punkt
ganz umläuft. D.h. die Umlaufszahl (oder Winding Number)
liegt in
für Punkte, die im Polygon liegen und ist
für Punkte, die nicht im Polygon liegen.
Für jede Polygonkante von nach
bildet man die Vektoren von
nach
und von
nach
und berechnet den Winkel
zwischen diesen beiden Vektoren. Die Umlaufszahl ergibt sich
dann zu:
Diese Methode ist jedoch mathematisch aufwändig. Es reicht, wenn der
Algorithmus zählt, wie oft die Begrenzungskurve an einem bestimmten Punkt
vorbeikommt. Es wird also wieder ein Strahl von waagerecht nach rechts
geschossen und wieder wird die Zahl der Kanten ermittelt, die diesen Strahl
schneiden. Allerdings wird jetzt die Richtung der Kante berüecksichtigt.
Wenn die Kante von unten nach oben läuft, wird die Umlaufszahl um 1
erhöht. Wenn die Kante hingegen von oben nach unten läuft, wird die
Umlaufszahl um 1 erniedrigt.
Dadurch erhalten Punkte außerhalb des Polygons die Umlaufszahl 0 und
innere Punkte eine Umlaufszahl ungleich 0.
public boolean contains(int x, int y) { int wn = 0; int x1 = xpoints[npoints-1]; int y1 = ypoints[npoints-1]; int x2 = xpoints[0]; int y2 = ypoints[0]; boolean startUeber = y1 >= y? true : false; for(int i = 1; i<npoints ; i++) { boolean endUeber = y2 >= y? true : false; if(startUeber != endUeber) { if((y2 - y)*(x2 - x1) <= (y2 - y1)*(x2 - x)) { if(endUeber) { wn ++; } } else { if(!endUeber) { wn --; } } } startUeber = endUeber; y1 = y2; x1 = x2; x2 = xpoints[i]; y2 = ypoints[i]; } return wn == 0; } |