google-maps - une - widget carte google map




Routage de carte, à la Google Maps? (6)

J'ai toujours été intrigué par Map Routing, mais je n'ai jamais trouvé de bons tutoriels de niveau introductif (ou même avancé!). Quelqu'un a-t-il des indications, des astuces, etc.?

Mise à jour: Je suis principalement à la recherche de pointeurs sur la façon dont un système de carte est implémenté (structures de données, algorithmes, etc.).


Jetez un coup d'oeil sur le projet de carte ouverte pour voir comment ce genre de chose est abordé dans un projet de logiciel vraiment gratuit en utilisant uniquement des données fournies par l'utilisateur et sous licence et avoir un wiki contenant des choses que vous pourriez trouver intéressantes .

Il y a quelques années, les gars impliqués étaient assez faciles et ont répondu à beaucoup de questions que j'ai eues, donc je ne vois pas pourquoi ils ne sont toujours pas un bon groupe.


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

"Mapstraction est une bibliothèque qui fournit une API commune pour diverses API de mappage 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.


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

Il existe 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 utilisant les mêmes données, mais gosmore a quelques utilisations intéressantes, par exemple l'interface avec des sites Web .

Le plus gros problème avec le routage est de mauvaises données, et vous n'obtenez jamais assez de données. Donc, si vous voulez l'essayer, gardez votre test très local afin de mieux contrôler les données.


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


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

Construire le réseau de routes est la partie la plus difficile, mais cela peut être décomposé en une série de mesures simples: obtenir toutes les routes; trier les points dans l'ordre; faire des groupes de points identiques sur des routes différentes en intersections (nœuds); ajouter des arcs dans les deux directions où les nœuds se connectent (ou dans une direction uniquement pour une route à sens unique).

L'algorithme A * lui-même est bien documenté sur Wikipedia . L'endroit clé à optimiser est la sélection du meilleur nœud de la liste ouverte, pour lequel vous avez besoin d'une file d'attente prioritaire haute performance. Si vous utilisez C ++, vous pouvez utiliser l'adaptateur STL priority_queue.

La personnalisation de l'algorithme pour acheminer différentes parties du réseau (p. Ex., Piéton, voiture, transport en commun, etc.) de manière à favoriser la vitesse, la distance ou d'autres critères est assez facile. Vous le faites en écrivant des filtres pour contrôler quels segments d'itinéraire sont disponibles, quand vous construisez le réseau, et quel poids est assigné à chacun.


Une autre pensée me vient à l'esprit en ce qui concerne le coût de chaque traversée, mais augmenterait le temps et la puissance de traitement requis pour le calcul.

Exemple: Il y a 3 façons que je peux prendre (où je vis) pour passer du point A au point B, selon les GoogleMaps. Les unités Garmin offrent chacun de ces trois chemins dans le calcul de l'itinéraire le plus Quickest . Après avoir parcouru chacune de ces routes plusieurs fois et moyenné (évidemment il y aura des erreurs selon l'heure, la quantité de caféine etc.), je pense que les algorithmes pourraient prendre en compte le nombre de coudes sur la route pour un haut niveau de précision Par exemple, une route droite de 1 mile sera plus rapide qu'une route de 1 mile avec des virages serrés . Pas une suggestion pratique mais certainement une que j'utilise pour améliorer le résultat de mon trajet quotidien.





gis