Kartenrouting, a la Google Maps?

Translate

Ich war schon immer von Map Routing fasziniert, aber ich habe nie gute Einführungs- (oder sogar fortgeschrittene!) Tutorials gefunden. Hat jemand irgendwelche Hinweise, Hinweise usw.?

Aktualisieren:Ich suche hauptsächlich nach Hinweisen, wie ein Kartensystem implementiert wird (Datenstrukturen, Algorithmen usw.).

This question and all comments follow the "Attribution Required."

Alle Antworten

Translate

Schauen Sie sich das anoffenes Straßenkartenprojektum zu sehen, wie solche Dinge in einem wirklich freien Softwareprojekt angegangen werden, bei dem nur vom Benutzer bereitgestellte und lizenzierte Daten verwendet werden und über eine solche verfügenWiki mit Dingen, die Sie vielleicht interessant finden.

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

Quelle
Translate

Barry Brumitt, einer der Ingenieure der Routenfindungsfunktion von Google Maps, hat einen Beitrag zu diesem Thema verfasst, der möglicherweise von Interesse ist:

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

Quelle
Translate

A * ist tatsächlich viel näher an Produktionsmapping-Algorithmen. Im Vergleich zum ursprünglichen Algorithmus von Dijikstra ist weniger Erkundung erforderlich.

Quelle
Translate

Mit Kartenrouting meinen Sie, den kürzesten Weg entlang eines Straßennetzes zu finden?

Der Dijkstra-Algorithmus für kürzeste Wege ist der bekannteste. Wikipedia hat kein schlechtes Intro:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

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

Jede echte Implementierung zum Generieren von Fahrrouten enthält eine ganze Reihe von Daten im Straßennetz, die die Kosten beschreiben, die mit dem Überqueren von Verbindungen und Knoten verbunden sind - Straßennetzhierarchie, Durchschnittsgeschwindigkeit, Kreuzungspriorität, Verkehrssignalverbindung, verbotene Abbiegungen usw.

Quelle
Translate

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

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

Ich würde vorschlagen, dass Sie zur URL gehen und eine allgemeine API lernen. Es gibt auch eine gute Menge an How-Tos.

Quelle
Translate

Ich habe noch kein gutes Tutorial zum Routing gefunden, aber es gibt viel Code zu lesen:

