Karte Routenplaner, a la Google Maps?

stimmen
19

Ich habe immer von Map Routing fasziniert, aber ich habe festgestellt, nie eine gute einführende (oder auch Fortgeschrittene!) Ebene Tutorials auf sie. Hat jemand irgendwelche Hinweise, Hinweise, etc?

Aktualisieren: Ich suche in erster Linie für Hinweise , wie ein Kartensystem implementiert ist (Datenstrukturen, Algorithmen, etc.).

Veröffentlicht am 05/08/2008 um 21:24
quelle vom benutzer
In anderen Sprachen...                            


9 antworten

stimmen
14

Werfen Sie einen Blick auf der Open Street Map - Projekt zu sehen , wie diese Art der Sache ist in einem wirklich freien Software - Projekt in Angriff genommen werden , indem nur Benutzer geliefert und lizenzierten Daten und haben ein Wiki Sache enthält , die Sie interessant finden könnten .

Vor ein paar Jahren die Jungs beteiligt, wo ziemlich einfach viele Fragen gehen und beantwortet hatte ich so sehe ich keinen Grund, warum sie immer noch nicht ein netter Haufen sind.

Beantwortet am 05/08/2008 um 21:27
quelle vom benutzer

stimmen
4

A * ist eigentlich viel näher an der Produktion Mapping-Algorithmen. Es erfordert ziemlich viel weniger Exploration im Vergleich zu Dijikstra ursprünglichen Algorithmus.

Beantwortet am 25/09/2008 um 00:19
quelle vom benutzer

stimmen
4

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

Der Weg zu einem besseren Weg zu finden , 11.06.2007 03.47.00

Beantwortet am 17/09/2008 um 09:44
quelle vom benutzer

stimmen
4

Durch die Karte Routing, mean finden Sie den kürzesten Weg entlang einer Straßennetz?

Dijkstra Shortest-Path - Algorithmus ist die bekannteste. Wikipedia hat kein schlechtes Intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Es ist 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 Quellcode in fast jedem Sprache.

Jede wirkliche Implementierung zur Erzeugung von Fahrtrouten beinhaltet einiges an Daten auf dem Straßennetz, das die Kosten assoziieren mit durchqueren Verbindungen und Knoten-Straßennetz Hierarchie, Durchschnittsgeschwindigkeit beschreibt, Schnitt Priorität, Verkehrssignalverknüpfung, verboten Wendungen usw.

Beantwortet am 15/08/2008 um 05:31
quelle vom benutzer

stimmen
2

Aus konzeptioneller Sicht vorstellen, einen Stein in einen Teich fallen und die Wellen zu beobachten. Die Routen würden den Teich stellen und den Stein Ihre Ausgangsposition.

Natürlich würde der Algorithmus haben einen gewissen Anteil an n ^ 2 Wege, wenn der Abstand zunimmt n suchen. Sie würden Sie die Ausgangsposition nehmen und überprüfen Sie alle verfügbaren Pfade von diesem Punkt aus. Dann ruft rekursiv für die Punkte am Ende dieser Wege und so weiter.

Sie können die Leistung, indem sie nicht doppelt Unterstützung auf dem Weg erhöhen, indem sie nicht an einem Punkt die Routen neu zu überprüfen, ob es bereits behandelt wurde und durch auf Wegen Aufgeben, die zu lang einnehmen.

Eine alternative Möglichkeit ist die Ameise Pheromon Ansatz zu verwenden, wo Ameisen zufällig von einem Startpunkt kriechen und eine Duftspur hinterlassen, die das mehr Ameisen überqueren um einen bestimmten Pfad aufbaut. Wenn Sie (genug) Ameisen senden sowohl vom Startpunkt und den Endpunkten dann schließlich der Weg mit dem stärksten Duft wird die kürzeste sein. Dies liegt daran, der kürzeste Weg mehrmals in einer gegebenen Zeitspanne besucht wurde, werden, 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 verlassen nun die Karte als Netzwerk speichern müssen. Dies ist einfach eine Reihe von nodesund edgeszwischen ihnen. Ein Satz nodesbilden ein route. Eine Kante verbindet zwei Knoten (beide möglicherweise derselbe Knoten) und hat ein zugehöriges costwie distanceoder timeden Rand zu verfahren. Eine Kante kann entweder entweder bidirektional oder unidirektional. Wahrscheinlich einfachste nur unidirektional Einsen und verdoppeln für Zweiweg Reise zwischen den Knoten (dh einer Kante von A nach B und einem anderen für B zu A).

Als Beispiel vorstellen, drei Bahnhöfe in einem Dreieck nach oben zeigend angeordnet. Darüber hinaus gibt es drei weitere Stationen, die jeweils auf halber Strecke zwischen ihnen. Kanten kommen alle benachbarten Stationen zusammen, wird das letzte Diagramm, das ein umgekehrtes Dreieck innerhalb des größeren Dreiecks sitzen hat.

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

Es sei angenommen, die Kanten in beiden Richtungen durchlaufen werden können. Jede Kante hat eine Gebühr von 1 km.

Ok, so wollen wir den Weg vom links unten zum oberen Station F. viele mögliche Routen gibt es auch solche, die auf sich selbst zurückgehen, zB ABCEBDEF.

Wir haben eine Routine sagen wir NextNode, die eine übernimmt nodeund ein costund nennt sich für jeden Knoten um es zu reisen.

