Ellipse identifizieren

[positronium]

Hallo,

wieder ein mathematisches Problem von mir: Ich habe in 3D eine Menge Punkte p[down]n[/down] numerisch vorliegen, und will den Mittelpunkt m und die beiden Achsenvektoren a und b der diese Punkte enthaltenden Ellipse errechnen.
Mein Versuch sieht so aus:
Ich nehme 4 der Punkte, p[down]1..3[/down] und p[down]x[/down], und errechne zuerst aus p[down]1..3[/down] die auf der Ellipsenebene stehende Normale n=(p[down]2[/down]-p[down]1[/down])x(p[down]3[/down]-p[down]2[/down]), und projeziere p[down]x[/down] auf diese Ebene mit p[down]4[/down]=p[down]x[/down]+k*n. Dann kann ich ein Gleichungssystem aufstellen:
p[down]1..4[/down]=m+cos(w[down]1..4[/down])*a+l*sin(w[down]1..4[/down])*(a x n)
w ist der umlaufende Winkel und l der Streckungsfaktor der zweiten Achse b, wobei ich b = a x n setze.
An dem Punkt habe ich also ein Gleichungssystem mit 12 Gleichungen und ebenso vielen Unbekannten, aber: das Gleichungssystem ist nicht linear, was es ziemlich kompliziert macht. Ich komme nicht weiter.

Ist der Ansatz vernünftig bzw. wie kann ich damit zu einer Lösung kommen?
Gibt es eine bessere Methode?

Gruss

positronium

[tomS]

Ich würde zunächst mal die zwei Punkte bestimmen, deren Abstand maximal ist. Daraus folgt die Lage der großen Halbachse sowie der Mittelpunkt. Dann würde ich die zwei Punkte bestimmen, die senkrecht dazu den größten Abstand haben. Daraus folgt die Lage der kleinen Halbachse.

Dann würde ich die gesamte Punktewolke so rotieren, dass alle Punkte in der xy-Ebene liegen und dass die Ellipse symmetrisch zur x- und zur y-Achse liegt.

[positronium]

Vielen Dank für Deine Antwort!
Leider liegen die Punkte meist in nur einem Teil der Ellipse, maximal um den halben Umfang, in der Regel wird wohl ein Bereich von ca. 45° bis 180° abgedeckt. Deshalb kann ich nicht direkt Daten heraus suchen, sondern muss rechnen.

[tomS]

Die nächste Methode die mir einfällt ist die Methode der kleinsten Quadrate.

Du setzt eine Parameterdarstellung deiner Ellipse an, ausgehend von einem zunächst unbekannten Mittelpunkt sowie ebenfalls zunächst unbekannten großen und kleinen Halbachsen (oder einer anderen Darstellung).

Dann definierst du die Summe derFehlerquadrate als Funktion des Mittelpunktes sowie der Halbachsen. Für eine Ellipse in drei Dimensionen sind das nach meiner Zählung
- drei Unbekannte für den Mittelpunkt
- drei Unbekannte für Länge und Richtung der ersten Halbachse
- zwei Unbekannte für die zweite Halbachse (eine entfällt aufgrund der Bedingung, dass beide Halbachsen senkrecht stehen)

Dann minimierst du die Summe der Fehlerquadrate iterativ, in dem du die Ableitung (den Gradienten) der Summe nach den unbekannten Parametern bestimmst und so das Minimum bestimmst. Wenn du die Summe explizit hinschreiben kannst (kannst du) ist es evtl. sinnvoll, den Gradienten explizit als Funktion und nicht numerisch zu bestimmen.

Zur numerischen Berechnung würde ich die Conjugate Gradients Methode empfehlen, aber ich denke, dazu gibt es ausführliche Literatur und Software im Internet.

http://de.wikipedia.org/wiki/Methode_de ... n_Quadrate
http://de.wikipedia.org/wiki/CG-Verfahren

[positronium]

Das ist eine gute Idee, Danke, aber das würde leider nur in manchen Sonderfällen funktionieren. Ich habe nämlich eine Punktmenge, deren Elemente nicht alle auf der Ellipse liegen müssen, das aber mehrheitlich sollten. Beispielsweise könnte das so aussehen (normalerweise mit deutlich mehr Punkten):

ellipse.png (4.38 KiB) 4755 mal betrachtet

Die Reihenfolge der Punkte ist bekannt, und alle liegen abgesehen von Rundungsfehlern in einer Ebene. Deshalb dachte ich, immer vier aufeinander folgende zu nehmen, und jeweils eine Ellipse zu konstruieren, wodurch dann einige der Mittelpunkte nahe beisammen liegen müssten; deren Mittelpunkt wäre dann der Mittelpunkt der gesuchten Ellipse.
Gibt es denn bei Ellipsen keine Möglichkeit wie beim Kreis, wo man die Mittelsenkrechten zwischen zwei Punktpaaren schneidet, nur eben etwas aufwendiger?

[tomS]

In dem Fall musst du die Punktewolke eben zunächst plotten und die unerwünschten Punkte aussondern.

[positronium]

Ich muss noch überlegen; vielleicht kann ich etwas mit den Winkeln zwischen den Segmenten machen, um die falschen Punkte auszusortieren, weil das alles vollautomatisch in einem Programm aublaufen muss.
Vielen Dank für Deine Hilfe!