2008-08-05 9 views
18

Ich war schon immer fasziniert von Map Routing, aber ich habe noch nie eine gute Einführung (oder sogar fortgeschrittene!) Level Tutorials gefunden. Hat jemand irgendwelche Hinweise, Hinweise, etc?Map Routing, a la Google Maps?

Update: Ich suche in erster Linie nach Zeigern, wie ein Kartensystem implementiert ist (Datenstrukturen, Algorithmen usw.).

Antwort

14

Werfen Sie einen Blick auf die open street map project, um zu sehen, wie diese Art von Sache in einem wirklich freien Software-Projekt mit nur vom Benutzer bereitgestellten und lizenzierten Daten angegangen wird und eine wiki containing stuff you might find interesting haben.

Vor ein paar Jahren waren die involvierten Leute ziemlich einfach und beantworteten viele Fragen, die ich hatte, also sehe ich keinen Grund, warum sie immer noch keine nette Gruppe sind.

2

Statt APIs zu jeder Karte Service-Provider Lernen (wie Gmaps, Ymaps api) Seine gute Mapstraction

zu lernen

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

I würde vorschlagen, dass Sie zu der URL gehen und eine allgemeine API lernen. Es gibt eine gute Menge von How-Tos auch.

4

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

Dijkstra Kürzester-Pfad-Algorithmus ist der bekannteste. Wikipedia hat kein schlechtes Intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Es gibt ein Java-Applet hier, wo Sie es in Aktion sehen können: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html und Google Sie führen Sie zu Quellcode in fast jeder Sprache.

Jede echte Implementierung zum Generieren von Fahrrouten wird ziemlich viele Daten auf dem Straßennetz enthalten, die die Kosten assoziieren, die mit traversierenden Verbindungen und Knoten - Straßennetzwerkhierarchie, Durchschnittsgeschwindigkeit, Kreuzungsvorrang, Verkehrssignalverknüpfung, verbotenen Abbiegungen usw .

+1

Karten sind in der Regel zu groß, um Standard-Algorithmen für den kürzesten Pfad zuzulassen. Sie müssen einige Heuristiken erstellen, um einen Untergraphen auszuwählen. Außerdem können Sie völlig unterschiedliche, heuristische Ansätze (z. B. Autobahnen zuerst, ..) verwenden, um eine Route zu finden. –

2

ich habe noch ein gutes Tutorial auf Routing zu finden, aber es gibt viele Codes zu lesen:

