Algorithmus für Track-Analyse (Roadbook)

[DelphiFan2008]

Hallo,

das mit dem Durchlesen ist durchaus richtig - habe wohl Sonntagmorgen einen ganz schönen Stuss geschrieben

Jedoch dachte ich, dass das angehängte Bild ein wenig hilft.

Das ganze Vorhaben dient einer Steckenplanung für Fahrrad/Motorrad/Pkw. Die gewünschte Strecke liegt als GPS-Datei (GPX-Format) vor. Nun soll zusätzlich mittels der GPS-Daten und einer Datenbank, in der alle Orte/Städte und weitere interessante Punkte (Seen, Schlösser, Tunnels, Pässe etc.) vorhanden sind, ein „Roadbook“ erstellt werden.

Roadbook bedeutet: Liste mit den Orten/Städten auf/an der Strecke mit Abstand vom Start, Höhe des Ortes, evtl. Abstand vom Track -> Wenn man die Strecke nun z.B. mit dem Rad abfährt, befindet sich das Roadbook in der Trikottasche und man kann schnell einen Blick darauf werfen, ob etwas interessantes in der Nähe ist oder auch nur zur Orientierung.

Zusätzlich kommt auf das Roadbook eine Grafik des Streckenprofil mit den Achsen Höhe/Entfernung und Basisdaten - Steckenlänge/Höhenmeter etc.

Hier ein „Roadbook“ - nur Liste der Orte - aus meiner ersten Applikation

Delphi-Quellcode:

...
(3) Untervaz / 549hm / 9,8km
(4) Trimmis  / 640hm / 14,7km
(5) Chur  / 631hm / 22,6km
(6) Churwalden  / 1391hm / 30,0km
(7) [Pass:Lenzerheidepass / 1547hm / 35,6km]
...

Daten-Ausgangslage:

• GPS-Track mit ca. 1.500..5.000 Wertepaaren
• Orts/Punkte Liste mit ca. 180.000 Einträgen

Eine deutliche Reduzierung der Ort/Punkte Wertepaare erreiche ich indem ich die maximalen Koordinaten (xmin,ymin) und (xmax,ymax) des GPS-Track ermittle und mir nur die Orte/Punkte innerhalb des Rechtecks merke. Bleiben ca. 500..2.000 Ort/Punkte Wertepaare übrig.

• GPS-Track mit ca. 1.500..5.000 Wertepaaren
• Gefilterte Orts/Punkte Liste mit ca. 500..2.000 Einträgen

Ziel ist es nun Orte und interessante Punkte (aus den Ort/Punkt Wertepaare) entlang einer Strecke zu ermitteln, welche auf dem Track oder nahe am Track liegen.
Ich denke das Vorhaben sieht auf den ersten Blick trivial aus - bei genauer Betrachtung gibt es doch so manchen Sonderfall und in bin mir noch nicht ganz sicher wie ich den Algorithmus angehe.

Bei einer direkten Strecke von A nach B und einer durchschnittlichen „Ortsdichte“ und dem entsprechend angepassten Fangradius passt mein vorhandener Algorithmus. Schwieriger wird es wenn:

• Start/Ende an gleichem Punkt
• Strecke kreuzt (mehrfach)
• Stecke wird parallel in eine Richtung doppelt/mehrfach gefahren
• Stecke wird parallel in gegengesetzte Richtung doppelt/mehrfach gefahren
• Große Städte sind reduziert auf eine Koordinate -> Fangradius zu klein, Stadt fehlt
• Fangradius zu groß bei hoher Ortsdichte -> zu viele Orte die nicht durchfahren werden
• Fangradius zu klein bei geringer Ortsdichte z.B. Alpen -> zu wenig Orte an der Strecke

Momentan habe ich nur den Ansatz von „Strecke A nach B“ umgesetzt. Hier durchlaufe ich das Track-Array und vergleiche für jeden Trackpunkt den Abstand zu jedem Ort der gefilterten Orts-Liste. Liegt dieser im Fangradius, so wird der Ort einmalig in einer weiteren Liste abgelegt. Gleichzeitig wird der geringste Abstand Ort/Trackpunkt ermittelt und das Minimum dann dem Ortspunkt in der weiteren Liste zugeordnet.

Gefühlt wird ein „vollautomatische“ Algorithmus nicht funktionieren. Beispiel: Strecke streift den Bodensee, Koordinaten liegen aufgrund der Größe nicht im Fangradius -> manuelle Zuordnung wahrscheinlich notwendig.

Hoffe dass die Beschreibung dieses mal etwas klarer ist

[Edit] Das ganze kann dann so aussehen, siehe Bild im Anhang

Gruß DelphiFan2008