Übereinstimmende Zeitstempel GPS-Punkte zu einem Pfad, der keine Zeitstempel hat

Question

Ich habe zwei Datenquellen zur Verfügung - eine ist Zeitstempel GPS-Punkte, und eine andere ist ein Pfad an Straßen, ohne Zeitstempel (obwohl Punkte sind bestellt).

Ich versuche die Datenquellen zu einem angepassten Pfad zu kombinieren, der Zeitstempel basierend auf den rohen GPS-Punkten interpoliert hat. Aktuelle Versuche eines Algorithmus haben nicht funktioniert - es scheitert an Randfällen wie scharfen Ecken oder Wegen, die sich kreuzen.

Gibt es einen Algorithmus oder eine Art von Mathematik, die ich verwenden kann, um dies zu tun? Etwas wie die Summe der Fehler zwischen GPS-Punkten und angepassten Pfaden zu minimieren, während die Punkte in Ordnung gehalten werden. Ich bin mir jedoch nicht sicher, wie ich dies in eine mathematische Formel oder einen Algorithmus umwandeln soll. Es macht mir nichts aus, die Arbeit zu machen, aber ich brauche einen Hinweis darauf, welche Art von Mathematik oder Algorithmus ich verwenden kann, die gut funktionieren wird.

Answer 1

Als Baustein entscheiden Sie, wie die Anpassungsgüte (oder Kosten) bewertet wird, wenn k Punkte einem einzelnen Intervall im Pfad zugewiesen werden. Von den GPS-Zeitstempeln wissen Sie die relative Reihenfolge, in der die k Punkte besucht wurden, so dass Sie die Strafe für ein einzelnes Intervall die Länge eines Pfades in einem Intervall, das mit dem Beginn des Intervalls beginnt, alle k besucht Punkte in der Reihenfolge und endet mit dem Ende des Intervalls. Sie möchten dann alle Punkte einem Intervall zuordnen, um die Summe der resultierenden Kosten zu minimieren - das ist die Länge des Pfades, der den Anfang und das Ende jedes Intervalls besucht, und alle verfügbaren Punkte in einer Reihenfolge von die GPS-Zeitstempel und die Zuordnung von Punkten zu Intervallen.

Ich denke, Sie können die beste Zuordnung für diese Kostenfunktion mit dynamischer Programmierung finden. Berücksichtigen Sie die Intervalle im Pfad nacheinander in der Reihenfolge, in der sie im Pfad auftreten. Wenn nur zwei Intervalle im Pfad vorhanden sind und es k Punkte gibt, können Sie die beste Lösung ausarbeiten, indem Sie einfach jeden der k + 1 möglichen Splits berücksichtigen, die dem ersten und dem anderen Intervall die j-Punkte mit dem kleinsten GPS-Zeitstempel zuweisen kj zeigt auf das zweite Intervall für j = 0..k.

Wenn es mehr als zwei Intervalle in dem Weg, ihnen eines nach der anderen, in aufsteigender Reihenfolge betrachten und ein Array BestCost bauen, wo BestCost [i] [j] sind die besten Kosten, wenn Sie die ersten j zuweisen zeigt auf die ersten i Intervalle. bestCost [1] [j] ist offensichtlich, da keine Entscheidungen zu treffen sind, und der vorherige Absatz erklärt bestCost [2] [j]. Für größere Werte von i können Sie bestCost [i + 1] [j] aus bestCost [i] [j] für verschiedene Werte von j berechnen - berücksichtigen Sie jede mögliche Aufteilung der ersten j GPS-Punkte zwischen dem i + 1. Intervall und die ersten Intervalle. Suchen Sie in bestCost [i] [s] nach den besten Kosten für die s Punkte, die Sie dem ersten i-Intervall zuweisen möchten, und berechnen Sie die zurückgelegten Strecken für die j-s-Punkte, die dem i + 1-ten Intervall zugewiesen sind. Zählen Sie die beiden für jede mögliche Aufteilung zusammen und wählen Sie die niedrigste Kostenoption.

Sobald Sie bestCost [i] [j] für i = die Anzahl der Intervalle im Pfad und j = die Gesamtzahl der Punkte ausgearbeitet haben, kennen Sie die Kosten der besten Antwort, und Sie können zurück zu finden, zu finden die Zuordnung von Punkten zu Intervallen, die dies erzeugen. Sie können dies leichter für sich selbst machen, indem Sie ein wenig mehr Buchhaltung auf dem Weg nach vorne halten, als ich hier beschrieben habe - typischerweise verfolgen Sie den Wert von s, der die niedrigste Kosten-Antwort für bestCost [i] [j] in sChosen bietet [i] [j].