Algorithmus-Vorschlag für effektive Ausdünnung von GPX-Tracks zu abfahrbarer Route

[torben]

Hallo zusammen,

ich bin als Motorradfahrer unterwegs und habe folgenden Usecase: Ich möchte gerne Routen von www.mopedmap.net auf mein Navigon Select (iPhone) laden um die Touren abfahren zu können.

Die Unterstützung für die Navigon-URLs (Speichern Unter-Dialog "Navigon Mobile Navigator URL") ist schon mal ein Traum!

Das Hauptproblem ist jedoch, dass das Navigon aus jedem einzelnen Wegpunkt aus dem GPX ein Zwischenziel macht und alle 50m freudig mitteilt, dass man das Ziel erreicht hätte. Das ist natürlich nicht benutzbar.

Ich habe deshalb heute mit unterschiedlichen Routen herumgespielt und folgende 80%-Lösung gefunden, die auch nicht so wahnsinnig aufwändig ist:

1. GPX laden
2. Positionsliste => Konvertiere Track in Route
3. Position => Doppelte Positionen löschen
4. Markiere alle redundanten Positionen bei einem Grenzwert von 1500 Metern mit dem Douglas-Peucker-Algorithmus.
5. Markieren-Knopf
6. Lösche markierte Positionen

Damit kommt man ganz gut hin. Wie gesagt, die Route bleibt zu gefühlten 80% intakt, aber an ein paar Stellen verläuft die neue Route leider etwas anders...

Folgende Idee für einen 100%-Algorithmus für ein Track zu Route-Algorithmus ohne manuelle Nacharbeit. Ich habe ihn manuell ausschnittsweise für ein paar Problemstellen der obigen 80%-Lösung durchgespielt und da scheint er zu passen.

Code:

i = 3
Berechnung 1: Berechne sämtliche Abbiegepunkte zwischen Trackpoint 1 und Trackpoint i (genau wie bei Position > Zwischenposition einfügen > Nur die Abbiegepunkte)
Entferne Trackpoint i-1 (Zwischenspeichern)
Berechnung 2: Berechne sämtliche Abbiegepunkte zwischen Trackpoint 1 und Trackpoint i (genau wie bei Position > Zwischenposition einfügen > Nur die Abbiegepunkte)
Für alle Abbiegepunkte aus Berechnung 2: Prüfe ob ein Äquivalent (GPS-Koordinaten) auch in Berechnung 1 vorhanden war und umgekehrt(!)
WENN Abbiegepunktemenge nicht äquivalent DANN stelle Trackpoint i-1 aus Zwischenspeicher wieder her  SONST nix tun
i = i+1
WENN i >= n-1 DANN stop SONST GOTO 1

Im Wesentlichen versucht man einfach per Trial&Error jeden Zwischen-Trackpoint zu entfernen und guckt hinterher ob sich die Route geändert hat. Hat die Route sich nicht geändert, kann der Trackpoint weg - sonst muss er bleiben.
Die Abbiegepunkte dienen nur der Zwischenberechnung, ob die Route noch identisch geblieben ist und brauchen nie selbst eingefügt werden. Auf diese Weise müsste man recht zuverlässig die Minimalanzahl an Wegpunkten für die exakt identische Route bekommen, wenn ich nicht einen Denkfehler eingebaut habe.

Ich fänd's super, wenn man diesen Algorithmus vielleicht anstatt des bisherigen für Positionsliste => Konvertiere Track in Route nehmen könnte. Dann hat man echt keinerlei Arbeit mehr...

Viele Grüße,
Torben

[routeconverter]

Die Unterstützung für die Navigon-URLs (Speichern Unter-Dialog "Navigon Mobile Navigator URL") ist schon mal ein Traum!

Hallo Torben,

danke, das freut mich.

Das Hauptproblem ist jedoch, dass das Navigon aus jedem einzelnen Wegpunkt aus dem GPX ein Zwischenziel macht und alle 50m freudig mitteilt, dass man das Ziel erreicht hätte. Das ist natürlich nicht benutzbar.

Gab es da nicht einen Tipp hier im Forum von den anderen Navigon-Nutzern, wie man damit umgehen könnte?

Ich habe deshalb heute mit unterschiedlichen Routen herumgespielt und folgende 80%-Lösung gefunden, die auch nicht so wahnsinnig aufwändig ist:

1. GPX laden
2. Positionsliste => Konvertiere Track in Route
3. Position => Doppelte Positionen löschen
4. Markiere alle redundanten Positionen bei einem Grenzwert von 1500 Metern mit dem Douglas-Peucker-Algorithmus.
5. Markieren-Knopf
6. Lösche markierte Positionen

Damit kommt man ganz gut hin. Wie gesagt, die Route bleibt zu gefühlten 80% intakt, aber an ein paar Stellen verläuft die neue Route leider etwas anders...

