Algorithmus um mit KML Datei zu navigieren

[Holger K. (holgerkraehe)]

Hallo zusammen

Ich möchte gerne auf einem Display die Richtung zu einem Wegpunkt 
anzeigen.
Die Wegpunkte stammen dabei z.B. aus einer KML Datei.
Mein aktueller Standort kommt natürlich von einem GPS Empfänger.

Nun habe ich bereits lösungen gefunden, wie ich den Winkel zwischen zwei 
Punkten berechnen kann. ebenso wie ich die Distanz dazwischen berechnen 
kann.

Nun gibt es jedoch noch das Problem, dass ich nicht weiss, ob ich den 
Punkt bereits passiert habe.

Wenn man sich eine Route auf einer Karte anklickt, so wird man ja nicht 
unendlich viele Punkte anwählen, sondern nur die wichtigsten "Eckpunkte" 
so dann sich dann eine relativ genaue Route ergeben würde.

Nun habe ich mir überlegt, wie ich denn nun feststellen kann, ob ich an 
einem Punkt bereits vorbei bin. Dazu habe ich ein einfaches Bild 
erstellt.

Gegeben sind die Punkte P1-6. Diese befinden sich in einer Datei.
Ich starte noch vor P1. Zu diesem Zeitpunkt ist es für mich mit dem 
aktuellen Wissenstand noch kein Problem, den Winkel, Distanz, Richtung 
etc. bis zu P1 zu berechnen. Nun passiere ich P1 an Punkt P7 (der blaue 
Punkt) Dieser befindet sich jedoch nicht genanu bei P1. Die frage ist 
nun, wie kann ich mathematisch feststellen, dass ich P1 bereits passiert 
habe? Bei mehr als der hälfte der Strecke zwischen P1 und P1 sollte dies 
kein Problem sein. Denn dann ist die Distanz zu P2 kleiner als jene zu 
P1. Bis zur orangen Markierung ist dies jedoch bestimmt nicht der Fall.

Eine Möglichkeit wäre, das Erreichen der Punkte innerhalb eines 
Umkreises von z.b. 10m zu prüfen. Dies würde aber die auf 10m genaue 
bestimmung der Punkte der Route voraussetzen. Ein grösserer Radius würde 
z.B. dazu führen, dass wenn man in die nähe von P2 kommt, dieser direkt 
als passiert erkannt wird und dadurch direkt zu P3 navigiert wird. Was 
dazu führt, dass man evtl. den Weg verlässt.

Ich bin mir ziemlich sicher, dass ich nicht der Erste bin, der sich über 
diese Probleme gedanken macht. Kennt jemand mögliche Lösungen oder ist 
die Methode mit dem Umkreis bereits das Mittel der Wahl?

Danke schonmal.

[HildeK (Gast)]

Holger K. schrieb:
> Die frage ist
> nun, wie kann ich mathematisch feststellen, dass ich P1 bereits passiert
> habe?

Ich habe mir darüber noch nie Gedanken gemacht, aber meine Idee wäre:

Wenn du auf den Punkt zu gehst, dann werden die Distanzen zum Punkt 
kleiner, wenn du ihn passiert hast, dann wieder größer.
Du müsstest also aus zwei GPS-Messungen die Distanzen zu P1 berechnen 
und dann vergleichen, ob sie kleiner oder größer werden.

[Holger K. (holgerkraehe)]

HildeK schrieb:
> Wenn du auf den Punkt zu gehst, dann werden die Distanzen zum Punkt
> kleiner, wenn du ihn passiert hast, dann wieder größer.

Das wäre grundsätzlich eine Lösung.
Wenn ich jedoch ein paar Meter zurück laufen, da ich was gesehen / 
vergesen habe, wird sofort der nächste Punkt aktiv.

Dass selbe Problem habe ich, wenn ich in einer Kreisbahn um den Punkt 
gehe (unbewusst natürlich)

[HildeK (Gast)]

Holger K. schrieb:
> Wenn ich jedoch ein paar Meter zurück laufen, da ich was gesehen /
> vergesen habe, wird sofort der nächste Punkt aktiv.

Dann muss man vielleicht noch weitere Px im Algo berücksichtigen und 
z.B. erst zum nächsten springen, wenn die Distanz zu dem auch kleiner 
wird, ev. mehrfach. Und ggf. die Historie der Messungen etwas komplexer 
betrachten. Stichwort Triangulation.

> Dass selbe Problem habe ich, wenn ich in einer Kreisbahn um den Punkt
> gehe (unbewusst natürlich)
Ja. Wieder eine Algo-Frage. Distanz zu Px bleibt (im Toleranzbereich) 
gleich, aber Annäherung/Entfernung zu Px+1 und auch zu Px-1 erfolgt 
wiederholt.

Wie ich schon sagte, es war nur so eine Idee, ohne je damit praktische 
Erfahrung gesammelt zu haben.

[Ich (Gast)]

Ich würde von jedem Punkt aus zum vorherigen und nachfolgenden je einen 
Vektor bilden und dann den Normalvektor.
Du erhältst um jeden Punkt dann eine Fläche, die von den Normalvektoren 
begrenzt wird (sofern der vorherige und nachfolgende Punkt nicht auf 
einer Linie liegen). Innerhalb dieser Fläche hast du noch nicht 
passiert; Der rest sollte klar sein.

