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 _______________________________________________ Talk-de mailing list [email protected] http://lists.openstreetmap.org/listinfo/talk-de