Es gibt GPL-Routing-Anwendungen, die OpenStreetMap-Daten verwenden, zB Gosmore funktioniert unter Windows (+ Mobile) und Linux. Es gibt eine Reihe von interessanten [Anwendungen mit den gleichen Daten, aber gosmore hat einige coole Anwendungen e.g. interface with websites.

Das größte Problem mit dem Routing ist schlechte Daten, und Sie erhalten nie genug Daten. Also, wenn Sie es versuchen wollen, halten Sie Ihren Test sehr lokal, damit Sie die Daten besser kontrollieren können.

4

Barry Brumitt, einer der Ingenieure von Google Maps Routensuche-Funktion hat einen Kommentar zu dem Thema, das von Interesse sein könnte:

The road to better path-finding 11/06/2007 03:47:00 PM

4

A * ist den Produktions-Mapping-Algorithmen tatsächlich viel näher. Im Vergleich zu Dijikstras ursprünglichem Algorithmus erfordert es viel weniger Erforschung.

+0

Eigentlich ist das modifizierte D * das, was ich allgemein weiß. – mmcdole

2

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

Natürlich würde der Algorithmus haben einen gewissen Anteil an n^2 Wege, wenn der Abstand zunimmt n suchen. 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 erhöhen, indem Sie nicht auf einem Pfad doppelspurig verfahren, indem Sie die Routen an einem Punkt, an dem sie bereits abgedeckt wurden, nicht erneut prüfen und Pfade, die zu lange dauern, aufgeben. Ein alternativer Weg ist der Ameise-Pheromon-Ansatz, bei dem Ameisen willkürlich von einem Startpunkt aus krabbeln und eine Duftspur hinterlassen, die mehr Ameisen auf einem bestimmten Pfad aufbaut. Wenn Sie (genügend) Ameisen sowohl vom Anfangspunkt als auch von den Endpunkten senden, wird der Pfad mit dem stärksten Geruch schließlich der kürzeste sein. Dies liegt daran, dass der kürzeste Weg in einem bestimmten Zeitraum öfter besucht wurde, da die Ameisen in einem gleichmäßigen Tempo gehen.

EDIT @ Spikie

Als weitere Erklärung, wie der Teich Algorithmus zu implementieren - Strukturen Potential Daten benötigt werden hervorgehoben:

Sie benötigen die Karte als Netzwerk zu speichern. Dies ist einfach ein Satz von nodes und edges zwischen ihnen. Ein Satz von nodes bildet einen route. Eine Kante verbindet zwei Knoten (möglicherweise beide den gleichen Knoten) und hat eine cost wie distance oder time zugeordnet, um die Kante zu durchlaufen. Eine Kante kann entweder bidirektional oder unidirektional sein. Wahrscheinlich am einfachsten, nur unidirektionale Einsen zu haben und für eine Zweiwegefahrt zwischen Knoten zu verdoppeln (d. H. Eine Kante von A nach B und eine andere von B nach A).

Als Beispiel vorstellen, drei Bahnhöfe in einem Dreieck nach oben zeigend angeordnet. Es gibt auch noch drei weitere Stationen auf halbem Weg zwischen ihnen. Kanten verbinden alle benachbarten Stationen zusammen, das endgültige Diagramm wird ein umgekehrtes Dreieck haben, das innerhalb des größeren Dreiecks sitzt.

Label-Knoten von unten links beginnend, nach rechts und nach links und nach oben, wie A, B, C, D, E, F (F an der Spitze).

Es sei angenommen, die Kanten in beiden Richtungen durchlaufen werden kann. Jede Kante kostet 1 km.

Ok, so wollen wir von unten nach Route links A bis zur Bergstation F. Es gibt viele mögliche Routen, einschließlich derer, die auf sich selbst zurückgehen, zum Beispiel ABCEBDEF.

Wir haben eine Routine sagen, NextNode, die eine node akzeptiert und eine cost und ruft sich selbst für jeden Knoten, den es reisen kann.

Klar, wenn wir diese Routine laufen lassen es alle Routen schließlich entdecken werden, einschließlich solcher, die in der Länge potentiell unendlich sind (zB ABABABAB usw.). Wir stoppen dies durch Überprüfung gegen die cost. Immer wenn wir einen Knoten besuchen, der vorher 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 die vorhandenen Kosten überprüfen, und wenn wir billiger sind, aktualisieren wir den Knoten und machen weiter (rekursiv). Wenn wir teurer sind, überspringen wir den Knoten. Wenn alle Knoten übersprungen sind, verlassen wir die Routine.

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

So werden alle brauchbaren Routen überprüft, aber entscheidend sind nur die mit den geringsten Kosten. Am Ende des Prozesses hat jeder Knoten die niedrigsten Kosten, um zu diesem Knoten zu gelangen, einschließlich unseres Zielknotens.

Um die Route zu bekommen, arbeiten wir rückwärts von unserem Zielknoten. Da wir den Knoten, aus dem wir gekommen sind, zusammen mit den Kosten gespeichert haben, springen wir einfach rückwärts und bauen die Route auf. (Total) Kosten 0 - - Von Knoten Keine
Node B - Kosten 1 - von Knoten A
Knoten C - Kosten 2 - Vom Knoten B

Knoten A: Für unser Beispiel würden wir mit so etwas wie am Ende Knoten D - Kosten 1 - Von Knoten A
Knoten E - Kosten 2 - Von Knoten D/Kosten 2 - Von Knoten B (dies ist eine Ausnahme, da die Kosten gleich sind)
Knoten F - Kosten 2 - Von Knoten D

So ist der kürzeste Weg ADF.

+0

@ Jonathan bitte können Sie Detail des Stein im Teich Algorithmus geben und wie kann ich es auf einer Karte anwenden.Lass mich sagen, ich bin an einem Punkt, und ich möchte in Welligkeit herum suchen, bevor ich weiter zum nächsten äußeren Welligkeit. und dude ich weiß und 2 Jahre zu spät zur Konversation – Spikie

1

Ein anderer Gedanke kommt mir bezüglich der Kosten jedes Durchlaufs vor, würde aber die Zeit und die Verarbeitungsleistung erhöhen, die zum Berechnen benötigt werden.

Beispiel: Es gibt 3 Möglichkeiten, wie ich (wo ich lebe) von Punkt A nach B gehen kann, nach den GoogleMaps. Garmin-Einheiten bieten jeden dieser 3 Pfade in der Quickest Routenberechnung an. Nachdem ich jede dieser Routen viele Male durchlaufen und gemittelt habe (natürlich gibt es Fehler in Abhängigkeit von der Tageszeit, der Menge an Koffein usw.), denke ich, dass die Algorithmen die Anzahl der Kurven auf der Straße für eine hohe Genauigkeit berücksichtigen könnten , zgerade Straße von 1 Meile wird schneller sein als eine 1 Meile Straße mit scharfen Kurven darin. Kein praktischer Vorschlag, aber sicherlich einen, den ich verwende, um das Ergebnis meiner täglichen Fahrt zu verbessern.

1

Aus meiner Erfahrung in diesem Bereich, A * macht die Arbeit sehr gut. Es ist (wie oben erwähnt) schneller als der Dijkstra-Algorithmus, ist aber immer noch einfach genug für einen normal kompetenten Programmierer, um es zu implementieren und zu verstehen.

Der Aufbau des Streckennetzes ist der schwierigste Teil, aber das kann in eine Reihe von einfachen Schritten unterteilt werden: alle Straßen; sortiere die Punkte in Reihenfolge; mache Gruppen von identischen Punkten auf verschiedenen Straßen zu Kreuzungen (Knoten); Fügen Sie Bögen in beide Richtungen hinzu, in denen sich Knoten verbinden (oder in einer Richtung nur für eine Einbahnstraße).

Der A * -Algorithmus selbst ist well documented on Wikipedia. Der Schlüssel zur Optimierung ist die Auswahl des besten Knotens aus der offenen Liste, für den Sie eine leistungsstarke Prioritätswarteschlange benötigen. Wenn Sie C++ verwenden, können Sie den Adapter STL priority_queue verwenden.

Die Anpassung des Algorithmus zum Routen über verschiedene Teile des Netzwerks (z. B. Fußgänger, Auto, öffentliche Verkehrsmittel usw.) mit günstigen Geschwindigkeiten, Entfernungen oder anderen Kriterien ist ziemlich einfach. Sie tun dies, indem Sie Filter schreiben, um zu steuern, welche Routensegmente verfügbar sind, wann das Netzwerk aufgebaut wird und welches Gewicht jedem zugewiesen wird.