route berechnen?

[Der_Unwissende]

Zitat von Matze:

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen), sofern diese nicht zu allzu großen Umwegen führen. Dann werden kleinere Straßen berücksichtigt, wenn es beispielsweise durch Orte geht oder man in Zielnähe ist bzw. auf dem Weg zu Schnellstraßen. Natürlich müssen Einbahnstraßen berücksichtigt werden.

Hier denke ich lohnt sich eben diese Rasterung. So kann man ja leicht einen Ort oder ein Land rastern und dort für Start- und Zielpunkt den nächsten Punkt suchen. Möchte man sich z.B. nur innerhalb Berlins bewegen, wird kaum die Deutschlandkarte betrachtet. Möchte man hingegen nach München, nun ja,...
Hat man die beiden Knoten, die dieser gröbsten Granularität entsprechen, kann man weiter in Detail gehen. Im einfachsten Fall haben beide bereits den gleichen Knoten, dann ist natürlich nichts weiter zu tun. Ansonsten sucht man eben den kürzesten Weg. Verwendet man dabei gerichtete Graphen, so lassen sich solche Dinge wie die Fahrt im Kreis leicht (und effektiv) berücksichtigen. Jede Verbindung zwischen zwei Knoten hat zudem sicherlich eine Angabe der Kosten. Die dürften eben auf Autobahnen besonders günstig sein, in Verkehrsberuhigten Zonen hingegen entsprechend hoch!
Was man dann nur noch machen muss ist eben für jede Rasterung den entsprechend kürzesten Weg zu finden (z.B. die A9 für die Tour Berlin-München). Dann halt den Weg auf die A9 usw.

[Newbie44]

ja genau das is mir auch schon aufgefallen, ab und zu gibts mal kleine fehler und man wird rückwärts in eine einbahnstraße geschickt (is mir auch schon passiert)

irgendwie find ich das immer lustig wenn solche fehler passieren, nur die programmierer habens da nicht so einfach die fehler zu beheben, der algo is ja ein modifizierter A*, hab ich gerade bei google gelesen.

aber so ne detailliete beschreibung wie ich am schnellsten von A nach B komme gibt es nicht.

Map24 machts ja mit einer Java Anwendung, vielleicht kann man sich den quellcode von den mal anschauen, gibt ja java decompiler, die echt gut funktionieren.

es seid denn, jemand kennt noch ne seite, wo man einen navi algo komplett sehen kann

[leddl]

Zitat von Newbie44:

ja genau das is mir auch schon aufgefallen, ab und zu gibts mal kleine fehler und man wird rückwärts in eine einbahnstraße geschickt (is mir auch schon passiert)

Das sind im Normalfall aber keine Berechnungsfehler Das passiert, wenn dein Kartenmaterial nicht up 2 date ist oder wenn die GPS-Verbindung kurz flöten gegangen ist und das Navi dadurch durcheinandergeraten ist

[Matze]

Zitat von Newbie44:

es seid denn, jemand kennt noch ne seite, wo man einen navi algo komplett sehen kann

Ich glaube nicht, dass es da etwas in Open-Source geben wird, denn es handelt sich um hochkomplexe Algorithmen, mit denen man auch gut Geld verdienen kann. Aber vielleicht gibt's auch was.
Dir würde der Source vermutlich auch nichts nutzen, da du sicher nicht verstehen würdest, was die tausenden Zeilen Code genau machen. Eine schematische Übersicht wäre da hilfreicher, nur habe ich noch keine gefunden.

[Newbie44]

Aber es wäre echt mal sehr interessant so einen ablauf zu sehen. ich meine es gibt doch schon soviel opensource, darum wundert es mich das es sowas noch nicht gibt.

aber wenn jemand was in die richtung findet, auch ist ein Strucktugramm sehr sinnvoll

[OregonGhost]

Zitat:

Map24 machts ja mit einer Java Anwendung, vielleicht kann man sich den quellcode von den mal anschauen, gibt ja java decompiler, die echt gut funktionieren.

Ich bezweifle, dass die Java-Anwendung die kompletten Kartendaten herunterlädt, um die Routenplanung auszuführen
Das passiert serverseitig, sonst könnte man das ja in der Tat leicht stehlen.

