Carte Route, a la Google Maps?

voix
19

J'ai toujours été intriguée par Carte Route, mais je ne l'ai jamais trouvé une bonne introduction (ou même avancé!) Niveau des tutoriels sur elle. Quelqu'un at-il des pointeurs, conseils, etc?

Mise à jour: Je suis avant tout à la recherche de pointeurs à la façon dont un système de carte est mis en œuvre (structures de données, algorithmes, etc.).

Créé 05/08/2008 à 21:24
source utilisateur
Dans d'autres langues...                            


9 réponses

voix
14

Jetez un coup d' oeil au projet de plan ouvert pour voir comment ce genre de chose est abordée dans un projet de logiciel libre en utilisant uniquement truely utilisateur et les données fournies sous licence et un wiki contenant des choses que vous pourriez trouver intéressant .

Quelques années les gars impliqués où assez facile et répondu à beaucoup de questions que j'avais donc je ne vois aucune raison pourquoi ils ne sont toujours pas un beau bouquet.

Créé 05/08/2008 à 21:27
source utilisateur

voix
4

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

Créé 25/09/2008 à 00:19
source utilisateur

voix
4

Barry Brumitt, l'un des ingénieurs de fonction de recherche d'itinéraire Google Maps, a écrit un message sur le sujet qui peut intéresser:

La route de mieux chemin trouver 11/06/2007 15:47:00

Créé 17/09/2008 à 09:44
source utilisateur

voix
4

Par Carte Route, vous voulez dire trouver le chemin le plus court le long d'un réseau routier?

Dijkstra algorithme du plus court chemin est le plus connu. Wikipedia n'a pas une mauvaise introduction: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Il y a une applet Java ici où vous pouvez le voir en action: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html et Google vous vous dirigez au code source dans presque tous les la langue.

Toute mise en œuvre réelle pour générer des itinéraires de conduite comprendra un peu de données sur le réseau routier qui décrit les coûts associés à qui traversent les liens et la hiérarchie des nœuds de réseau routier, la vitesse moyenne, la priorité d'intersection, le signal de trafic de liaison, tours interdits etc.

Créé 15/08/2008 à 05:31
source utilisateur

voix
2

D'un point de vue conceptuel, imaginez tomber une pierre dans un étang et regarder les ondulations. Les routes représenteraient l'étang et la pierre de votre position de départ.

Bien sûr, l'algorithme devrait rechercher une certaine proportion de n ^ 2 voies que la distance augmente n. Vous prendriez-vous la position de départ et vérifier tous les chemins disponibles à partir de ce moment-là. Ensuite, appelez récursive pour les points à la fin de ces chemins et ainsi de suite.

Vous pouvez augmenter les performances, en ne double appui sur un chemin, en ne revérifier les routes à un point si elle a déjà été couvert et en donnant sur les chemins qui prennent trop de temps.

Une autre façon est d'utiliser l'approche de phéromone fourmi, où les fourmis ramper au hasard à partir d'un point de départ et de laisser une trace de parfum, qui construit les plus de fourmis traverser un chemin donné. Si vous envoyez (assez) fourmis à la fois le point de départ et les points d'extrémité puis finalement le chemin avec le sera le plus fort parfum. En effet, le chemin le plus court aura été visité plusieurs fois dans une période de temps donnée, étant donné que les fourmis marchent à un rythme uniforme.

EDIT @ spikie

Comme une explication plus détaillée de la façon de mettre en œuvre l'algorithme de l'étang - structures de données potentielles nécessaires sont mises en évidence:

Vous aurez besoin de stocker la carte en tant que réseau. Ceci est tout simplement un ensemble de nodeset edgesentre eux. Un ensemble de nodesconstituer un route. Une arête relie deux noeuds (peut - être tous les deux le même noeud), et a un associé costcomme distanceou timepour traverser le bord. Une arête peut soit être soit bi-directionnel ou uni-directionnel. Probablement la plus simple d'avoir juste les unidirectionnelles et double pour deux Voyage de chemin entre les noeuds ( par exemple un bord de A à B et un autre pour B à A).

A titre d'exemple imaginer trois gares disposés dans un triangle équilatéral vers le haut. Il y a aussi trois autres stations chacune à mi-chemin entre eux. Arêtes rejoindre toutes les stations adjacentes ensemble, le schéma finale aura un triangle inversé assis à l'intérieur du triangle plus grand.

les noeuds d'étiquettes à partir de la gauche en bas, en allant de gauche à droite et de haut, comme A, B, C, D, E, F (F en haut).

Supposons que les bords peuvent être traversés dans les deux sens. Chaque bord a un coût de 1 km.