Es gibt GPL-Routing-Anwendungen, die Openstreetmap-Daten verwenden, zGosmoreDas funktioniert unter Windows (+ Mobile) und Linux. Es gibt eine Reihe interessanter [Anwendungen, die dieselben Daten verwenden, aber Gosmore hat einige coole VerwendungsmöglichkeitenzB Schnittstelle zu Websites.

Das größte Problem beim Routing sind schlechte Daten, und Sie erhalten nie gut genug Daten. Wenn Sie es also versuchen möchten, halten Sie Ihren Test sehr lokal, damit Sie die Daten besser kontrollieren können.

Quelle
Translate

Stellen Sie sich aus konzeptioneller Sicht vor, Sie lassen einen Stein in einen Teich fallen und beobachten die Wellen. Die Routen würden den Teich und den Stein als Ihre Ausgangsposition darstellen.

Natürlich müsste der Algorithmus einen Teil von n ^ 2 Pfaden suchen, wenn der Abstand n zunimmt. Sie würden Ihre Startposition einnehmen und alle verfügbaren Pfade von diesem Punkt aus überprüfen. Rufen Sie dann rekursiv die Punkte am Ende dieser Pfade auf und so weiter.

Sie können die Leistung steigern, indem Sie einen Pfad nicht doppelt sichern, indem Sie die Routen an einem Punkt, an dem sie bereits zurückgelegt wurden, nicht erneut überprüfen und auf zu lange Pfade verzichten.

Eine alternative Möglichkeit ist die Verwendung des Ameisenpheromon-Ansatzes, bei dem Ameisen zufällig von einem Startpunkt aus kriechen und eine Duftspur hinterlassen, die sich aufbaut, je mehr Ameisen einen bestimmten Pfad überqueren. Wenn Sie (genug) Ameisen sowohl vom Startpunkt als auch vom Endpunkt senden, ist der Weg mit dem stärksten Geruch möglicherweise der kürzeste. Dies liegt daran, dass der kürzeste Weg in einem bestimmten Zeitraum mehrmals besucht wurde, da die Ameisen in einem gleichmäßigen Tempo laufen.

EDIT @ Spikie

Als weitere Erklärung zur Implementierung des Teichalgorithmus werden mögliche Datenstrukturen hervorgehoben:

Sie müssen die Karte als Netzwerk speichern. Dies ist einfach eine Reihe vonnodesundedgeszwischen ihnen. Eine Menge vonnodesaroute. Eine Kante verbindet zwei Knoten (möglicherweise beide denselben Knoten) und hat einen zugeordneten Knotencostsowiedistanceodertimedie Kante überqueren. Eine Kante kann entweder bidirektional oder unidirektional sein. Wahrscheinlich am einfachsten, nur unidirektionale zu haben und sich für eine bidirektionale Bewegung zwischen Knoten zu verdoppeln (dh eine Kante von A nach B und eine andere für B nach A).

Stellen Sie sich zum Beispiel drei Bahnhöfe vor, die in einem gleichseitigen Dreieck nach oben angeordnet sind. Es gibt auch drei weitere Stationen auf halber Strecke zwischen ihnen. Kanten verbinden alle benachbarten Stationen miteinander. Das endgültige Diagramm enthält ein umgekehrtes Dreieck innerhalb des größeren Dreiecks.

Beschriften Sie die Knoten von links unten nach links nach rechts und oben als A, B, C, D, E, F (F oben).

Angenommen, die Kanten können in beide Richtungen durchlaufen werden. Jede Kante kostet 1 km.

Ok, also möchten wir von links unten A zur oberen Station F routen. Es gibt viele mögliche Routen, einschließlich solcher, die sich auf sich selbst verdoppeln, z. B. ABCEBDEF.

Wir haben eine Routine zu sagen,NextNode, das akzeptiert anodeund eincostund ruft sich für jeden Knoten auf, zu dem er reisen kann.

Wenn wir diese Routine laufen lassen, werden schließlich alle Routen erkannt, einschließlich solcher, die möglicherweise unendlich lang sind (z. B. ABABABAB usw.). Wir verhindern dies, indem wir uns mit dem vergleichencost. Immer wenn wir einen Knoten besuchen, der zuvor noch nicht besucht wurde, setzen wir sowohl die Kosten als auch den Knoten, von dem wir gekommen sind, gegen diesen Knoten. Wenn ein Knoten besucht wurde, bevor wir ihn mit den vorhandenen Kosten vergleichen, und wenn wir billiger sind, aktualisieren wir den Knoten und fahren fort (rekursiv). Wenn wir teurer sind, überspringen wir den Knoten. Wenn alle Knoten übersprungen werden, verlassen wir die Routine.

Wenn wir unseren Zielknoten erreichen, verlassen wir auch die Routine.

Auf diese Weise werden alle realisierbaren Routen überprüft, vor allem aber nur die mit den niedrigsten Kosten. Am Ende des Prozesses hat jeder Knoten die niedrigsten Kosten für den Zugang zu diesem Knoten, einschließlich unseres Zielknotens.

Um die Route zu erhalten, arbeiten wir von unserem Zielknoten aus rückwärts. Da wir den Knoten, von dem wir kamen, zusammen mit den Kosten gespeichert haben, springen wir einfach rückwärts und bauen die Route auf. Für unser Beispiel würden wir am Ende so etwas wie:

Knoten A - (Gesamt-) Kosten 0 - Ab Knoten Keine
Knoten B - Kosten 1 - Von Knoten A.
Knoten C - Kosten 2 - Von Knoten B.
Knoten D - Kosten 1 - Von Knoten A.
Knoten E - Kosten 2 - Ab Knoten D / Kosten 2 - Ab Knoten B (dies ist eine Ausnahme, da die Kosten gleich sind)
Knoten F - Kosten 2 - Von Knoten D.

Der kürzeste Weg ist also ADF.

Quelle
Translate

Aufgrund meiner Erfahrung in diesem Bereich macht A * die Arbeit sehr gut. Es ist (wie oben erwähnt) schneller als der Dijkstra-Algorithmus, aber dennoch einfach genug, damit ein normalerweise kompetenter Programmierer es implementieren und verstehen kann.

Der Aufbau des Streckennetzes ist der schwierigste Teil, der jedoch in eine Reihe einfacher Schritte unterteilt werden kann: Holen Sie sich alle Straßen; sortiere die Punkte in der Reihenfolge; Gruppen identischer Punkte auf verschiedenen Straßen zu Kreuzungen (Knoten) machen; Fügen Sie Bögen in beide Richtungen hinzu, in denen Knoten verbunden sind (oder in eine Richtung nur für eine Einbahnstraße).

Der A * -Algorithmus selbst istgut dokumentiert auf Wikipedia. Der Schlüsselpunkt für die Optimierung ist die Auswahl des besten Knotens aus der offenen Liste, für den Sie eine Warteschlange mit hoher Leistungspriorität benötigen. Wenn Sie C ++ verwenden, können Sie den STL-Adapter für die Prioritätswarteschlange verwenden.

Das Anpassen des Algorithmus für die Route über verschiedene Teile des Netzwerks (z. B. Fußgänger, Auto, öffentliche Verkehrsmittel usw.) nach Geschwindigkeit, Entfernung oder anderen Kriterien ist recht einfach. Dazu schreiben Sie Filter, um zu steuern, welche Routensegmente beim Aufbau des Netzwerks verfügbar sind und welche Gewichtung jedem zugewiesen ist.

Quelle
Translate

Ein anderer Gedanke kommt mir in Bezug auf die Kosten jeder Durchquerung in den Sinn, würde aber die für die Berechnung erforderliche Zeit und Rechenleistung erhöhen.

Beispiel:Laut GoogleMaps gibt es drei Möglichkeiten, wie ich (wo ich wohne) von Punkt A nach B gelangen kann. Garmin-Einheiten bieten jeden dieser 3 Pfade in derQuickestRoutenberechnung. Nach mehrmaligem Durchlaufen jeder dieser Routen und Mittelwertbildung (offensichtlich treten je nach Tageszeit, Koffeinmenge usw. Fehler auf) können die Algorithmen meines Erachtens die Anzahl der Kurven auf der Straße berücksichtigen, um ein hohes Maß an Genauigkeit zu erzielen ,z.B Eine gerade Straße von 1 Meile ist schneller als eine 1 Meile Straße mit scharfen Kurven. Kein praktischer Vorschlag, aber sicherlich einer, mit dem ich die Ergebnisse meines täglichen Arbeitswegs verbessern kann.

Quelle