Mir sind keine OS-Navigationsalgorithmen bekannt. Davon abgesehen brauchst du ja nicht nur den Algorithmus - detaillierte Kartendaten kosten eine Stange Geld. Das ist sicherlich auch ein Grund, weshalb es keine kostenlose Navigationssoftware gibt.

[Der_Unwissende]

Zitat von Newbie44:

Aber es wäre echt mal sehr interessant so einen ablauf zu sehen. ich meine es gibt doch schon soviel opensource, darum wundert es mich das es sowas noch nicht gibt.

Nun ja, irgendwie dürfte das komplette Kartenmaterial von einer Stadt schon recht teuer sein, von einem Land oder Europa mal ganz zu schweigen. Da mag Opensource dann schon an den Kosten scheitern. Und für den Rest gibt es ja einfache Ansätze, die man nach und nach optimieren kann. Wie gesagt, das Routing bei Netzen geht wahrscheinlich schon einen ähnlichen Weg (zumindestens sind die Anforderungen schon mal sehr sehr ähnlich!). Und dort gibt es dann natürlich auch OpenSource (da einige bekannte OS-Betriebssysteme natürlich auch ihre Stärken in Netzwerken, z.B. als Router haben).

[edit]
Roter Kasten streikt heute (in diesem Thread), wollte das mit den Karten nicht sinnlos wiederholen!
[/edit]

[Newbie44]

das mit den kartendaten wundert mich ja eben. die sind echt unheimlich teuer. scheint ne menge arbeit diese zu machen.

die 2 größten firmen die das machen (die mir jetzt einfallen) sind soweit ich weis Navteq und Teleatlas

[Der_Unwissende]

Zitat von Newbie44:

das mit den kartendaten wundert mich ja eben. die sind echt unheimlich teuer. scheint ne menge arbeit diese zu machen.

Was wundert Dich denn da?! Ich meine alle Straßen samt Richtung, zusammen mit den Angaben über die geltende Geschwindigkeiten (und natürlich auch anzahl der Spuren), dann noch zusätzlich die Verknüpfung mit den GPS-Daten. Da behaupte ich doch einfach mal, dass es allein in einer Stadt schon unheimlich anstrengend sein dürfte, für alle in D oder Europa...

[matashen]

Ich möchte hier mal einen negativen Komentar anbringen.

Positiv:
Ich finde Navis ganz gut um in einer größeren Stadt ein bestimmtes Haus zu finden. Dürfte also für Servicetechniker interessant sein !?!

Negativ:
Langstrecken über Navi fahren ist wohl der absolute Schwachsinn. Bis jetzt hab ich auch kein Navi gesehen (bei Geschäftsfahrten will meistens der Fahrer - mach ich ungern- das Navi benutzen)
das sauber geroutet hätte Bsp. Wohnort nach Nürnberg, kenn ich perfekte Route auswendig. Navi Rechnet 190km über was weis ich für Verbindungen als schnellste und wir sinds dann um 70!km kürzer und 45min schneller gefahren (ohne gegen Beschränkungen zu verstoßen - bevor da jemand was falsches denkt). Anderes Beispiel. Wollte auf ein Konzert, Kumpel mit Navi über meine Strecke ausm FF sind wir 150km gefahren Laut Navi war die Verbindung 280km und 3Std Fahrzeit - tja da waren wir dann auch etwas schneller

Wenn jemand mal so nen genialen Code entwickelt der das in perfekto kann, Hut ab. Aber derzeitiger Stand der Technik - In Stadt ja - Fernverbindung, auf keinen Fall - Da leist ich mir dann doch lieber den Satz Straßenkarten ausm Discounter für ein paar Euro.
Das zu einem Perfekten System auch ein Perfekter Kartensatz gehört versteht sich von selbst,das wird auch denke ich weiter verbessert.

Anmerkung:
Für die meisten Leute handelt es sich eh mehr um ein Prestigeobjekt. Denn wenn ich einmal die Woche zum Einkaufen fahre und täglich in der Arbeit sitze, frag ich mich wozu brauch ich dann ein Navi, für einmal im Jahr in die Alpen?. Schließlich ist ja keiner so gemein und reißt Tagsüber eine Straßenverbindung weg und verpflanzt diese an einen anderen Ort um Leute zu verwirren, und die tägliche Strecke sollte man dann doch kennen.

Gruß und viel Spaß beim zerpflücken meiner Meinung zum Thema Navi