Ok, donc nous voulons la route du bas à gauche A à la station supérieure F. Il existe de nombreuses voies possibles, y compris ceux qui doublent sur eux-mêmes, par exemple ABCEBDEF.

Nous avons un exemple de routine, NextNodequi accepte nodeet costet appelle lui - même pour chaque nœud , il peut se rendre.

Il est clair que si nous laissons cette course de routine , il finira par découvrir toutes les routes, y compris ceux qui sont potentiellement une longueur infinie (par exemple ABABABAB etc). Nous nous arrêtons cela se passe en vérifiant contre cost. Chaque fois que nous visitons un nœud qui n'a pas été visité, nous mettons à la fois le coût et le nœud que nous venons contre ce nœud. Si un nœud a été visité , nous vérifions contre le coût existant et si nous sommes moins chers que nous mettons à jour le noeud et continuez (récursion). Si nous sommes plus chers, alors nous sautons le nœud. Si tous les noeuds sont ignorés alors que nous sortons de la routine.

Si nous avons atteint notre noeud cible alors nous sortirons aussi la routine.

De cette façon, toutes les routes viables sont vérifiées, mais cruciale que ceux qui ont le plus bas coût. À la fin du processus chaque nœud aura le coût le plus bas pour arriver à ce noeud, y compris notre noeud cible.

Pour obtenir l'itinéraire que nous travaillons en arrière de notre noeud cible. Puisque nous stockons le nœud que nous venons avec le coût, nous sautons juste en arrière construire la route. Pour notre exemple, nous finirions avec quelque chose comme:

Noeud A - (Total) Coût 0 - à partir du noeud Aucun
nœud B - Coût 1 - à partir du noeud A
noeud C - Coût 2 - à partir du noeud B
noeud D - Coût 1 - à partir du noeud A
noeud E - Coût 2 - à partir du noeud D / coût 2 - à partir du noeud B (ce qui est une exception car il y a coût égal)
Noeud F - coût 2 - à partir du noeud D

Ainsi, la route la plus courte est ADF.

Créé 26/09/2008 à 15:05
source utilisateur

voix
2

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

Il y a des applications de routage GPL qui utilisent des données OpenStreetMap, par exemple Gosmore qui fonctionne sur Windows (+ mobile) et Linux. Il y a un certain nombre d'applications intéressantes [ en utilisant les mêmes données, mais Gosmore a une certaine fraîcheur utilise l' interface par exemple avec des sites Web .

Le plus gros problème avec le routage est mauvais données, et vous n'obtenir des données assez bonnes. Donc, si vous voulez essayer de garder votre test très local afin que vous puissiez contrôler les données mieux.

Créé 17/09/2008 à 09:34
source utilisateur

voix
2

Au lieu d'API apprendre à chaque fournisseur de services de carte (comme Gmaps, Ymaps api) Il est bon d'apprendre Mapstraction

« Mapstraction est une bibliothèque qui fournit une API commune pour les différentes API de cartographie javascript »

Je vous suggère d'aller à l'URL et d'apprendre une API générale. Il y a une bonne quantité de How-Tos aussi.

Créé 06/08/2008 à 14:35
source utilisateur

voix
1

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

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

L'algorithme A * lui - même est bien documenté sur Wikipedia . L'endroit clé pour optimiser le choix du meilleur noeud de la liste ouverte, pour laquelle vous avez besoin d' une file d' attente prioritaire de haute performance. Si vous utilisez C ++ , vous pouvez utiliser l'adaptateur priority STL.

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

Créé 15/07/2012 à 22:13
source utilisateur

voix
1

Une autre pensée me vient en ce qui concerne le coût de chaque traversal, mais augmenterait le temps et la puissance de traitement nécessaire pour calculer.

Exemple: Il y a 3 façons que je peux prendre (où je vis) pour aller du point A à B, selon la GoogleMaps. Les appareils Garmin offrent chacun de ces 3 chemins dans le Quickestcalcul de l' itinéraire. Après avoir traversé chacun de ces itinéraires plusieurs fois et en moyenne ( de toute évidence , il y aura des erreurs en fonction du moment de la journée, la quantité de caféine , etc.), je pense que les algorithmes pourraient prendre en compte le nombre de virages sur la route pour haut niveau de précision , par exemple route droite de 1 mile sera plus rapide qu'une route 1 mile avec virages serrés en elle . Pas une suggestion pratique , mais certainement l' un que j'utilise pour améliorer le jeu de résultats de mon trajet quotidien.

Créé 18/09/2011 à 22:34
source utilisateur

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