Algorithmus für Track-Analyse (Roadbook)

[DelphiFan2008]

Hallo,

Wende mich mit einer Frage zu einem Algorithmus an euch.

Ich habe vor einiger Zeit eine Applikation für die Erstellung eines „Roadbook“ erstellt, momentan im wesentlichen eine Liste aus Orten und interessanten Punkten (wie Pässe, Seen, Schlösser etc.) entlang einer Strecke mit zusätzlichen Angaben wie Abstand vom Startpunkt, Abstand zur Strecke, Höhenangaben.
Basis dafür ein GPS-Track, sprich die Wegpunkte entlang der Strecke liegen als x,y-Koordinate (geographische Länge, geographische Breite) vor. Meist wurde hier schein ein Optimierungsschritt durch das aufzeichnende Gerät oder die SW eines Routenplaneres auf dem PC verwendet (Stichwort Douglas Peucker Algorithmus) – Erste Schwierigkeit: Keine Äquidistanter Abstand der Punkte.

Die Liste der Orte/Punkte liegen ebenfalls als x,y-Koordinate (geographische Länge, geographische Breite) mit Zusatzdaten vor.

Der erste Anwendungszweck war ein „Roadbook“ für eine Stecke nach Skizze 1. Mein Algorithmus arbeitet folgendermaßen. Nehme die Wegpunkte entlang des Track. Bestimme einen Fangradius „f“ um den aktuellen Wegpunkt in nehme temporär den aktuell gefunden Ort/Punkt innerhalb des Fangradius in eine Liste auf. Bestimme den Abstand a. Liegt der Ort/Punkt beim nächsten Wegpunkt näher als beim vorherigen, dann ändere der Abstand  kein neues hinzufügen. Steigt der Abstand a wieder, dann nimm den kürzesten in die endgültige Liste auf.

Algorithmus hat gut für Strecken des Typ 1 funktioniert. Jetzt hatte ich das Programm wieder ausgegraben und wollte es auf aktuell geplante Strecken/Tracks anwenden, welche nicht mehr dem Typ 1 entsprechen.

• Kreuzung
• Abstand Track zu Track kleiner Fangradius
• Start/Ende gleicher Punkt
• Parallel geführte Strecke bzw. gleiche Strecke hin- und zurück

Schon scheitert der einfache Algorithmus. Anfänglich hatte ich mit etlichen if/else … versucht die Sonderfälle zu unterscheiden, wird aber langsam unübersichtlich, da aus dem einfachen Algorithmus viele Algorithmen werden die nicht so recht zusammenpassen.

Hat jemand eine Idee für einen schlanken „allgemeingültigen Ansatz“.

Habe auf den Skizze versucht die Sonderfälle und die Grundlegende Idee zu beschreiben.

LG DelphiFan2008

[himitsu]

Du berechnest den Abstand aller Zielpunkte zu allen Wegpunken, oder zu der Geraden zwischen zwei Punkten, falls die Wegpunkte weiter auseinanderliegen.

Und dann nimmst du einfach für jeden Zielpunkt den Wegpunkt mit dem geringsten Abstand.
Bei gleichen Abständen z.B. den Ersten, einen zuälligen oder den, wo mehr/weniger andere Zielpunkte in der ähe des gewünschten wegpunktes liegen .... jenachdem wie das dann verteilt sein soll.

[Aphton]

Ich habe dein Anliegen nicht ganz verstanden.

Willst du von allen Orten, die in der Nähe (Distanz <= maximale Distanz [=Fangradius]) deiner Strecke ist, den nahesten Wegpunkt auf deiner Strecke bestimmen?

Falls ja, dann sollte das ganz einfach sein

Code:

- Iteriere über alle Wegpunkte (aktueller Wegpunkt = i)
-- erstelle eine Liste aller Orte, die in der Nähe (Nähe = Distanz <= Fangradius) vom Wegpunkt i sind (Liste = l)
-- iteriere alle Orte in der Liste l und update die Distanz, sofern die neue Distanz (vom aktuellen Wegpunkt i zu diesem Ort) kleiner ist

Dein Algorithmus hätte genau hier den Fehler

Zitat:

Bestimme den Abstand a. Liegt der Ort/Punkt beim nächsten Wegpunkt näher als beim vorherigen, dann ändere der Abstand kein neues hinzufügen

Das ist logisch nicht ganz korrekt!
Hier berücksichtigst du nur benachbarte Wegpunkte (nächster Wegpunkt). Es sollte aber global gültig sein (alle Wegpunkte)!

[Namenloser]

So wie Aphton würde ich das auch machen.

Ich hatte aber echt Schwierigkeiten, deinen (DelphiFan2008) Algorithmus zu verstehen, weil deine Beschreibung grammatikalisch irgendwie durcheinander ist. Hättest du vielleicht vor dem Abschicken noch mal drüberlesen sollen... (nebenbei: Es heißt „Nimm“, nicht „Nehme“)

Dass die Punkte nicht äquidistant sind, ist eigentlich kein Problem. Lege einfach eine Schrittweite fest und dann interpoliere einfach die Strecke zwischen zwei Punkten, wenn sie zu lang ist. Oder wandele Aphtons Algorithmus so ab, dass du über die Segmente iterierst statt über die Punkte (und dann eben auch den Abstand zum Segment berechnest statt zum Punkt). Aber ich glaube, die Punkte zu interpolieren, wäre einfacher und für den Anwendungszweck genau so gut.

[DelphiFan2008]

Doppelt

[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

[Graberius]

Zitat von DelphiFan2008:

Hallo,


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

Da hasst du dir ja was Vorgenommen
Ich hoffe ich kann dir ein bisschen helfen obwohl uff, das ist ein grosses Projekt.
Du hast ja diese Liste mit Ausnahmebehandlungen.
Das wichtigste ist das du eventuell anhand von Geografischen gegebenheiten wie

• Bevölkerungsdichte
• Strassennetzdichte
• Geografische Lage (Unterland, Gebierge, Hochgebierge,....)
• Bereits bekannte Orte

eine grobe Vorsortierung machst.
Ebenfalls könntest du eine Art erinnerung Programmieren die sagen wir mal ein Dreieck alle 5km oder
so "Zeichnet" und nach bereits bekannten Punkten sucht, anhand von diesem Wissen kannst du dann deinen Fangradius erweitern.
Nun kannst du mehrere Algorythmen in Abhängigkeit dieser Filterungen erstellen.
Wenn du eine Strecke doppelt befahrst, einmal hin und dann wieder zurück, kannst du die Werte +- aus der
vorangegangenen Fahrt wiederverwenden.
Komplexer wird es wenn du die vorangegangene Route Kreuzt, da wäre ein Algorythmus der dir aus jeder zur Verfügung stehenden
möglichen Route innerhalb eines Radius (dieser Radius umschliesst Tangential die Routenradien die aus den möglichen Routen bestehen),
die Tracks schon Vorberechnet. Diese können dann beim befahren der Strecke erweitert werden.
Du könntest natürlich auch den Fangradius vergrössern sobald du eine Rooute Kreuzt und zwar um aus einem Fanktor der aus der Anzahl
möglichen Routen oder Kreuzungen besteht.

Puhh jetzt aber mal genug Geschrieben.
Hoffe das hilft dir weiter und viel Spass noch beim Coden