[Code] Ellipse aus Punktmenge erstellen

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von aRiGaT0, 25. August 2011 .

Schlagworte:
  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen
  1. #1 25. August 2011
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    Ellipse aus Punktmenge erstellen

    Hallo Leute,

    ich suche einen Algorithmus mit dem ich aus eine Ellipse um eine Anzahl von Messpunkten ziehen kann. Es handelt sich also um eine Punktwolke, um die die Ellipse gezogen werden soll, so dass z.B. 95 % aller Messpunkte in der Ellipse liegen.

    Mein Ansatz ist bisher folgender:

    Als erstes generiere ich ein Array in dem der Abstand jedes Punktes zum Urspung eingetragen ist (Pythagoras). Diesen Array sortiere ich nun der Größe nach.
    Nun durchlaufe ich mit einer for-Schleife das sortiere Array und rechne die Prozentwerte aus, so dass z.B. 95 % innerhalb meiner Werte liegen, um mögliche Ausreißer auszuschließen.

    Jetzt habe ich meinen ersten Wert der Ellipse. Meint ihr kann so vorgehen?

    Ich habe die Problemstellung mal mit Paint aufgezeichnet: das Rote ist die Ellipse, in der sich die Punktmenge befindet.
    [​IMG]

    Grüße
     

  2. Anzeige
    Dealz: stark reduzierte Angebote finden.
  3. #2 29. August 2011
    AW: Ellipse aus Punktmenge erstellen

    Dafür fallen mir gleich mehrere Lösungen ein.

    1. Wenn man nicht weiter weiss, ist einfach optimieren immer gut. Stell eine Fehlerfunktion (Kostenfunktion, Energiefunktion, wie auch immer man es nennen will) abhängig von den Ellipsen-Parametern auf, die meinetwegen die Fläche minimiert wärend alle Punkte drin liegen müssen. Lös das mit einem Optimierungsverfahren Deiner Wahl.

    2. Den Schwerpunkt der Punkte ist ja trivial zu berechnen. Dadurch müsste man eine "Schwerpunkt-Achse" legen. Das hat auch nen Namen, der mir aber nicht einfällt. Oder: eine PCA (Principle Component Analysis) gibt Dir da schon fast alles, was Du brauchst, musst nur eine Ellipse daraus konstruieren.

    3. Kurz mal googlen: java - Bounding ellipse - Stack Overflow

    EDIT:
    Wegen 95% und Ausreissern: Nimm einfach RANSAC auf eins der möglichen Verfahren.
     
  4. #3 29. August 2011
    AW: Ellipse aus Punktmenge erstellen

    Du kannst auch die Convexe-Hülle relativ einfach errechnen (gibt z.B. nen guten Sweepline-Algorithmus dafür). Wenn du die Convexe Hülle mal hast, sollte es relativ einfach sein, um diese eine Ellipse zu legen.

    Etwas Literatur dazu:
    Algorithmen und Komplexit
     
  5. #4 1. September 2011
    AW: Ellipse aus Punktmenge erstellen

    Ausreisser machen Dir die Konvexe-Hülle aber unbrauchbar. Gut, könnte man mit random-sampling etc. vielleicht umgehen. Davon abgesehen stehe ich aber auf dem Schlauch: Wie findet man relativ einfach eine möglichst minimale Ellipse um diese konvexe Hülle herum?

    Übrigens: In der von mir verlinkten Stack-Overflow Antwort ist der optimale Algorithmus beschrieben ;)
     
  6. #5 1. September 2011
    AW: Ellipse aus Punktmenge erstellen

    Was für Ausreisser denn ? Er hat doch ne feste Punktmenge. Davon kann man einfach ne CH bauen.

    Ich habs nicht 100% überprüft/durchgedacht. Aber sollte es nicht reichen, wenn er die Punkte (die der CH) nach x-Koordinate sortiert, dass er dann den ersten und letzten Punkt nimmt, und von dort aus seine Ellipse aufspannt ? (Also gerade von 1. zu letztem Punkt, und dann ellipse aufspannen über die am weitesten entfernten Punkten (der CH).)

    Jup, hab ich gesehen. Wollt nur noch mehrere Möglichkeiten aufzeigen/diskutieren.
     
  7. #6 2. September 2011
    AW: Ellipse aus Punktmenge erstellen

    Steht doch in der Fragestellung, dass er Ausreisser hat, und daher will, dass 95% der Punkte in der Ellipse liegen. Das ist ja überhaupt er der Sinn des Ganzen ;)

    Dafür braucht man die konvexe Hülle aber nicht, sondern kann gleich die Punkte nach x und y sortieren. Entsprechend die minimale Bounding-Box bestimmen und die darin beschriebene Ellipse verwenden. Eigentlich gar kein so schlechter Ansatz, braucht aber Extra-Behandlung für die Ausreisser und Du hast keine Ahnung, wieweit die Lösung vom Optimum entfernt ist. Lassen sich sicherlich Fälle konstruieren, in denen Du mit einer sehr schlechten Lösung endest.
     
  8. #7 2. September 2011
    AW: Ellipse aus Punktmenge erstellen

    Ich hab das mit den Ausreissern anders verstanden. Ich dachte dass eine Fehlerquote von 5% erlaubt ist, nicht gewuenscht.

    Zur CH, sollte das nicht Lfz-Technisch weitaus schneller sein?

    Sorry, schreib grad vom Handy aus, daher bisschen kurzer Beitrag.
     
  9. #8 4. September 2011
    AW: Ellipse aus Punktmenge erstellen

    Nein, es gibt eben Ausreisser, die außerhalb der anderen Messwerte liegen.

    Habe es jetzt so realisiert:

    1. Schritt: Auffinden der großen Halbachse, wie oben schon beschrieben über Pythagoras
    2. Schritt: arctan(y/x) ergibt den Winkel
    3. Alle Koordinaten um den Winkel drehen. Ellipse liegt jetzt der länge nach im Koordinatensysstem. Jetzt ziehe ich die Ellipse (Ellipsengleichung!) einfach um die Messwerte und zähle wieviel noch innerhalb sind. Wenn der vom User vorgegebene Grenzwert erreicht ist, breche ich ab. Die Ellipse wird dabei 0.1 Schritten immer kleiner.

    Das Ergebnis sieht echt schon super aus. Jetzt muss ich noch ein bisschen die Laufzeit optimieren. Bei ~350 000 Messwerten brauche ich schon ~5-8 Minuten.

    Danke für die Hilfe!

    Gruß
     

  10. Videos zum Thema
Die Seite wird geladen...
Similar Threads - Code Ellipse aus
  1. Antworten:
    0
    Aufrufe:
    3.243
  2. Antworten:
    6
    Aufrufe:
    7.779
  3. Antworten:
    1
    Aufrufe:
    1.393
  4. Antworten:
    2
    Aufrufe:
    5.073
  5. Antworten:
    0
    Aufrufe:
    922