Der Schritt 2 wirft auch den Douglas-Peucker-Algorithmus an, vielleicht läßt sich das in Verbindung mit 2. bis 4. noch verbessern?

Folgende Idee für einen 100%-Algorithmus für ein Track zu Route-Algorithmus ohne manuelle Nacharbeit. [..]
Im Wesentlichen versucht man einfach per Trial&Error jeden Zwischen-Trackpoint zu entfernen und guckt hinterher ob sich die Route geändert hat. Hat die Route sich nicht geändert, kann der Trackpoint weg - sonst muss er bleiben.

Das ist doch das, was der Douglas-Peucker für den gesamten Linienzug macht: die Punkte entfernen, die für die Darstellung des Linienzugs nicht erforderlich sind. Wo ist der Vorteil Deines Algorithmus'?

Ich fänd's super, wenn man diesen Algorithmus vielleicht anstatt des bisherigen für Positionsliste => Konvertiere Track in Route nehmen könnte. Dann hat man echt keinerlei Arbeit mehr...

RouteConverter ist Open Source, probiers doch aus und berichte, wie die Ergebnisse so sind.

[torben]

Das Hauptproblem ist jedoch, dass das Navigon aus jedem einzelnen Wegpunkt aus dem GPX ein Zwischenziel macht und alle 50m freudig mitteilt, dass man das Ziel erreicht hätte. Das ist natürlich nicht benutzbar.

Gab es da nicht einen Tipp hier im Forum von den anderen Navigon-Nutzern, wie man damit umgehen könnte?

Hab nochmal nachgeschaut, konnte aber nichts finden. Weißt du, wo ich nochmal schauen könnte?

Folgende Idee für einen 100%-Algorithmus für ein Track zu Route-Algorithmus ohne manuelle Nacharbeit. [..]
Im Wesentlichen versucht man einfach per Trial&Error jeden Zwischen-Trackpoint zu entfernen und guckt hinterher ob sich die Route geändert hat. Hat die Route sich nicht geändert, kann der Trackpoint weg - sonst muss er bleiben.

Das ist doch das, was der Douglas-Peucker für den gesamten Linienzug macht: die Punkte entfernen, die für die Darstellung des Linienzugs nicht erforderlich sind. Wo ist der Vorteil Deines Algorithmus'?

Der Vorteil ist, dass man nicht eine Approximation durchführt wie bei Douglas-Peucker, die in Kauf nimmt dass die Route sich ggf. im Detail verändert. Der von mir vorgeschlagene Algorithmus bestimmt (hoffentlich) die minimale Menge der Wegpunkte, die für die exakt gleiche Routenführung nötig sind.
Das ist in meinen Augen schon ein wesentlicher qualitativer Vorteil.

Ich fänd's super, wenn man diesen Algorithmus vielleicht anstatt des bisherigen für Positionsliste => Konvertiere Track in Route nehmen könnte. Dann hat man echt keinerlei Arbeit mehr...

RouteConverter ist Open Source, probiers doch aus und berichte, wie die Ergebnisse so sind.

Ja, dass RouteConverter Open Source ist war mir bewusst. Ich fürchte aber, dass ich es leider einfach nicht schaffen werde mir ausreichend Zeit zu nehmen um mich dort einzufuchsen. Ich habe Spaß an der Denkaufgabe zum Algorithmus und habe natürlich ein Interesse daran die Funktionalität hinterher zu nutzen, da sie einen echten Mehrwert darstellt.

Ich bin selbst in der Softwarebranche unterwegs. Gute Software ist auch Geld wert. Ich habe dir daher eine Spende zukommen lassen. Ich bin der Meinung, dass RouteConverter auch ohne den Algorithmus bereits für mich wertvoll ist. Nichtsdestotrotz fände ich es natürlich super, wenn du einmal schauen könntest ob man das ohne wahnsinnig riesige Aufwände umsetzen könnte.

Gruß,
Torben

[routeconverter]

Hab nochmal nachgeschaut, konnte aber nichts finden. Weißt du, wo ich nochmal schauen könnte?

Wenn Du schon "gegooglet" hast: nein. Ich erinnere nichts Konkretes.

Ja, dass RouteConverter Open Source ist war mir bewusst. Ich fürchte aber, dass ich es leider einfach nicht schaffen werde mir ausreichend Zeit zu nehmen um mich dort einzufuchsen.

So geht es mir auch. Daneben erleichert die Berechnung von Zwischenpunkten über asynchrone JavaScript-Calls an Googles Server einen iterativen Algorithmus nicht

Ich bin selbst in der Softwarebranche unterwegs. Gute Software ist auch Geld wert. Ich habe dir daher eine Spende zukommen lassen. Ich bin der Meinung, dass RouteConverter auch ohne den Algorithmus bereits für mich wertvoll ist.

Danke dafür!