#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. Grüße + Multi-Zitat Zitieren
#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. + Multi-Zitat Zitieren
#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 + Multi-Zitat Zitieren
#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 + Multi-Zitat Zitieren
#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. + Multi-Zitat Zitieren
#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. + Multi-Zitat Zitieren
#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. + Multi-Zitat Zitieren
#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ß + Multi-Zitat Zitieren