Carte de Routage, à la manière de Google Maps?

Question

J'ai toujours été intrigué par Carte de Routage, mais je n'ai jamais trouvé une bonne introduction (ou même avancé!) niveau de tutoriels sur elle.Ne quelqu'un a des pointeurs, des astuces, etc?

Mise à jour: Je suis principalement à la recherche pour obtenir des conseils quant à la façon d'une carte système est mis en œuvre (structures de données, algorithmes, etc).

Answer 1

Jetez un oeil à la open street map projet pour voir comment ce genre de chose est d'être abordé dans un véritable projet de logiciel libre en utilisant uniquement fournie par l'utilisateur et de données sous licence et avoir un wiki contenant des trucs que vous pourriez trouver intéressant.

Quelques années en arrière le gars en question où assez facile à vivre et a répondu à beaucoup de questions que j'avais, donc je vois pas pourquoi ils ne sont toujours pas un joli bouquet.

Answer 2

Barry Brumitt, l'un des ingénieurs de Google maps itinéraire de trouver de fonction, a écrit un post sur le sujet qui peut être intéressant:

Le chemin de la recherche de chemin 11/06/2007 03:47:00 PM

Answer 3

A* est en fait beaucoup plus proche de la production de la cartographie des algorithmes.Il nécessite un peu moins d'exploration par rapport à Dijikstra de l'algorithme original.

Answer 4

Par Carte de Routage, vous trouver le chemin le plus court le long d'une rue de réseau?

Dijkstra plus court chemin algorithme est le plus connu.Wikipédia n'est pas une mauvaise intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Il y a un applet Java ici où vous pouvez la voir en action: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html et Google vous vous amener vers le code source dans à peu près n'importe quelle langue.

Réelle mise en œuvre pour la génération de parcours comprendra un peu de données sur le réseau de rues qui décrit les coûts associés avec la traversée des liens et des nœuds de réseau routier de la hiérarchie, vitesse moyenne, à l'intersection de priorité, le trafic de signal de liaison, interdit les virages etc.

Answer 5

Au lieu d'apprendre des Api pour chaque carte de fournisseur de service ( comme Gmaps, Ymaps api) il est bon de savoir Mapstraction

"Mapstraction est une bibliothèque qui fournit une API commune pour divers javascript Api de cartographie"

Je vous suggère d'aller à l'URL et d'en apprendre un général de l'API.Il ya une bonne quantité de Comment-Tos trop.

Answer 6

Je n'ai pas encore trouver un bon tutoriel sur le routage, mais il y a beaucoup de code à lire:

Il y a des GPL de routage applications qui utilisent les données d'Openstreetmap, par exemple Gosmore qui fonctionne sur Windows (+ mobile), et Linux.Il y a un certain nombre d'intéressant [applications en utilisant les mêmes données, mais gosmore a quelques cool utilise par exempleinterface avec les sites web.

Le plus gros problème de routage est mauvais de données, et vous ne jamais obtenir une qualité suffisante des données.Donc, si vous voulez essayer de garder votre test très local, de sorte que vous pouvez contrôler les données mieux.

Answer 7

À partir d'un point de vue conceptuel, imaginer de laisser tomber une pierre dans un étang et en regardant les vagues.Les routes représentent l'étang et la pierre de votre position de départ.

Bien sûr, l'algorithme serait de rechercher une certaine proportion de n^2 chemins que la distance n augmente.Vous vous prendrait position de départ et de vérifier tous les chemins disponibles à partir de ce point.Puis, de manière récursive d'appel pour les points à la fin de ces chemins et ainsi de suite.

Vous pouvez augmenter les performances, par pas de double sauvegarde sur un chemin, par pas de re-vérifier les routes à un point si elle a déjà été couverts et en donnant sur les chemins qui prennent trop de temps.

Une alternative est d'utiliser la fourmi phéromone approche, où les fourmis d'analyse de façon aléatoire à partir d'un point de départ et laissez une traînée de parfum, qui construit le plus de fourmis croix sur un chemin donné.Si vous envoyez (assez) des fourmis à la fois le point de départ et les points de fin puis finalement le chemin avec le plus fort parfum sera le plus court.C'est parce que le chemin le plus court aura été visité plusieurs fois dans une période de temps donnée, étant donné que les fourmis marcher à un rythme uniforme.

EDIT @ Spikie

Une autre explication de la façon de mettre en œuvre l'étang de l'algorithme potentiel des structures de données nécessaires sont mis en évidence:

Vous aurez besoin de stocker la carte comme un réseau.C'est tout simplement un ensemble de nodes et edges entre eux.Un ensemble de nodes constituer un route.Une arête relie deux nœuds (peut-être les deux le même nœud), et est associé à un cost comme distance ou time la traversée de la pointe.Une arête peut soit être bidirectionnel ou unidirectionnel.Probablement plus simple d'avoir de l'uni-directionnelle et un double pour deux façon de voyager entre les nœuds (c'est à direun bord de A à B et un autre de B à A).

