spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Nachdem ich mein letztes geometrisches Problem gelöst habe, folgt direkt das Nächste.

Ich möchte herausfinden, ob ein Punkt innerhalb eines Polygons liegt.
Bei ersten Recherchen fand ich auch direkt eine tolle Lösung:
Man iteriert durch alle Strecken des Polygons und prüft ob der Punkt entweder rechts oder links liegt.
Toll, hat funktioniert, nur nach weiterer Überlegung dann doch zu wenig!
Das Ganze funktioniert nur so lange, wie das Polygon konvex ist. Ist es konkav ist die Prüfung nicht zu gebrauchen.

Also habe ich weiter gesucht.
Die nächste Lösung war, einen random Punkt außerhalb des Polygons zu nehmen und diesen mit dem anderen Punkt zu einer Strecke zu verbinden.
Wenn eine ungerade Anzahl an Schnittpunkten vorliegt, ist der Punkt innerhalb, wenn gerade (oder 0) ist er außerhalb.
Allerdings konnte ich an mehreren Stellen lesen, das dies zu Ungenauigkeiten führen kann. Warum dem so ist, konnte ich nicht herausfinden.

Die 3. Lösung ist die bei weitem komplex este.
Man unterteilt das Polygon in Dreiecke und prüft ob der Punkt innerhalb eines dieser Dreiecke liegt.
Das hört sich soweit ganz gut an, nur kann sich das Ganze auch sehr schnell zu einem sehr komplexen Laufzeitverhalten entwickeln.

Ich präferiere Methode 2, allerdings würde mich interessieren, warum davon abgeraten wird? Bestimmt hatte jemand schon ähnliche Gedanken

mfg

PS: Was ist an "komplex este" falsch (natürlich zusammen geschrieben)?

Ok, klingt einleuchtend, also immer einen 2. oder 3. Test nach schieben? Oder wie kann man da ran gehen?

Zu deiner Frage:
An sich habe ich keine konkaven Polygone, aber ich biete in meiner Library die Möglichkeit welche zu nutzen. Dabei werden aber Sonderfälle wie überschlagende Polygone oder Polygone mit Löchern ausgeschlossen.