Klar , wenn wir diese Routine laufen lassen wird es entdeckt schließlich alle Routen, darunter auch solche , die potenziell unendlich lang sind (zB ABABABAB usw.). Wir halten dies geschieht , indem er gegen die Kontrolle cost. Jedes Mal , wenn wir einen Knoten besuchen , die vorher noch nicht besucht hat, haben wir sowohl die Kosten als auch die Knoten wir gegen diesen Knoten kam. Wenn ein Knoten besucht wurde , bevor wir gegen die bestehenden Kosten überprüfen und wenn wir billiger sind , dann aktualisieren wir den Knoten und weitermachen (Rekursion). Wenn wir teurer sind, dann überspringen wir den Knoten. Wenn alle Knoten übersprungen werden , dann verlassen wir die Routine.

Wenn wir unsere Zielknoten treffen dann verlassen wir auch die Routine.

Auf diese Weise alle tragfähige Routen geprüft, aber entscheidend nur diejenigen mit den niedrigsten Kosten. Am Ende des Prozesses wird jeder Knoten mit den niedrigsten Kosten für zu diesem Knoten erhalten, einschließlich unserer Zielknoten.

Um die Route, die wir rückwärts aus unserem Zielknoten arbeiten. Da wir den Knoten wir kamen zusammen mit den Kosten gespeichert, hüpfen wir nur nach hinten um die Strecke aufzubauen. Für unser Beispiel würden wir am Ende mit etwas wie:

Knoten A - (Total) Kosten 0 - von dem Knoten keiner
Node B - Kosten 1 - vom Knoten A
Knoten C - Kosten 2 - von dem Knoten B
Knoten D - Kosten 1 - vom Knoten A
Knoten E - Kosten 2 - von dem Knoten D / Cost 2 - Vom Knoten B (dies ist eine Ausnahme , da es gleich Kosten)
Knoten F - Kosten 2 - Vom Knoten D

So ist der kürzeste Weg ist ADF.

Beantwortet am 26/09/2008 um 15:05
quelle vom benutzer

stimmen
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 , die unter Windows funktioniert (+ mobile) und Linux. Es gibt eine Reihe von interessanten [Anwendungen dieselben Daten verwenden, aber Gosmore hat einige coole verwendet zB Schnittstelle mit Websites .

Das größte Problem mit Routing ist schlechte Daten, und man bekommt nie gut genug Daten. Also, wenn Sie wollen versuchen, es Ihren Test hält sehr lokal, so dass Sie die Daten besser steuern können.

Beantwortet am 17/09/2008 um 09:34
quelle vom benutzer

stimmen
2

Anstelle von APIs zu jeder Karte Service Provider (wie Gmaps, Ymaps api) Es ist gut , das Lernen zu lernen Mapstraction

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

Ich möchte Sie auf die URL vorschlagen gehen und eine allgemeine API lernen. Es gibt gute Menge von How-Tos zu.

Beantwortet am 06/08/2008 um 14:35
quelle vom benutzer

stimmen
1

Aus meiner Erfahrung in diesem Bereich zu arbeiten, tut A * den Job sehr gut. Es ist (wie oben erwähnt) schneller als Dijkstra-Algorithmus, ist aber immer noch einfach genug für einen gewöhnlichen zuständigen Programmierer zu implementieren und zu verstehen.

das Streckennetz zu bauen ist der schwierigste Teil, aber das kann in eine Reihe von einfachen Schritten unterteilt werden: erhält alle Straßen; Sortieren der Punkte in Ordnung; stellen Gruppen von identischen Punkten auf verschiedenen Straßen in Kreuzungen (Knoten); hinzufügen Bögen in beiden Richtungen, in denen Knoten verbinden (oder nur in einer Richtung für eine Einbahnstrasse).

Der A * Algorithmus selbst ist gut auf Wikipedia dokumentiert . Der Schlüssel Ort zu optimieren , ist die Auswahl des besten Knoten aus der freien Liste, für die Sie brauchen eine leistungsstarke Prioritätswarteschlange. Wenn Sie C ++ verwenden können Sie die STL priority_queue Adapter verwenden.

Anpassen des Algorithmus zur Route über verschiedene Teile des Netzes (zB Fußgänger, Auto, öffentliche Verkehrsmittel usw.) zugunsten von Geschwindigkeit, Distanz oder anderen Kriterien ist ganz einfach. Sie tun das Filter durch das Schreiben zu steuern, welche Streckenabschnitte zur Verfügung stehen, wenn das Netzwerk den Aufbau und das Gewicht jeder zugeordnet ist.

Beantwortet am 15/07/2012 um 22:13
quelle vom benutzer

stimmen
1

Ein anderer Gedanke kommt mir in Bezug auf die Kosten der einzelnen Traversal, würde aber die Zeit und Rechenleistung erhöhen, die erforderlich zu berechnen.

Beispiel: Es gibt 3 Möglichkeiten , die ich nehmen kann (wo ich wohne) von Punkt A nach B zu gehen, nach dem Googlemaps. Garmin Geräte bieten jede dieser 3 Pfade in der QuickestRoutenberechnung. Nach jedem dieser Strecken oft durchlaufen und Mitteln (natürlich wird es zu Fehlern in Abhängigkeit von der Tageszeit, die Menge an Koffein etc.), ich fühle die Algorithmen berücksichtigen die Anzahl der Kurven in der Straße für hohe Genauigkeit nehmen könnten , zB wird gerade Straße von 1 Meile schneller sein als 1 Meile Straße mit scharfen Kurven drin . Kein praktischer Vorschlag , aber sicherlich ein Ich benutze die Ergebnismenge meiner täglichen Weg zur Arbeit zu verbessern.

Beantwortet am 18/09/2011 um 22:34
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more