Wie Weg von lauten X, um zu bestimmen, Y-Daten
https://stackoverflow.com/questions/240473
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine unsortierte Liste von lauten X, Y Punkten. Sie bilden jedoch einen Weg durch die Welt. Ich würde einen Algorithmus wie eine Annäherung dieser Daten unter Verwendung von Liniensegmenten zu zeichnen.
Dies ist ähnlich wie Sie eine Linie -fitting Algorithmus verwenden würde eine Annäherung von linearen Daten zu holen. Mein Problem ist nur schwieriger, weil der Weg biegt und windet sich auf der ganzen Welt. alt text http://www.praeclarum.org/so/pathfinder.png
Kennt jemand von Standard / robust / einfacher Algorithmen zu verstehen, dies zu erreichen?
Q & A :
Was meinst du laut? Wenn ich eine ideale Realisierung des Weges habe, dann würde meine Reihe von Punkten von diesem idealen Weg abgetastet wird mit Gaußsche Rauschen auf das X- und Y-Elemente hinzugefügt. Ich weiß nicht, den Mittelwert oder Standardabweichung von dem Lärm. Ich kann am std dev ...
erraten kann,Ist die Punkte liegen in der Nähe, aber nicht auf, einig ideal, aber komplizierter Weg, die Sie suchen zu nähern? Ja.
Haben Sie eine a-priori-Informationen über er des Weges gestalten? Jede andere Art und Weise, solche Informationen zu bekommen? Leider nicht.
Lösung
Mit einer unsortierten Liste, werden Sie nicht wirklich wissen, was in jedem Segment enthält Punkte, so dass ich glaube, dass Sie nur mit dem nächsten Punkt gehen könnten.
Eine Möglichkeit könnte sein, einen Startpunkt zufällig zu holen, und in jedem Schritt den nächsten Punkt als nächsten Punkt holen. Fügen Sie die ersten beiden Punkte auf einen Satz S.
Setzen Sie eine Linie an die Punkte in S bis der RMS einen gewissen Wert übersteigt, dann klar S und eine neue Zeile beginnen.
Der Schnittpunkt von aufeinanderfolgenden Linien würden die Endpunkte der Segmente werden.
Andere Tipps
Bezier Interpolation Ihr Problem passen.
Dies bezieht sich nicht auf die Reihenfolge der Punkte in einen Pfad, jedoch; gibt es eine Reihe von Ansätzen zu berücksichtigen:
- Jeder „optimal“ Pfadtyp (zB kleinste Richtungsänderung an jedem Punkt auf dem Weg, * kürzester Weg durch alle Punkte) wird wahrscheinlich kocht die NP vollständig nach unten Reisen Salesman Problem (TSP).
- Ein „vernünftiger“ Pfad die Knoten clustern und dann Strecke zwischen den Clustern und innerhalb von Clustern. Natürlich, desto größer die Cluster, oder je größer sieht die Anzahl der Cluster desto mehr kleineres Problem wie ein großen n TSP.
- Bestellen der Punkte durch eine Achse. Wenn es viel mehr als 2 Achsen, einig Dimensionsreduktion Strategie nützlich sein kann. z.B. Independent Component Analysis.
Wenn Sie Ihre Punkte sind nahe beieinander, können Sie normal „gerade“ Linien (orthogonale Linien). Mit Hilfe der normalen Glättungsalgorithmen . Sie können die Welt als flach sehen.
Wenn sie weit voneinander entfernt sind, müssen Sie für die Rundung der Erde zu kompensieren, von Großkreise von Punkt zu navigieren zu zeigen. Andernfalls wird Ihr gerade Linien einen längeren Weg machen.
Es ist Ihre Wahl, wenn ein Punkt zu weit ist gerade Linien zu schaffen.
Ferner müssen Sie wissen, wenn Sie auf „Besuch“ jeden Punkt, oder einfach nur in der Nähe gehen müssen, und wie nahe, dass in der Nähe ist.
Wenn Sie den Kurs (en) zu einem Flugzeug, Schiff oder anderen Reisenden zu senden, müssen Sie wahrscheinlich jeden Punkt besuchen. Wenn Sie die GPS-Daten von einem Objekt erhalten, wahrscheinlich wollen Sie nur einen Kurs auf einem Bildschirm zeichnen, und das Rauschen entfernen.
Nach Ihren Änderungen zu sehen: Wenn dies ein Objekt etwas traject bewegen Sie darstellen möchten, können Sie die Richtung glätten und anstelle der x / y-Werte zu beschleunigen. (Erstellen der Messwerte (x) haben einen festen und steigenden Y-Intervall macht viel einfacher zu glätten.)
Hier ist ein heuristisches Hack, der die Reihenfolge Problem für die Daten, wenn
könnte Adresse- Sie haben genug Punkte
- der mittlere Abstand zwischen den Punkten ist klein im Vergleich zu dem kleinsten Krümmungsradius des Weges erwartet
- der mittlere Abstand zwischen den Punkten ist nicht groß im Vergleich zu dem std. dev. des Lärms
- wird der Pfad nicht selbst Kreuzung (Sie könnten Glück haben, aber keine Garantie)
Gehen Sie wie folgt aus:
- Wählen Sie (hoffentlich durch eine sinnvolle und nicht zufällig Mittel) ein Ausgangspunkt, p1 .
- Sie erhalten alle Punkte, die in einem gewissen Abstand Clustering liegen, R_c p1 . Wählen Sie R_c klein im Vergleich zu dem erwarteten Wenderadius, aber groß im Vergleich zur Streuung.
- Rufen Sie diese Cluster C1 .
- Finden Punkt q1 der Mittelwert der Positionen in C1 .
- Setzen Sie eine Linie zu den Punkten in C1 und Projekt (oder darüber hinaus) den Rand des Clusters, und den nächsten Punkt in Ihren ursprünglichen Daten. Label, das Punkt p2 .
- Iterate die Schritte 2-5, bis Sie aus Daten ausgeführt werden.
Jetzt haben Sie eine neue Liste der Punkte q1 .. qn , die bestellt werden.
Aus der Spitze von meinem Kopf, sehr rau, und funktioniert nur unter recht guten Bedingungen ...
Selbst crossing Verhalten kann wahrscheinlich durch die Forderung, in Schritt verbessert werden (5), dass die neue projizierte Linie liegt innerhalb eines gewissen maximalen Winkel von dem vorherigen.
Das Problem mit der Bezier-Kurve ist also eigentlich nicht gehen, obwohl die Punkte, die Sie probiert haben und auch wenn die Punkte Proben ein wenig verzerrt; die Bezier-Kurve tatsächlich sein könnte Meilen vor.
Eine bessere Annäherung, und eine Lösung, die das ursprüngliche Bild Art und Weise besser ist ein Catmull-Rom Spline weil es aber alle Punkte in der Kurve ausgeführt wird.
Mein Ansatz wäre, zunächst die Liste der Punkte zu sortieren, dann eine Bezier-Kurve verwenden.
Der Trick ist natürlich die Sortierung. Beginnen Sie mit einem beliebigen Punkt und den nächsten Punkt finden. Angenommen, diese beiden sind miteinander verbunden. Mit diesen beiden Endpunkten, finden die nächsten Punkte zu ihnen. Es sei angenommen, dass die eine mit dem kleineren Abstand zu ihm ist Endpunkt zu diesem Punkt verbunden ist. Wiederholen, bis alle Punkte verbunden sind.
Ich gehe davon aus, dass es noch einige Probleme mit diesem Ansatz, aber vielleicht können Sie es als Ausgangspunkt nutzen (Wortspiel beabsichtigt).
Edit: Sie können es mehrmals mit verschiedenen Startpunkten tun, und dann sehen, wo die Ergebnisse abweichen. Das zumindest gibt Ihnen einige Vertrauen, die Punkte miteinander verbunden sind.
Ein ganz anderer Ansatz, die nicht eine andere Einschränkung erfordert, aber Details zu Ihrer Anwendung abhängen. Es sghould funktioniert am besten, wenn Sie eine „dichte Wolke von Punkten“ haben rund um den Weg.
Mit einer „Kosten“ Funktion, die die Differenz zwischen der Kurve und der Wolke von Punkten definiert. Verwenden Sie eine parametrisierte Kurve, und ein Standard-Optimierungsalgorithmus. - ODER - Beginnen Sie mit einer geraden Kurve vom Anfang bis zum Ende, dann einen genetischen Algorithmus verwenden, um es zu ändern.
Die typische Kostenfunktion den kleinsten Abstand zwischen jedem Punkt und der Kurve, und der Summe der Quadrate zu nehmen wäre.
Ich habe nicht genug Erfahrung, eine Optimierung oder genetischen Algorithmus vorschlagen, aber ich bin sicher, dass es getan werden kann:)
Ich könnte einen genetischen Algorithmus wie folgt vorstellen: Der Weg wird von Wegpunkten gebaut werden. Beginnen Sie mit Inbetriebnahme der N Wegpunkte in einer straigt Linie von Anfang bis Ende. (N kann je nach Problemstellung gewählt werden). Mutationen können sein:
- Für jedes Segment, wenn RND ()
- Für jeden Wegpunkt, die X- und Y-Koordinate leicht variiert werden.
Sie müssen die Gesamtlänge in der Kostenfunktion aufzunehmen. Splitting möglicherweise nicht benötigt werden, oder vielleicht × (die „split Chance“) könnte als mehr Wegpunkte eingeführt werden, müssen verringern. Sie können oder können nicht wollen, (2) an den Start- und Endpunkt zu übernehmen.
Würde Spaß, das versuchen ...
Ich nehme an, dass „unsortierten Liste“ bedeutet, dass, während die Menge der Punkte abgeschlossen ist, Sie nicht wissen, in welcher Reihenfolge sie wurden durch gereist?
Das Gaußsche Rauschen hat grundsätzlich ignoriert werden. Wir sind absolut keine Informationen gegeben, die uns jeden Versuch zu machen, ermöglichen den ursprünglichen, unver laut Weg zu rekonstruieren. Also ich denke, das Beste, was wir tun können, ist nehmen die Punkte korrekt sind.
An diesem Punkt wird die Aufgabe besteht darin, „finden Sie den besten Weg durch eine Menge von Punkten“, mit „besten“ vage gelassen. I ausgepeitscht einige Codes up, das eine Menge von Punkten im euklidischen Raum zu bestellen versucht, lieben Anordnungen, die in geradere Linien führen. Während die Metrik zu implementieren war leicht zu, konnte ich nicht eine gute Art und Weise denken Sie an die Bestellung auf dieser Grundlage zu verbessern, so dass ich Punkte nur zufällig tauschen für eine bessere Anordnung suchen.
So, hier einig PLT Scheme-Code, der das tut.
#lang scheme
(require (only-in srfi/1 iota))
; a bunch of trig
(define (deg->rad d)
(* pi (/ d 180)))
(define (rad->deg r)
(* 180 (/ r pi)))
(define (euclidean-length v)
(sqrt (apply + (map (lambda (x) (expt x 2)) v))))
(define (dot a b)
(apply + (map * a b)))
(define (angle-ratio a b)
(/ (dot a b)
(* (euclidean-length a) (euclidean-length b))))
; given a list of 3 points, calculate the likelihood of the
; angle they represent. straight is better.
(define (probability-triple a b c)
(let ([av (map - a b)]
[bv (map - c b)])
(cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2))))
; makes a random 2d point. uncomment the bit for a 3d point
(define (random-point . x)
(list (/ (random 1000) 100)
(/ (random 1000) 100)
#;(/ (random 1000) 100)))
; calculate the likelihood of an entire list of points
(define (point-order-likelihood lst)
(if (null? (cdddr lst))
1
(* (probability-triple (car lst)
(cadr lst)
(caddr lst))
(point-order-likelihood (cdr lst)))))
; just print a list of points
(define (print-points lst)
(for ([p (in-list lst)])
(printf "~a~n"
(string-join (map number->string
(map exact->inexact p))
" "))))
; attempts to improve upon a list
(define (find-better-arrangement start
; by default, try only 10 times to find something better
[tries 10]
; if we find an arrangement that is as good as one where
; every segment bends by 22.5 degrees (which would be
; reasonably gentle) then call it good enough. higher
; cut offs are more demanding.
[cut-off (expt (cos (/ pi 8))
(- (length start) 2))])
(let ([vec (list->vector start)]
; evaluate what we've started with
[eval (point-order-likelihood start)])
(let/ec done
; if the current list exceeds the cut off, we're done
(when (> eval cut-off)
(done start))
; otherwise, try no more than 'tries' times...
(for ([x (in-range tries)])
; pick two random points in the list
(let ([ai (random (vector-length vec))]
[bi (random (vector-length vec))])
; if they're the same...
(when (= ai bi)
; increment the second by 1, wrapping around the list if necessary
(set! bi (modulo (add1 bi) (vector-length vec))))
; take the values from the two positions...
(let ([a (vector-ref vec ai)]
[b (vector-ref vec bi)])
; swap them
(vector-set! vec bi a)
(vector-set! vec ai b)
; make a list out of the vector
(let ([new (vector->list vec)])
; if it evaluates to better
(when (> (point-order-likelihood new) eval)
; start over with it
(done (find-better-arrangement new tries cut-off)))))))
; we fell out the bottom of the search. just give back what we started with
start)))
; evaluate, display, and improve a list of points, five times
(define points (map random-point (iota 10)))
(define tmp points)
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 100))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 1000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
Es scheint, dass Sie die ‚goldene Kurve‘ aus dem Antworten auf die Fragen wissen, würde ich vorschlagen, die Bezier-Kurve der ‚goldenen Kurve‘ zu finden, wie durch @jamesh vorgeschlagen und Zeichnung.
Wie viele Punkte haben Sie?
Eine Bezier-Kurve, wie bereits erwähnt, ist eine gute Idee, wenn Sie comparedly paar Punkte haben. Wenn Sie viele Punkte haben, buiding Cluster wie Dmckee vorgeschlagen.
Jedoch Sie auch müssen eine andere Einschränkung für die Reihenfolge der Punkte definieren. Es gibt viele gute Vorschläge gewesen, wie die Punkte zu wählen, aber wenn Sie eine andere Beschränkung einführen, jede gibt eine mögliche Lösung.
Mögliche Einschränkungen Ich kann mich:
- kürzester Weg
- die meisten geraden Segmenten
- mindestens gesamte absolute Rotation
- Richtungspräferenz (d.h. horizontal / vertikal ist wahrscheinlicher als kreuz und quer)
In allen Fällen den Zwang treffen Sie wahrscheinlich alle Permutationen der Sequenz testen müssen. Wenn Sie mit einer „guten guess“ beginnen, Cayn Sie die andere schnell beenden.
