Karten-Routing, a la Google Maps?

Question

Map Routing hat mich schon immer fasziniert, aber ich habe noch nie eine gute Einführung (oder gar ein Tutorial für Fortgeschrittene!) dazu gefunden. Hat jemand irgendwelche Hinweise, Tipps, etc?

Aktualisierung: Ich suche vor allem nach Hinweisen darauf, wie ein Kartensystem implementiert ist (Datenstrukturen, Algorithmen usw.).

Answer 1

Werfen Sie einen Blick auf die Projekt der offenen Straßenkarte um zu sehen, wie diese Art von Problemen in einem wirklich freien Softwareprojekt angegangen wird, das nur von den Nutzern bereitgestellte und lizenzierte Daten verwendet, und um eine Wiki mit Informationen, die für Sie interessant sein könnten .

Vor ein paar Jahren waren die beteiligten Jungs ziemlich locker und beantworteten viele meiner Fragen, so dass ich keinen Grund sehe, warum sie nicht immer noch ein netter Haufen sind.

Answer 2

Mit Map Routing meinen Sie die Suche nach dem kürzesten Weg entlang eines Straßennetzes?

Der Dijkstra-Algorithmus für den kürzesten Weg ist der bekannteste. Wikipedia hat keine schlechte Einführung: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Hier finden Sie ein Java-Applet, mit dem Sie es in Aktion sehen können: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html und Google führen Sie zu Quellcode in nahezu jeder Sprache.

Jede reale Implementierung zur Generierung von Fahrtrouten wird eine ganze Reihe von Daten über das Straßennetz enthalten, die die mit der Überquerung von Verbindungen und Knotenpunkten verbundenen Kosten beschreiben - Straßennetzhierarchie, Durchschnittsgeschwindigkeit, Kreuzungspriorität, Verknüpfung von Ampeln, Abbiegeverbote usw.

Answer 3

A* ist eigentlich viel näher an den Algorithmen für die Produktionsabbildung. Er erfordert im Vergleich zu Dijikstras ursprünglichem Algorithmus deutlich weniger Erkundung.

Answer 4

Barry Brumitt, einer der Entwickler der Google Maps-Routenfindung, hat einen Beitrag zu diesem Thema geschrieben, der von Interesse sein könnte:

Der Weg zu einer besseren Wegfindung 11/06/2007 03:47:00 PM

Answer 5

Anstatt APIs für jeden Kartendienstanbieter zu lernen (wie Gmaps, Ymaps api), ist es gut zu lernen Mapstraction

"Mapstraction ist eine Bibliothek, die eine gemeinsame API für verschiedene Javascript Mapping-APIs bietet"

Ich würde vorschlagen, dass Sie die URL besuchen und eine allgemeine API lernen. Es gibt auch eine gute Menge von How-Tos.