Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Algorithmus-Vorschlag für effektive Ausdünnung von GPX-Tracks zu abfahrbarer Route
#1
Hallo zusammen,

ich bin als Motorradfahrer unterwegs und habe folgenden Usecase: Ich möchte gerne Routen von http://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! Wink

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
Reply


Messages In This Thread
Algorithmus-Vorschlag für effektive Ausdünnung von GPX-Tracks zu abfahrbarer Route - by torben - 26.03.2011, 19:48

Forum Jump:


Users browsing this thread: 1 Guest(s)