mikrocontroller.net

Forum: Offtopic Funktionsweise von Routenplanern


Autor: Rahul Der trollige (rahul)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christoph Wagner (christoph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: leif (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rahul Der trollige (rahul)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.