Punkt in Polygon-Fläche?

[WL]

Hallo Jaecko,
schau mal hier..............
http://www.dbs.ifi.lmu.de/Lehre/GIS/SS2009/Skript/Kap-06.pdf

[Jaecko]

Moin.

So, hatte in letzter Zeit leider nicht die Zeit hier was zu machen. Jetzt gehts wieder weiter.
Also das mit der Vektorgeometrie erscheint mir doch etwas aufwändiger als mein bisheriger Stand. V.a.: Wie viele dieser Teildreiecke hätte z.B. ein Polygon mit 10 Eckpunkten? Bzw. wie unterteil ich dann das Polygon am geschicktesten?

Edit: Oder wird nicht das Polygon selbst in Dreiecke unterteilt sondern mit Hilfe des zu prüfenden Punktes? Wie in Lösung 2 in der PDF?

Das mit dem in der PDF beschriebenen Vorgang mach ich ja quasi schon, nur dass mein "Strahl" so liegt, dass er durch den zu prüfenden Punkt und einen Punkt geht, der sicher ausserhalb des Polygons liegt.

Einige Sonderfälle hab ich schon durch, allerdings bleibt noch einer, der doch etwas kniffliger ist. Nämlich genau der auf S. 159 (in der PDF S, 14/38), die unteren rechten beiden Abbildungen.
(Im Beitrag hier nochmal als Grafik angehängt)
Wenn die "Referenzlinie" nun durch einen Eckpunkt geht: Wie krieg ich raus, ob ich danach noch innerhalb oder ausserhalb des Polygons bin?

mfG

Nachtrag: Die Lösung 2 scheint nach was brauchbarem auszusehen. Nur Winkelfunktionen auf nem µC dürften reine Zeit/Speicherfresser sein.

[Jaecko]

So, endlich "fertig": http://wiki.cihome.de/index.php?titl..._(Algorithmus)
Im Prinzip läufts nun ohne Referenzpunkt und -Linie ab; ähnlich (oder eigentlich genau so), wie in der PDF als Lösung 2 angegeben. Hauptproblem war hierbei aber ständig die Berechnung des Winkels und auch dessen Drehrichtung (Über das Skalarprodukt z.B.... oder ich habs ständig falsch berechnet...)
Durch einen Tip, atan2() zu verwenden, kommt man nun zum Winkel mit Vorzeichen. Damit lässt sich das Problem dann einfach mit der Winkelsumme od. Windungszahl lösen.

Falls man das atan2(y, x) noch gegen was "effizienteres" (= schnelleres) austauschen kann, wärs natürlich noch besser.

mfG

[oberallgeier]

... Falls man ... atan2(y, x) ... gegen was ... schnelleres ... wärs ... besser ...

Dazu kann ich sagen: no Problem. Klick mal hier und geh nach "... Sonntag, 18. April 2010, 20:16 ..." - dort werden sie geholfen. War mal ein Projektchen für den asuro/mega8.