-         

Ergebnis 1 bis 6 von 6

Thema: Punkt in Polygon-Fläche?

  1. #1
    Erfahrener Benutzer Robotik Einstein Avatar von Jaecko
    Registriert seit
    16.10.2006
    Ort
    Lkr. Rottal/Inn
    Alter
    35
    Beiträge
    1.987

    Punkt in Polygon-Fläche?

    Anzeige

    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
    #ifndef MfG
    #define MfG

  2. #2
    Benutzer Stammmitglied
    Registriert seit
    29.08.2008
    Beiträge
    73
    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:
    Klicke auf die Grafik für eine größere Ansicht

Name:	dreieck.jpg
Hits:	5
Größe:	3,2 KB
ID:	22116

    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

  3. #3
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    31.05.2009
    Beiträge
    251
    Hallo Jaecko,
    schau mal hier..............
    http://www.dbs.ifi.lmu.de/Lehre/GIS/SS2009/Skript/Kap-06.pdf
    mfG
    Willi

  4. #4
    Erfahrener Benutzer Robotik Einstein Avatar von Jaecko
    Registriert seit
    16.10.2006
    Ort
    Lkr. Rottal/Inn
    Alter
    35
    Beiträge
    1.987
    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.
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken Polygone_Eckschnittpunkte.gif  
    Geändert von Jaecko (01.05.2012 um 15:07 Uhr)
    #ifndef MfG
    #define MfG

  5. #5
    Erfahrener Benutzer Robotik Einstein Avatar von Jaecko
    Registriert seit
    16.10.2006
    Ort
    Lkr. Rottal/Inn
    Alter
    35
    Beiträge
    1.987
    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
    #ifndef MfG
    #define MfG

  6. #6
    Erfahrener Benutzer Robotik Visionär Avatar von oberallgeier
    Registriert seit
    01.09.2007
    Ort
    Oberallgäu
    Beiträge
    7.557
    Zitat Zitat von Jaecko Beitrag anzeigen
    ... 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.
    Ciao sagt der JoeamBerg

Ähnliche Themen

  1. Eagle: Polygon ohne Rand?
    Von Tido im Forum Konstruktion/CAD/Sketchup und Platinenlayout Eagle & Fritzing u.a.
    Antworten: 2
    Letzter Beitrag: 22.12.2010, 20:57
  2. Problem mit dem Polygon bei eagle
    Von humus im Forum Konstruktion/CAD/Sketchup und Platinenlayout Eagle & Fritzing u.a.
    Antworten: 2
    Letzter Beitrag: 15.02.2008, 16:36
  3. Eagle Masseflächen (Polygon GND) fragen
    Von Accenter im Forum Konstruktion/CAD/Sketchup und Platinenlayout Eagle & Fritzing u.a.
    Antworten: 4
    Letzter Beitrag: 24.10.2007, 13:19
  4. Punkt im Raum bestimmen
    Von BlackBroom im Forum Sensoren / Sensorik
    Antworten: 9
    Letzter Beitrag: 11.11.2004, 12:06
  5. [ERLEDIGT] Den hellsten punkt erkennen
    Von Mr.X im Forum Sensoren / Sensorik
    Antworten: 9
    Letzter Beitrag: 04.11.2004, 10:38

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •