Kurvenanpassung unsortierter Punkte in einem Flugzeug

Question

Frage: Wie passt man eine Kurve an Punkte in einer Ebene an, wenn sie nicht einwertig sind?

Für das gezeigte Beispiel, wie würde man eine Kurve (wie die schwarze) an die lauten blauen Daten anpassen? Es ähnelt Spline-Glättung, aber ich kenne die Reihenfolge der Daten nicht.

Matlab bevorzugt werden würde, aber Pseudo-Code ist in Ordnung. Oder ein Hinweis auf die richtige Terminologie für dieses Problem wäre groß.

Dank

Answer 1

Überprüfen Sie diesen Artikel: Shape-preserving least-squares approximation by polynomial parametric spline curves scheint es eine Lösung zu präsentieren. Siehe auch das Literaturverzeichnis am Ende.

Answer 2

Sie müssen mehrere stückweise Fitting oder Splines tun. Erwarten Sie nicht, dass ein Algorithmus in der Lage ist, alles auf einmal zu erledigen. Könnte mindestens drei Kurven sein: die erste bis zur Kreuzung, die Schleife und dann zurück von der Kreuzung nach vorne.

Answer 3

Edit: nvm fehlinterpretierte die Frage. Ich werde diese Antwort hier trotzdem hinterlassen.

versuchen Vielleicht die convex hull der Punkte zu finden, zuerst, dann passen die konvexe Hülle auf der Ebene

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html < --includes Java-Animationen der Umsetzung http://en.wikipedia.org/wiki/Convex_hull_algorithms

Wenn Sie nicht wollen, Effizienz gibt es einige sehr einfache Implementierungen wie die Version Geschenkverpackung, die Version O (n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

die Teile und Herrsche ist O (n log n)

Answer 4

Ihre Daten sehen wie ein zweidimensionaler parametric plot von (x,y) in Abhängigkeit von einem zugrunde liegenden Parameter t aus. Als solche kann es möglich sein, einen least-squares Fit von x(t) und y(t) zu machen, wenn Sie ein vernünftiges Modell für sie finden können. Ihre Daten scheinen eine limacon zu beschreiben.

Answer 5

Dieses Problem ist wirklich hart, wenn Sie keine Bestellung haben. Die kleinsten Quadrate auf einigen (x (t), y (t)) ist einfach - vorausgesetzt, Sie kennen die Reihenfolge t.

Sie benötigen wahrscheinlich einen Suchalgorithmus. Ein genetischer Algorithmus könnte in Ordnung sein.

Answer 6

Sie könnten versuchen, die Reihenfolge der Punkte abzuleiten, wenden Sie dann die Spline-Verfahren an. Es gibt eine Zweideutigkeit, wo die Kurve sich natürlich kreuzt. Der vielleicht naivste Ansatz wäre die Berechnung der Delaunay-Triangulation (nlogn-Zeit), von der ein euklidischer Hamilton-Minimalabstand durch die Punkte angenähert wird. Sie müssten immer noch herausfinden, wo die "Enden" sind. Von der Bestellung könnten Sie dann die Spline-Techniken anwenden.Als Referenz finden Sie Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete oder Reinelt Papier auf TSP-Heuristik, 1992, oder EMST bei Wikipedia

hth,

Answer 7

für stückweise Annäherungen mit B-Splines Sie this Matlab Paket verwenden können. Es funktioniert auf automatischen und halb manuellen Modi.