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