Punkt in Polygon-Fläche?

[Jaecko]

Moin.

Welche effiziente (µC-geeignete) Methode gibt es, herauszufinden, ob ein beliebiger Punkt P_n innerhalb eines (durch ein Punkte-Array beschriebenes) Polygons liegt?

Praktische Anwendung z.B.:
Bin ich mit meiner GPS-Position innerhalb einer bestimmten Stadt?
Oder würde ich mit einem Projektil eine bestimmte Fläche treffen?

Meine bisherige Idee:
Ich such mir von den Punkten den kleinsten X-Wert und den kleinsten Y-Wert. Von diesem Punkt P_min geh ich nochmal jeweils eine Einheit Richtung negativer Werte => P_ref, so dass ich nicht auf einem Eckpunkt liege, falls y_min und x_min zum gleichen Punkt gehören sollten.

Ich ziehe eine Linie LP von diesem P_ref zu meinem Punkt P_n und berechne für jede Linie Ln des Polygons, ob sich Ln und LP schneiden/berühren.
Ist die Anzahl der Schnittpunkte ungerade, muss der Punkt im Polygon liegen.
Der Sonderfall, dass die Linie durch einen der Eckpunkte des Polygons läuft, wird ja dadurch "gelöst", dass der Eckpunkt dann für beide angrenzenden Linien als "geschnitten" berechnet wird (auch wenn es mathematisch nur 1 Punkt ist), somit bleibt die Gesamtanzahl gerade bzw. ungerade.

Nur kommt mir das doch etwas "ineffizient" vor, v.a. steigt ja der Rechenaufwand mit Anzahl der Polygonpunkte gewaltig, was sich aber wohl bei keinem Algorithmus verhindern lassen dürfte.

Gibts da was besseres? Wichtig ist, dass diese Berechnung später auf einem µC laufen soll.

mfG

[ElchiMtr]

Hallo,

Also ich würde dem Problem mit etwas Vektorgeometrie zu leibe rücken.
zu erst teilt man das Polygon in Dreiecke und dann kann man überprüfen, ob der Punkt in einem der Dreiecke ist.
Das kann man mit der Skizze ganz gut bewerkstelligen:


a *n +b *m = c

der Vektor c zeigt auf deinen Punkt. Dieser liegt zwischen a und b, wenn n + m <= 1 aber m und n positiv sind.

Ich hoffe du verstehst was ich versuche zu sagen. Du solltest alles noch mal durchdenken, aber so sollte das gehen.

Gruß
ElchiMtr

[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.