2D Frage: Punkt in Polygon?

[------------]

Hi,

nehmen wir mal an ich habe einen Punkt an der Position 45x54 und ein Polygon mit 4 Ecken: 88x0, 33x55, 90x2, 103x46 und möchte nun wissen ob der Punkt im Polygon liegt.

Wie berechne ich das in 2D?

[otze]

das polygon in dreiecke aufteilen, und dann über die funktionen der seiten testen ob der punkt zwischen den seiten liegt

[Gunnar.]

Algemein: Ziehe eine gedachte Linie von deinem Punkt A zu einem Punkt B, der garantiert nicht im Polygon liegt. Zaehle die dabei geschnittenen Kanten des Polygons. Ist das Ergebnis ungerade <=> Punkt A liegt im Polygon.

[Sunday]

siehe hier für ausführliche informationen und zu möglichen problemen beim angedeuteten algorithmus.

http://www-lehre.inf.uos.de/~cg/2004/skript/node32.html
http://rw7.de/ralf/inffaq/polygon.html

[Valerij_7]

Hallo!

Ich habe drei Algorithmen ausprobiert und 2 davon haben Probleme.
Deswegen habe ich gesucht und gefunden, was wirklich funktioniert:

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Ich habe winding - Algorithmus verwendet, und bin sehr damit zufrieden.

Wenn jemand bool als result haben will, kann das einsetzen:

if (wn%2 == 0)
	{
		return false;
	}
	else
	{
		return true;
	}

Viel Spaß
Valerij