Par exemple, imaginez trois stations de chemin de fer disposés en un triangle équilatéral triangle pointant vers le haut.Il y a également trois autres stations de chaque mi-chemin entre eux.Les bords de rejoindre toutes les stations adjacentes ensemble, la version finale du schéma ont une forme de triangle inversé assis à l'intérieur du plus grand triangle.

Étiquette nœuds à partir du bas à gauche, de gauche à droite et de haut, A,B,C,D,E,F (F vers le haut).

Assumer les bords peuvent être parcourus dans les deux sens.Chaque arête a un coût de 1 km.

Ok, donc, nous souhaitons à la route à partir du bas à gauche, Un pour le haut de la station F.Il y a beaucoup de voies possibles, y compris ceux qui se replient sur eux-mêmes, par exempleABCEBDEF.

Nous avons une routine dire, NextNode, qui accepte une node et un cost et s'appelle elle-même pour chaque nœud, il peut voyager.

Clairement, si nous laissons cette routine lancé, il va finalement découvrir toutes les routes, y compris ceux qui sont potentiellement infini de longueur (par exemple ABABABAB etc).Nous nous arrêtons cela se passe par la vérification des cost.Chaque fois que nous visitons un nœud qui n'a pas été visité avant de nous mettre à la fois le coût et le nœud nous sommes venus à l'encontre de ce nœud.Si un nœud a été visité avant, nous vérifions contre les coûts existants et, si nous sommes moins chers que nous mettons à jour le nœud et portent sur (recursing).Si nous avons de plus cher, alors nous sauter le nœud.Si tous les nœuds sont ignorées alors nous sortir de la routine.

Si nous avons atteint notre cible nœud puis nous sortir de la routine aussi.

De cette façon, tous viables routes sont vérifiées, mais le point crucial seulement ceux avec le plus bas coût.Par la fin du processus, chaque nœud aura coût le plus bas pour arriver à ce nœud, y compris notre nœud cible.

Pour obtenir l'itinéraire nous travailler à rebours à partir de notre nœud cible.Depuis que nous avons stocké le nœud nous sommes venus avec le coût, nous avons juste hop vers l'arrière du bâtiment jusqu'à la route.Pour notre exemple, on allait se retrouver avec quelque chose comme:

Un Nœud - (Total) Coût 0 - À Partir Du Nœud Aucun
Le Nœud B - Coût 1 - À Partir D'Un Nœud
Le Nœud C - Coût 2 - Du Nœud B
Le Nœud D - Coût 1 - À Partir D'Un Nœud
Le noeud E - prix 2 - Du Nœud D / Coût 2 - à Partir du Nœud B (ceci est une exception, car il n'y a coût égal)
Nœud F - Coût 2 - Du Nœud D

Donc, la route la plus courte est de l'ADF.

Answer 8

À partir de mon expérience de travail dans ce domaine, Un* fait le travail très bien.Il est (comme mentionné ci-dessus) plus rapide que l'algorithme de Dijkstra, mais est encore assez simple pour un ordinairement un programmeur compétent pour mettre en œuvre et à comprendre.

La construction du réseau routier est la partie la plus difficile, mais qui peut être décomposé en une série d'étapes simples:obtenez toutes les routes;trier les points dans l'ordre;faire des groupes de points identiques sur différentes routes dans les intersections (nœuds);ajoutez des arcs dans les deux directions, où les nœuds se connecter (ou dans une seule direction pour une route à sens unique).

L'algorithme A* est lui-même bien documenté sur Wikipédia.La clé de la place pour optimiser la sélection du meilleur noeud de la liste ouverte, pour laquelle vous avez besoin de hautes performances, la file d'attente de priorité.Si vous êtes à l'aide de C++, vous pouvez utiliser la STL priority_queue adaptateur.

La personnalisation de l'algorithme de route sur les différentes parties du réseau (par exemple, piéton, voiture, transports en commun, etc.) de faveur de la vitesse, de la distance ou d'autres critères est assez facile.Vous le faire en écrivant des filtres pour contrôler les segments de route sont disponibles, lors de la construction du réseau, et dont le poids est attribué à chacun.

Answer 9

Une autre pensée me vient à l'esprit concernant le coût de chaque traversée, mais permettrait d'augmenter le temps et la puissance de traitement nécessaire pour calculer.

Exemple: Il existe 3 façons je peux prendre (où j'habite) pour aller d'un point A à B, selon le GoogleMaps.Les appareils Garmin offre à chacun de ces 3 chemins d'accès dans le Quickest le calcul de l'itinéraire.Après la traversée de chacune de ces voies de nombreuses fois et en moyenne (évidemment il y aura des erreurs en fonction du moment de la journée, la quantité de caféine, etc.), Je sens les algorithmes pourraient prendre en compte le nombre de coudes dans la route pour le haut niveau de précision, par exemple route droite de 1 mile sera plus rapide que de 1 mile de la route avec des virages en elle.Pas d'un point de vue pratique, mais certainement celui que j'utilise pour améliorer le résultat de mon trajet quotidien.