Algorithmus: Placemark mit (annähernd realistischer) Geschwindigkeit über Karte "fahren" lassen
Hallo zusammen,
ich hänge nun seit knapp zwei Tagen an diesem "Problem"... lasst es mich kurz umreißen, bevor ich auf den Knackpunkt zu sprechen komme:
Windows-Forms-Anwendung mit einem Karten-Control, welches Karten-Inhalte von OpenStreetMap einbindet und anzeigt (GMap.NET).
Nun möchte ich auf dieser Karte so etwas wie Routing simulieren, also mit anderen Worten möchte ich einen Placemark (das ist ein kleiner Marker auf der Karte, ein Pin wie man ihn von GoogleMaps kennt) eine bestimmte Route abfahren lassen und das auch noch mit (annähernd) realistischer Geschwindigkeit.
Als Daten habe ich eigentlich nur die Route, die als Liste von Latitude-/Longitude-Punkten (Breiten- und Längengeraden) vorliegt.
Eine Route mit nur einem Startpunkt und einem Endpunkt (ohne Richtungswechsel dazwischen) ist also schlicht eine Liste mit zwei Punkten: P1(Lat1, Lon1), P2(Lat2, Lon2).
Den Marker auf der Route "fahren zu lassen" funktioniert tadellos, nur die Geschwindigkeit ist alles andere als realistisch.
Folgenden Ansatz hatte ich:
Ich schaue mir immer nur den aktuellen Standort und den nächsten Routenpunkt an. Von diesen beiden errechne ich die Entfernung in Metern zueinander mittels
private double getDistanceInM(double lat1, double lat2, double lon1, double lon2)
{
double dy = 111.3 * (lat1 - lat2);
double dx = 111.3 * Math.Cos((lat1 + lat2) / 2 * 0.01745) * (lon1 - lon2);
return Math.Sqrt(dx*dx+dy*dy)*1000;
}
Effektiv findet dort nur der Satz des Pythagoras Anwendung. Erdrundung usw. kann ich getrost vernachlässigen, da ich für den Anfang nur über Entfernungen von ca. 1-10km rede.
Mit dieser Entfernung und der angestrebten Geschwindigkeit in m/s lasse ich nun den Marker jede Sekunde z.B. 13,8m (50 km/h = 13.88888 m/s) fahren.
Falls die 13,8m größer sind als die Entfernung vom aktuellen Standort zum nächsten Punkt, dann wird auf den nächsten Punkt "gezogen" und der "Überschuss" mit in die nächste Runde genommen.
Das ganze so lange, bis ich den letzten Punkt auf der Route erreicht habe.
Das eigentlich "Abfahren" der Route klappt wunderbar, der Marker bewegt sich astrein auf der Karte bzw. Route, nur ist die Geschwindigkeit alles andere als realistisch (meistens viel zu langsam) - nur warum?
Ist der Algorithmus an sich schon ein Denkfehler? Habe ich dort einen Implementations-Fehler, den ich einfach nur übersehe?
Hat jemand vielleicht sogar schonmal etwas in der Art realisiert und hat einen passenden Algorithmus zur Hand? Oder gibt es so etwas schon als Bibliothek und ich habe es einfach nicht gefunden?
Ich bin einfach mit meinem Latein am Ende 😉
Ein Beispiel:
Route mit exakt 100 Punkten, 70 km/h (= 19,4444444444 m/s) eingestellt.
Eigentliche Distanz zwischen Start und Ziel: ca. 2,2km.
2200(m)/19,4444444444(m/s) = 113,14s theoretisch benötigte Zeit.
In der Applikation benötigte der Marker 247s und ist auch - selbst zusammengerechnet innerhalb der Methode - 2836,5m gefahren, was eine durchschnittliche Geschwindigkeit von ca. 11,5m/s gibt - mit anderen Worten: viel zu langsam.
Die Implementation zur obigen Theorie (Methode läuft in einem eigenen Thread):
private void moveMarker()
{
/*
* hier findet ein wenig MapControl-Handling statt,
* damit alles korrekt angezeigt wird
*/
GMap.NET.PointLatLng currentPoint = this.currentLocation; //derzeitiger Standord
GMap.NET.PointLatLng nextPoint = route.Points[0]; //erster Punkt auf der Route
route.Points.RemoveAt(0);
double speed = Config.SPEED50; // angestrebte Geschwindigkeit. 13.8888888888 (m/s)
//Lat/Lon-Differenz zwischen dem aktuellen Punkt des Markers und dem nächsten Punkt auf der Route.
double difLat;
double difLon;
double nextDifM = 0.0; //Überschuss in Metern (s.O.)
double difM; //Differenz in m vom derzeitigen Standort zum nächsten Punkt auf der Route
double speedFactor = (this.getPercent(speed, difM) / 100); //Prozentwert, den der Marker von der Strecke (aktuellerPunkt -> nächsterPunkt) läuft
double newLat = 0.0, newLon = 0.0;
while (laufbedingung)
{
if (currentPoint == nextPoint)
{
//Wenn der Marker seinen nächsten Zielpunkt erreicht hat...
if (route.Points.Count > 1)
{
//... und die Route noch mehr Punkte hat, dann wird der nächste Punkt einen weiter gesetzt
nextPoint = route.Points[0];
route.Points.RemoveAt(0);
}
else
{
//ansonsten: "Sie haben ihr Ziel erreicht!"
laufbedingung = false;
break;
}
}
//Differenzen und Faktor berechnen; Erklärung der Bedeutung s.O.
difLat = (currentPoint.Lat > nextPoint.Lat ? (currentPoint.Lat - nextPoint.Lat) : (nextPoint.Lat - currentPoint.Lat));
difLon = (currentPoint.Lng > nextPoint.Lng ? (currentPoint.Lng - nextPoint.Lng) : (nextPoint.Lng - currentPoint.Lng));
difM = this.getDistanceInM(currentPoint, nextPoint) + nextDifM;
speedFactor = (this.getPercent(speed, difM) / 100);
if (difM > speed)
{
//Dies ist der Fall, wenn der Weg bis zum nächsten Punkt größer ist als der Weg, den der Marker in einem "Zug" zurücklegt
//dann werden die neuen Lat-/Lon-Werte berechnet und der Marker auf diese Position gesetzt
newLat = (currentPoint.Lat > nextPoint.Lat ? currentPoint.Lat - (speedFactor * difLat) : currentPoint.Lat + (speedFactor * difLat));
newLon = (currentPoint.Lng > nextPoint.Lng ? currentPoint.Lng - (speedFactor * difLon) : currentPoint.Lng + (speedFactor * difLon));
nextDifM = 0.0;
currentPoint = new GMap.NET.PointLatLng(newLat, newLon);
}
else
{
//Hier ist der Fall, dass der Marker mit einem Zug über den nächsten Punkt hinausschießen würde
//also wird direkt auf den nächsten Punkt gefahren...
currentPoint = nextPoint;
//und der Überschuss gespeichert
nextDifM = speed - difM;
}
/*
* Hier wird noch der Marker auf der Karte auf currenPosition gesetzt und das MapControl refreshed.
*/
}
}
Bitte nicht auf Unschönheiten im Code achten, da lässt sich bestimmt noch einiges angenehmer schreiben, aber ich möchte erstmal, dass es läuft! 😉
Hallo Sh00tingStar,
ohne dass ich denen Code näher angeschaut habe, fällt mir folgenden auf bzw. ein:
Liegen deine Winkel auch wirklich im Bogenmaß vor?
Was verstehst du unter Pixel? Die Pixel, die gefärbt sind bzw. wären, wenn man eine Linie vom Start- zum Zielpunkt zeichnet? Das sind ja in der Regel mehr oder weniger, als sich mathematisch aus dem "Pythagoras" ergibt. Oder meinst du eher mathematische Punkte?
Außerdem verstehe ich das mit dem Überschluss nicht so ganz. Warum stellst du einen Timer nicht so, dass er immer genau tickt, wenn das nächste Pixel erreicht ist?
herbivore
Hallo herbivore,
Liegen deine Winkel auch wirklich im Bogenmaß vor?
Ja, die Umrechnung in das Bogenmaß fließt in der getDistanceInM() ein (durch die Multiplikation mit 0,01745 = pi/180 rad = 1°)
Was verstehst du unter Pixel? Die Pixel, die gefärbt sind bzw. wären, wenn man eine Linie vom Start- zum Zielpunkt zeichnet? Das sind ja in der Regel mehr oder weniger, als sich mathematisch aus dem "Pythagoras" ergibt. Oder meinst du eher mathematische Punkte?
Pixel? Ich habe nirgendswo Pixel erwähnt... wäre aber aber auch ein interessanter Ansatz, dort über die gefärbten Pixel zu gehen, allerdings soll später die gefärbte Route eigentlich nicht zu sehen sein.
Theoretisch wären für mich in diesem Zusammenhang die Pixel erstmal die Pixel, die gefärbt wären.
Außerdem verstehe ich das mit dem Überschluss nicht so ganz.
Der "Überschuss" resultiert aus meinem Denkansatz:
Ich muss eine gewisse Anzahl von unterschiedlich langen, aber zusammenhängenden Linien in (absolut) gleichgroßen Schritten ablaufen um eine konstante bzw. gleichmäßige Laufgeschwindigkeit zu erzielen.
C _________ D Sei dies mal die Route
A_______/
B
Wenn ich nun bei A starte und anfange in bestimmten Schritten der Größe X zu laufen, werde ich (rein von der Theorie her) irgendwann auf das Problem stoßen, dass meine Schrittlänge größer ist als die noch verbleibende Strecke zum Punkt B.
Um nun aber meine Geschwindigkeit konstant zu halten muss ich diesen "Überschuss" (also die Strecke Schrittlänge minus verbleibende Strecke zum Punkt B) mit auf die nächste Strecke nehmen.
Also laufe ich direkt zum Punkt B und laufe auf der Strecke B - C noch den Überschuss ab.
Warum stellst du einen Timer nicht so, dass er immer genau tickt, wenn das nächste Pixel erreicht ist?
Timer ist auch ein interessantes Stichwort, hab noch keinen Ansatz mit einem Timer versucht.
Hallo Sh00tingStar,
wo fließt denn überhaupt die Zeit in deiner Methode ein?
Also wie synchronisierst du deinen Algorithmus mit der aktuellen Zeit - bisher sehe ich nur deine kontinuierlich laufende while-Schleife.
Hallo Th69,
hoppala!
Du hast natürlich Recht, dass ich die Zeit unterschlagen habe!
Die ganze Methode ist deutlich länger durch das Handling des Map-Controls, da hab ich wohl beim Kopieren&Einfügen eine Zeile wegrationalisiert 😁
Für den Anfang (und um mir weitere Umrechnungen zu sparen) habe ich direkt als erstes in der while-Schleife den Thread 1s warten lassen (und ich bin mir bewusst, dass das nicht die eleganteste Art ist 😉):
while (laufbedingung)
{
Thread.Sleep(1000);
if (currentPoint == nextPoint)
{
//und so weiter
Hatte da auch noch gar nicht an Timer gedacht... denke ich werde den Algorithmus dann in das Tick-Event vom Timer umbasteln.
Hallo Sh00tingStar,
ja dann ist ja klar, warum deine Methode langsamer ist.
Alleine durch das Aktualisieren der Map wird deine Methode ja einige Millisekunden benötigen.
Du mußt die Zeit berechnen, die deine Methode benötigt (z.B. mittels der Stopwatch-Klasse) und dann die Differenz zu 1 Sekunde nur noch warten.
Edit: auch beim Umstellen auf den Timer mußt du meine obige Methode benutzen...
Irgendwie hatte ich mit sowas gerechnet... ich melde mich, wenn ich es ausprobiert habe! 🙂
Danke erstmal für die Tipps, herbivore und Th69
Edit: auch beim Umstellen auf den Timer mußt du meine obige Methode benutzen...
Das kommt auf den Timer an. Ein System.Threading.Timer z. B. kann sich auch selbst "überholen", wenn eine Ausführung zu lang dauert.
An sich ist es auch bei Timern natürlich eine Frage der Genauigkeit der Timer. Man kann ja mal per StopWatch das Intervall überprüfen. Nicht zuletzt kann das abhängig vom Rechner sein.
Am besten fährt man wahrscheinlich mit dem Multimediatimer, für den es aber keine .Net-Entsprechung gibt, jedoch einen Wrapper auf Codeproject. Ansonsten wäre auch eine gute Alternative, per StopWatch oder DateTime.Now.Ticks die tatsächlich vergangene Zeit zu ermitteln und korrekt in die Rechnung einzubeziehen. Damit wären es also bspw. nicht 13.8m, sondern 13.7 oder 13.9 (was sicherlich der Darstellung keinen Abbruch tut, aber die Genauigkeit verbessert).
Damit wären es also bspw. nicht 13.8m, sondern 13.7 oder 13.9 (was sicherlich der Darstellung keinen Abbruch tut, aber die Genauigkeit verbessert).
Wenn man diese Ungenauigkeit mal auf 5km aufsummiert könnte das sogar rein vom Gefühl her hinkommen!
Ganz spontan wollte ich auch erstmal über die Ticks gehen, vllt noch über die Millisekunden.
(Edit: [ vergessen 😉 )
Okay... habs jetzt mit Stopwatch bzw. Timer versucht.
Ergebnis sieht definitiv besser aus! Danke für die wertvollen Tipps!
Werde, sobald ich Zeit finde, mal den "fertigen" Algorithmus posten (falls jmd etwas ähnliches vorhat).
Hallo,
while (laufbedingung) { Thread.Sleep(1000); if (currentPoint == nextPoint) { //und so weiterHatte da auch noch gar nicht an Timer gedacht... denke ich werde den Algorithmus dann in das Tick-Event vom Timer umbasteln.
Das Thread.Sleep(1000) + Zeit für die Ausführung mehr Zeit als 1s benötigt wurde schon erläutert. Aber dennoch eine kleine Anmerkung hierzu.
Thread.Sleep (x) verwendet wie die StopWatch die Timmings von der WinAPI. Somit sind diese auch von der Auflösung dieser Timmings abhängig. Daher sollte man niemals so etwas nacheinander summieren.
Besser ist etwas in Richtung
timestamp = now
while ( )
{
newTimestamp = now
deltaTime = newTimestamp - timestamp
timestamp = newTimestamp
berechne alle Aktionen für "timestamp"
// zur Minimierung der CPU-Auslastung
Thread.Sleep (0) // oder ähnliches
}
Der große Vorteil dieser Methode, man ist unabhängig von der Dauer eines Schleifendurchlaufes. Evtl. kann man am Ende auch einen FPS-Minimierung (FPS = FramesPerSeconds) betreiben. Aber bedenke, einen festen Wert, wie z.B. 60 FPS, wirst du nie hinbekommen. Nur eine Näherung.
Solltest du immer noch Probleme mit der Geschwindigkeit haben, solltest du dir über Beschleunigungsmöglichkeiten für die Berechnungen überlegen. Schaue dir mal mit einem Profiler an, wo du viel Zeit verlierst.
z.B.
- man muss nicht immer cos, sin, tan exakt berechnen, für Spezialfälle z.B. kleiner Winkel reichen auch Näherungen
- Wieso rechnest du in jeder Schleife Grad und Rad um? Das ist doch sinnlos. Nimm das, was du benötigst. Also Rad 😉
Gruß, Thomas