Jaecko
12.04.2012, 11:52
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
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