Ich bin jetzt zu faul, es mal aufzumalen, aber ich denke es müßte 
funktionieren.

[Tom K. (ez81)]

Holger K. schrieb:
> sondern nur die wichtigsten "Eckpunkte"
> so dann sich dann eine relativ genaue Route ergeben würde.

Das bedeutet aber nicht, dass deine Software intern auch nur deine 
angeklickten Punkte verwenden darf.

In den nachfolgenden Bildern ist Deine geklickte Strecke in rot von 
links nach rechts geplottet (Koordinaten sind m), die Pfeile geben die 
Richtung an, in die der Algorithmus an der Position des Pfeils zeigen 
würde.

Der erste Ansatz, der immer den dichtesten Wegpunkt als Ziel wählt, ist 
in 01_dichtester.svg. Das funktioniert nicht sinnvoll.

Wenn man intern die geklickten Punkte interpoliert (hier ca. alle 10m) 
und als Ziel den nächsten interpolierten Punkt wählt, findet man 
immerhin auf dem kürzesten Weg auf die Strecke. Wenn man dort ist, weiß 
man aber nicht, in welche Richtung es weitergeht: 02_interpol.svg

Der einfachste Weg, um eine sinnvolle Richtung zu gewinnen, ist, den 
dichtesten interpolierten Punkt zu finden, von dort aus ein paar 
interpolierte Punkte (hier ca. 50m) auf der Strecke weiter zu gehen und 
diesen Punkt als Ziel zu nehmen: 03_vorhalt.svg. Damit läuft man 
immerhin schon in die richtige Richtung und wird smooth wieder auf den 
Weg geführt. Mit mehr Vorhalt läuft man eher in die Zielrichtung und 
weniger senkrecht auf den Weg zu, schneidet aber in den Ecken die Kurve.

Einen Nachteil hat die Methode in Ecken: Bei (600, 100) wäre es evtl. 
sinnvoller, gleich nach rechts zu laufen, statt erst nach oben, um den 
Weg wieder zu finden. Wenn man erst den nächsten interpolierten Punkt 
sucht und von dort aus nochmal in Wegrichtung weitersucht, und dabei als 
Kriterium nicht nur eine kurze Entfernung zum int. Punkt verwendet, 
sondern auch die Laufweite auf der Strecke berücksichtigt, kann man in 
solchen Fällen etwas abkürzen und läuft so, dass man weiter hinten auf 
die Strecke trifft. Diese Methode (zusammen mit den 50m Vorhalt) ist in 
05_vorhalt_und_entfernung.svg dargestellt. EDIT: In der Praxis würde man 
das Abkürzen zusätzlich irgendwie beschränken, um nicht z.B. von (900, 
500) direkt zum Ziel zu marschieren.

Das alles ist mathematisch nicht komplizierter als dein vorhanderner 
Algorithmus. Wenn der RAM für die interpolierten Punkte nicht reicht, 
kann man diese auch bei jeder Suche on the fly berechnen, statt ein 
vorberechnetes Array durchzugehen; wenn das ein paar Sekunden dauert, 
sollte das für ein Wander-Navi egal sein.

[Holger K. (holgerkraehe)]

Tom K. schrieb:
> Holger K. schrieb:
>> sondern nur die wichtigsten "Eckpunkte"
>> so dann sich dann eine relativ genaue Route ergeben würde.
> ...
> sollte das für ein Wander-Navi egal sein.

Vielen vielen Dank!
Sieht wirklich hervorragend aus!
Auch deine Überlegungen helfen mir sehr weiter.

Mit welchem Programm hast du die Grafiken bzw die Algorithmen erstellt?
Ich arbeite meistens mit Matlab. Ob ich dieses Problem dort ebenfalls so 
schön darstellen kann, weiss ich leider nicht.

[Tom K. (ez81)]

Holger K. schrieb:
> Mit welchem Programm hast du die Grafiken bzw die Algorithmen erstellt?
Die Algorithmen mit C++.

Zur Darstellung schreibt die C++-Konsolen-Anwendung die Koordinaten bzw. 
Koordinaten+Richtung in Textdateien, die dann mit etwas gnuplot 
geplottet werden. Wenn man das in den Buildprozess integriert, sieht man 
mit ein paar Tastendrücken sofort Ergebnisse. Für die Visualisierung 
derartiger Anwendungen funktioniert das mit wenig Aufwand sehr gut. 
Punkte und Vektorfelder sind mit Matlab wahrscheinlich noch einfacher 
darstellbar.

[Holger K. (holgerkraehe)]

Tom K. schrieb:
> Holger K. schrieb:
>> Mit welchem Programm hast du die Grafiken bzw die Algorithmen erstellt?
> Die Algorithmen mit C++.
>
> Zur Darstellung schreibt die C++-Konsolen-Anwendung die Koordinaten bzw.
> Koordinaten+Richtung in Textdateien, die dann mit etwas gnuplot
> geplottet werden. Wenn man das in den Buildprozess integriert, sieht man
> mit ein paar Tastendrücken sofort Ergebnisse. Für die Visualisierung
> derartiger Anwendungen funktioniert das mit wenig Aufwand sehr gut.
> Punkte und Vektorfelder sind mit Matlab wahrscheinlich noch einfacher
> darstellbar.

Vielen Dank für deine Antwort.
Werde ich gleich auch mal ausprobieren.