[Talk-de] Viele GPX-Tracks sinnvoll vereinen

[Rainer Kluge]

Hallo Peter,
Am 06.11.2010 16:46, schrieb Peter Herison:
> Am 05.11.2010 18:57, schrieb Peter Herison:
> 
> OK, nach ein bischen Recherche scheint es sich hierbei um ein
> klassisches CPP (Chinese Postman Problem) zu handeln. Hat sich schon
> jemand damit befasst?

Ich habe vor kurzem ein Skript erstellt, welches aus OSM-Routen-Relationen, z.B.
Radwanderwegen, einen GPX-Track erstellt. Das ist zwar für deinen Anwendungsfall
nicht einsetzbar, aber ich hatte mit ähnlichen Problemen zu tun.

Wenn ich richtig verstanden habe, dann hast du eine Sammlung von GPX-Tracks, die
du zu einem einzigen Track zusammenfassen möchtest. Dieser Track soll mit dann
einem GPS-Gerät nachnavagiert werden.

> Der Algorithmus ist mir klar, aber es hapert ein wenig an der Umsetzung:
> 1. Ich finde keinen fertigen Code (Java oder Perl), der mir eine Loesung
> ausspuckt.

Den wirst du wohl auch nicht finden, da es in fast jedem Anwendungsfall
Randbedingungen gibt, die der Algorithmus nicht berücksichtigt. Ob das in deinem
Fall so ist, kann schwer beurteilt werden, da zu wenig über die Nutzung der
Tracks bekannt ist.

> 2. Ich habe in meinem GPX keine Knoten, sondern nur Kanten. Das liesse
> sich zwar haendisch regeln, aber automatisch waere schoener. ;)

Ich unterstelle, damit meinst du: einzelner GPX-Track = Kante; keine Knoten, da
benachbarte Anfangs-/Endpunkte zweier Tracks unterschiedliche Koordinaten haben.

Meiner Erfahrung nach lässt sich das nur dann automatisch lösen, wenn es eine
eindeutige Regel für die zu verbindenden Tracks gibt, z.B.: wenn
Anfangs-/Endpunkt des Track 1 weniger als x Meter vom Anfangs-/Endpunkt des
Track 2 entfernt ist, dann verbinde die Tracks. Das kann aber auch in die Hose
gehen, wenn zwischen den beiden Punkten ein Hindernis liegt, z.B. ein Fluss. Und
es muss sichergestellt sein, dass das Ende einer Sackgasse vom nächstgelegenen
Track soweit entfernt ist, dass keine automatische Verbindung erzeugt wird.

Solltest du es schaffen, einen zusammenhängenden Track zu erzeugen, dann wirst
du möglicherweise bei der Nutzung auf Probleme stossen. Die mir bekannten Geräte
haben alle Probleme beim Navigieren entlang von Tracks, welche Sackgassen bzw.
mehr als einmal vorkommende Teilstrecken enthalten. Kommt man mal vom
Trackverlauf ab, dann führen z.B. Garmin-Geräte zum nächstgelegenen Punkt des
Tracks. Das kann dann auch ein Punkt sein, an dem man bereits vorbeigekommen
ist, oder es führt zum Überspringen einer Teilstrecke.

Gruß
Rainer