Kartenrouting, a la Google Maps?

  • Map Routing hat mich schon immer fasziniert, aber ich habe noch nie ein gutes Einführungslehrgang (oder sogar Fortgeschrittene!) dazu gefunden. Hat jemand Zeiger, Hinweise usw.?

    Update: Ich bin vor allem auf der Suche nach Hinweisen, wie ein Kartensystem (Datenstrukturen) implementiert wird Algorithmen usw.).

    12 May 2016
    Vikash PandeyPatrick Peters
9 answers
  • Sehen Sie sich das Straßenkartenprojekt an, um zu sehen, wie sich diese Dinge entwickeln In einem wirklich kostenlosen Softwareprojekt mit nur vom Benutzer bereitgestellten und lizenzierten Daten bearbeitet, erhalten Sie ein Wiki mit Informationen, die Sie möglicherweise finden interessant .

    Vor ein paar Jahren waren die involvierten Jungs ziemlich unkompliziert und beantworteten viele Fragen, die ich hatte, daher sehe ich keinen Grund, warum sie immer noch nicht nett sind Bündel.

    06 August 2008
    sparkes
  • Barry Brumitt, einer der Ingenieure der Google Maps-Funktion zur Routenfindung, hat einen Beitrag zum Thema geschrieben, der möglicherweise von Interesse ist:

    Der Weg zu einer besseren Pfadfindung 11/06 / 2007 15:47:00 Uhr

    17 September 2008
    Mark
  • Unter Kartenrouting versteht man den kürzesten Pfad in einem Straßennetz?

    Der Dijkstra-Algorithmus für den kürzesten Pfad 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.html Sie führen den Quellcode in nahezu jeder Sprache aus.

    Jede reale Implementierung zum Erstellen von Fahrstraßen enthält eine ganze Reihe von Daten im Straßennetz, die die mit den durchquellenden Links verbundenen Kosten beschreiben und Knoten - Straßennetz-Hierarchie, Durchschnittsgeschwindigkeit, Kreuzungspriorität, Verknüpfung von Verkehrssignalen, verbotene Abbiegungen usw.

    20 November 2016
    RamenChefajith r
  • A * ist tatsächlich wesentlich näher an den Produktions-Mapping-Algorithmen. Im Vergleich zum ursprünglichen Algorithmus von Dijikstra ist dies etwas weniger erforscht.

    25 September 2008
    Sargun Dhillon
  • Ich habe noch kein gutes Tutorial für das Routing gefunden, aber es gibt viel zu lesenden Code:

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

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

    17 September 2008
    2 revsErik Johansson
  • Anstatt APIs für jeden Kartendienstanbieter (wie Gmaps, Ymaps-API) zu lernen, ist es gut zu lernen Mapstraction

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

    würde ich schlagen Sie vor, dass Sie zur URL gehen und eine allgemeine API lernen. Es gibt auch eine Menge How-Tos.

    06 August 2008
    Arjan
  • Stellen Sie sich konzeptionell vor, einen Stein in einen Teich fallen zu lassen und die Wellen zu beobachten. Die Routen würden den Teich und den Stein als Ausgangsposition darstellen.

    Natürlich müsste der Algorithmus mit zunehmender Entfernung n einen bestimmten Anteil von n ^ 2-Pfaden suchen. Sie würden Ihre Startposition übernehmen und alle verfügbaren Pfade von diesem Punkt aus überprüfen. Rufen Sie dann rekursiv die Punkte am Ende dieser Pfade usw. auf.

    Sie können die Leistung steigern, indem Sie nicht doppelt auf einem Pfad doppelklicken, indem Sie die Routen nicht erneut überprüfen zu einem Zeitpunkt, wenn es bereits abgedeckt wurde, und durch Aufgeben von Pfaden, die zu lange dauern.

    Eine Alternative ist die Verwendung des Pheromonansatzes, bei dem die Ameisen zufällig hin und her kriechen einen Startpunkt und hinterlasse einen Duftpfad, der die Anhäufung von mehr Ameisen über einen bestimmten Pfad aufbaut. Wenn Sie (genug) Ameisen sowohl vom Start- als auch vom Endpunkt senden, ist der Pfad mit dem stärksten Duft möglicherweise der kürzeste. Dies liegt daran, dass der kürzeste Weg in einem bestimmten Zeitraum mehrmals besucht wurde, vorausgesetzt, die Ameisen laufen in einem einheitlichen Tempo.

    EDIT @ Spikie

    Als weitere Erklärung für die Implementierung des Teichalgorithmus werden mögliche Datenstrukturen hervorgehoben:

    Sie werden es brauchen um die Karte als Netzwerk zu speichern. Dies ist einfach eine Menge von nodes und edges zwischen ihnen. Ein Satz von nodes bildet einen route. Eine Kante verbindet zwei Knoten (möglicherweise beide denselben Knoten) und ist mit cost wie distance oder time verknüpft, um die Kante zu durchqueren. Eine Kante kann entweder bidirektional oder unidirektional sein. Wahrscheinlich ist es am einfachsten, nur unidirektionale zu haben und für eine Hin- und Rückfahrt zwischen Knoten (dh eine Kante von A nach B und eine andere von B nach A) zu verdoppeln.

    By Als Beispiel stellen wir uns drei Bahnhöfe vor, die in einem gleichseitigen Dreieck aufwärts gerichtet sind. Es gibt auch drei weitere Stationen auf halber Strecke. KanteWenn Sie alle benachbarten Stationen zusammenfügen, wird das letzte Diagramm ein umgekehrtes Dreieck innerhalb des größeren Dreiecks haben.

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

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

    Ok, wir möchten also von links unten A bis zur Bergstation F fahren. Es gibt viele mögliche Routen, einschließlich derjenigen, die sich verdoppeln wieder auf sich selbst, z ABCEBDEF.

    Wir haben ein Routinewort NextNode, das ein node und ein cost akzeptiert und sich für jeden Knoten, zu dem es reisen kann, selbst aufruft.

    Wenn wir diese Routine ausführen lassen, werden natürlich alle Routen entdeckt, einschließlich der Routen, die möglicherweise unendlich lang sind (z. B. ABABABAB usw.). Wir stoppen dies, indem wir gegen cost prüfen. Immer wenn wir einen Knoten besuchen, der noch nicht besucht wurde, stellen wir sowohl die Kosten als auch den Knoten, von dem wir kamen, gegen diesen Knoten. Wenn ein Knoten besucht wurde, bevor wir die vorhandenen Kosten prüfen, und wenn wir billiger sind, aktualisieren wir den Knoten und machen weiter (Rekursion). Wenn wir teurer sind, überspringen wir den Knoten. Wenn alle Knoten übersprungen werden, verlassen wir die Routine.

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

    Auf diese Weise werden alle möglichen Routen geprüft, aber nur entscheidend diejenigen mit den niedrigsten 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 erhalten, arbeiten wir rückwärts von unserem Zielknoten. Da wir den Knoten gespeichert haben, aus dem wir mit den Kosten kamen, springen wir einfach zurück und bauen die Route auf. Für unser Beispiel würden wir am Ende Folgendes anzeigen:

    Knoten A - (Gesamt) Kosten 0 - Von 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 - Von Knoten D / Kosten 2 - Von Knoten B (dies ist eine Ausnahme als

    05 August 2010
    Guillermo Phillips
  • Ein anderer Gedanke fällt mir in Bezug auf die Kosten für jede Durchquerung ein, würde aber die Zeit und die Rechenleistung erhöhen, die zur Berechnung erforderlich sind.

    Beispiel: Es gibt drei Möglichkeiten, an denen (wo ich wohne) ich von A nach B gehen kann, je nach den GoogleMaps. Garmin-Einheiten bieten jeden dieser 3 Pfade in der Quickest Routenberechnung an. Nachdem ich jede dieser Routen mehrmals durchquert und gemittelt habe (offensichtlich wird es je nach Tageszeit, Menge an Koffein usw. zu Fehlern kommen), denke ich, dass die Algorithmen die Anzahl der Straßenbiegungen berücksichtigen könnten, um eine hohe Genauigkeit zu erreichen B. eine gerade Straße von 1 Meile wird schneller sein als eine 1 Meile Straße mit scharfen Kurven . Kein praktischer Vorschlag, aber sicherlich eine, die ich verwende, um sie zu verbessern Ergebnismenge meines täglichen Arbeitsweges.

    05 April 2016
    Eray BalkanliAnil
  • Aus meiner Erfahrung in diesem Bereich macht A * die Arbeit sehr gut. Es ist (wie oben erwähnt) schneller als der Algorithmus von Dijkstra, aber es ist für einen gewöhnlichen Programmierer immer noch einfach genug, es zu implementieren und zu verstehen Das kann in eine Reihe einfacher Schritte unterteilt werden: alle Straßen abfahren; sortiere die Punkte in der Reihenfolge; Gruppen von identischen Punkten auf verschiedenen Straßen zu Knotenpunkten (Knoten) machen; Fügen Sie Bögen in beiden Richtungen hinzu, in denen Knoten eine Verbindung herstellen (oder nur in eine Richtung für eine Einbahnstraße).

    Der A * -Algorithmus selbst ist auf Wikipedia gut dokumentiert . Die zu optimierende Schlüsselstelle ist die Auswahl des besten Knotens aus der offenen Liste, für den Sie eine Warteschlange mit hoher Performance-Priorität benötigen. Wenn Sie C ++ verwenden, können Sie den STL-Priority_queue-Adapter verwenden.

    Anpassen des Algorithmus zum Routen über verschiedene Teile des Netzwerks (z. B. Fußgänger, Auto, öffentliche Verkehrsmittel usw.) ) von Gunst Geschwindigkeit, Entfernung oder andere Kriterien ist ziemlich einfach. Dazu schreiben Sie Filter, um zu steuern, welche Routensegmente verfügbar sind, wann das Netzwerk erstellt wird und welche Gewichtung jedem zugewiesen wird.

    16 July 2012
    Graham Asher