Einen "Pfad" (oder GPS-Spur) eines Fahrzeugs vergleichen

Question

Ich habe ein bisschen eine schwierige Algorithmusfrage, ich kann keinen passenden Algorithmus aus einer Menge Suchen finden, also hoffe ich, dass jemand hier auf Stackoverflow könnte kenne die Antwort.

Ich habe eine Reihe von x, y-Koordinaten für ein Fahrzeug, wenn es sich durch ein 2D-Raum bewegt, die Koordinaten werden an "Entscheidungspunkten" in der Zeitperiode aufgezeichnet (dh sie haben angehalten und eine Entscheidung getroffen, wohin sie sich bewegen sollen) Nächster).

Was ich tun möchte, ist einen Mechanismus zu finden, um diese Spuren effizient zu vergleichen (d. H. Nicht jeden Punkt einzeln durchlaufen zu müssen). Hinzu kommt, dass ich mich für das "Muster" ihrer Bewegung interessiere, nicht unbedingt für die einzelnen Punkte, zu denen sie gegangen sind. Dies bedeutet, dass der "Pfad" als derselbe gilt, wenn Sie ihn um eine Achse reflektieren oder wenn Sie ihn um 90, 180 oder 270 Grad drehen.

Im Grunde versuche ich eine Art "Verhalten" auf die Art und Weise, wie sie sich durch den Raum bewegen, zu destillieren und dann die verschiedenen "Verhaltensweisen" zu Klassifizierungszwecken zu untersuchen.

Cheers,

Aidan

Answer 1

Dies kann Art und Weise komplizierter sein, als Sie suchen, aber es klingt wie das, was die Jungs haben bei astrometry.net zu ähnlich sein, was Sie suchen. Im Wesentlichen können Sie ein Bild von einigen Sternen hochladen, und es wird herausfinden, die Position in den Himmel gehört, zusammen mit Rotation, können Sie in der Lage sein, ähnliche Muster zu verwenden, was Sie suchen.

Sie haben eine tolle pdf erklären, wie es funktioniert here, und anscheinend können Sie sie per E-Mail und sie werden Ihnen den Quellcode senden (Details sind in der pdf).

Edit: offenbar können Sie den Code direkt herunterladen here.

Hoffe, es hilft.

Answer 2

gibt es mehrere Ansätze könnten Sie machen:

Mit Vektorpfade und Übersetzung Matrizes zusammen mit zwei Algorithmen, die A * (ein Stern) Algorithmus (am besten Routen aus zu orten, was gierig Funktionen aufgerufen werden), und die "nearest neighbor" -Algorithmus - diese werden beide üblicherweise zum Vergleichen von Pfad-Effizienzen für Routen verwendet.

Sie können es nicht wissen, aber das Problem, das Sie haben, ist bekannt als das "Reisen Verkäufer" Problem und hat viele viele Ansätze.

sehen so hoch

Verkäufer Problem Reisen A * Nächster Nachbar

auch einen Blick auf

Random-Walk-Algorithmus - für den grundlegendsten Ansatz

für ein Verhalten Ansatz gelernt versuchen neuronale Netze "ANN" oder genetische Algorithmen

die Mathematik für diese Art von Problem sind unter der sogenannten "Graph-Theorie" abgedeckt

Answer 3

Es scheint, dass im Grunde, was ist eine Metrik benötigt, um zwei (N im Allgemeinen) Pfade zu vergleichen und wählen Sie die beste? Wenn das der Fall ist, würde ich einfache Statistiken vorschlagen. Ich würde mit Überschrift (Orientierung) Histogramm, relativ (im Vergleich zu vorherigen Überschrift) Überschrift Histogramm und so weiter beginnen. Andere Sache kommt mir in den Sinn - Abstand/Orientierung zwischen Kovarianz der Punkte. Oder einfach eine Art "Statistik" (Anzahl der Umdrehungen usw.) erstellen und diese Pfade vergleichen.