Nabend, jedes Mal, wenn ich bei meiner Freundin im Auto sitze, frage ich mich, wie so ein Navigationssystem bzw. die Internet-Routenplaner funktionieren. Ich stelle mir das bildlich so vor, dass ich einen Faden zwischen den beiden Orten (Momentaner Aufenthalt und Zielort) spanne. Damit hätte ich Luftlinie. Jetzt würde ich den Faden entlang von Strassen legen, bis ich die beiden Orte miteinander verbunden habe. Ich könnte mir vorstellen, sowas mit einer Art Bildverabeitung anhand von eingescannten Landkarten zu machen. Zugegeben wäre das ein ziemliches Datenaufkommen, aber es könnte funktionieren (Strassen haben halt eine andere Farbe als Acker und Häuser. Da Speicher aber kostbar und die Bildverarbeitung relativ zeitaufwändig ist, wird es eine andere Lösung geben. Aber wie? Es muß ja eine Datenbank sein. Wie sieht die aus? Kann mir da jemand vielleicht einen Tip oder Link geben, wo darüber was finde? Da sich dieser Beitrag im Bereich "Offtopic/Sonstiges" befindet, finde ich Sachen wie "such doch bei google!" nicht wirklich angebracht. Allerdings habe ich da noch nicht geguckt, da ich eigentlich ins Bett gehen sollte... Und wenn ich erst mal Google durchforste, dann sehe ich die Sonne aufgehen. Vielleicht hat ja jemand einfach Lust, es mir so zu erklären. Wenn nicht, werde ich weiter drüber nachgrübeln und selbst suchen. Gruß Rahul
Das ganze wird meist so ähnlich wie mit dem Faden per Rekursion gemacht. Zuerst die naheliegendsten großen Straßen -> kürzeste Strecke über Autobahn und grobe Route. Dann jeweils das ganze mit Abkürzungen über kleinere Straßen verfeinern (bis zu einem best. Level). Zum Schluss nochmal drüber, sozusagen "glätten" -> voila.
hi, ich habe davon keine ahnung.. aber ohne tricks sind solche aufgaben nicht zu lösen, weil es viel zu viele möglichkeiten gibt, als das sich das jedesmal schnell berechnen ließe. auch bei deiner faden-methode musst du an jeder abzweigung entscheiden, wo's langgeht - und das könntest du nur wissen, wenn du jede möglichkeit durchprobiertest (und die nächste abzweigung, und die nächste, und ..). ein bekannter trick ist von ameisen abgekupfert, die sich mit duftstoffen mitteilen, wo es was zu futtern gibt: zwei ameisen finden gleichzeitig was zu fressen, und laufen den weg zum bau zurück, den sie gekommen sind. dabei strömen sie jetzt ihren duftstoff aus, der die anderen zur futterquelle leiten soll. die spur der ameise, die den kürzeren weg hat, kommt als erste bei ihren kollegen an, die sich wiederum sofort auf den weg machen, und den kürzesten weg noch stärker markieren. man schicke also erstmal eine virtuelle ameisenkolonie durch den virtuellen wald.. ich nehme also an, daß anstelle einer kompletten neuberechnung bestimmte, bereits ermittelte, ideale verbindungen (berlin<->köln) direkt abgespeichert werden, und für die nebenstrecken der weg mithilfe solcher tricks recht effizient berechnet werden. wie es aber wirklich gemacht wird, weiß ich nicht. vielleicht gibt es ja auf die algorithmen patente, die man zu rate ziehen kann? ach so: das straßennetz wird natürlich direkt in einer db abgelegt, wie kommst du denn auf die bilder? format der ablage? vielleicht so: tabelle straßensegmente (vektoren) straße anfang ende typ einbahnstr. hausnummeranfang hausnummerende tabelle anschlüsse 1 ende anfang 2 3 anfang anfang 2 2 ende ende 4 gute nacht
Das hat alles nix mit grafischer Bildverarbeitung etc. zu tun, sondern mit Graphentheorie. Ein Graph besteht aus Knoten und Kanten. Die Knoten sind Kreuzungen und die Kanten sind die Straßen zwischen den Kreuzungen. Die Kanten (Straßen) haben Attribute wie z.B. Entfernung und Typ (Autobahn, Feldweg) etc. Damit kennt man z.B. die benötigte Zeit zwischen zwei Kreuzungen oder die Strecke. Je nach dem ob Du nun die schnellste oder kürzeste Strecke fahren möchtest, oder möglichst viel oder möglichst wenig Autobahn etc., wird nun der optimalste Weg von Knoten zu Knoten berechnet. Dafür gibt es verschiedene Algorithmen. Details kannst Du bestimmt auch in der Wikipedia unter Graphentheorie finden. Einfach mal ein wenig suchen.
Wie ich schon vermutete, die Wikipedia ist wie immer bei solchen Dingen gut sortiert: a.) http://de.wikipedia.org/wiki/Graphentheorie b.) http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra
Vielen Dank für die freundlichen Beiträge. @Unbekannter: noch mal extra Dank für die Links, die werde ich mir nachher mal angucken. Gruß Rahul
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.