Module cartographie : calculs d'itinéraire
Comme vous avez pu le constater quand vous avez travaillé sur Open Street Map, il est possible de définir les voies de communication (principalement les routes). La base de données OSM contient donc les routes (enfin, la plupart des routes...). En utilisant ces données, il est possible de développer des outils capables de calculer des itinéraires routiers (comme le propose tous les logiciels "GPS" : Waze, ViaMichelin, Mappy...) : vous renseignez votre lieu de départ, votre lieu d'arrivée puis le logiciel calcule votre itinéraire. Ce calcul d'itinéraire repose sur des algorithmes relativement complexes, par exemple l'algorithme de Dijkstra qui permet d'obtenir le plus court chemin entre deux points.
À faire vous-même 1
Sans entrer dans les détails, l'algorithme de Dijkstra travaille sur des graphes (chaque ville est un sommet du graphe et chaque route est une arête du graphe), visionnez cette vidéo pour en savoir plus.
À faire vous-même 2
Expliquez en quelques lignes le principe de l'algorithme de Dijkstra.
La bibliothèque Python pyroutelib3 propose des "outils" pour calculer des itinéraires à partir des données d'Open Street Map.
À faire vous-même 3
En utilisant le logiciel spyder, saisir le code ci-dessous. Enregistrez le fichier contenant ce code dans le dossier "itin". Testez ensuite ce programme.
from pyroutelib3 import Router
####ATTENTION : les 4 lignes suivantes sont à conserver uniquement si vous exécutez ce programme depuis le lycée#####
import urllib.request
proxy = urllib.request.ProxyHandler({'https':'172.16.0.1:3128'})
opener = urllib.request.build_opener(proxy)
urllib.request.install_opener(opener)
#################
router = Router("car")
depart = router.findNode(46.078025, 6.409053)
arrivee = router.findNode(46.193253, 6.234158)
status, route = router.doRoute(depart, arrivee)
if status == 'success':
routeLatLons = list(map(router.nodeLatLon, route))
Une fois l'exécution du programme terminée (cela peut prendre quelques minutes), à l'aide de l'"explorateur de variables" de spyder, visionnez le contenu de la variable "routeLatLons". Comme vous pouvez le constater, cette variable contient une liste de couples de valeurs (latitude, longitude). Cette liste contient donc les coordonnées des différents points par lesquels il faut passer pour se rendre du point de départ jusqu'au point d'arrivée (en passant bien évidemment par les routes définies dans Open Street Map).
Quelques explications sur le programme proposé dans le "À faire vous-même 3" :
- Nous commençons par importer la bibliothèque "pyroutelib3" avec la première ligne "from pyroutelib3 import Router"
- La deuxième ligne permet de définir le véhicule qui sera utilisé pour effectuer le trajet. Dans notre cas, nous utilisons une voiture ("car"), mais il est possible de choisir d'autres moyens de transport : cycle, foot, horse, tram, train
- Les 2 lignes suivantes permettent de définir le point de départ et le point d'arrivée. Nous avons "router.findNode(latitude, longitude)", il suffit de renseigner la latitude et la longitude du lieu.
- La ligne "status, route = router.doRoute(depart, arrivee)" permet d'effectuer le calcul de l'itinéraire.
- La dernière ligne est exécutée uniquement si le calcul est mené à son terme ("if" de la ligne précédente). La variable "routeLatLons" contient la liste des coordonnées des points de cheminement (points qui constituent le chemin entre le point de départ et le point d'arrivée)
À faire vous-même 4
Modifiez le programme du "À faire vous-même 3", pour calculer le trajet entre deux villes de votre choix avec le moyen de transport de votre choix.
Avoir une liste de coordonnées, c'est déjà pas mal, mais cette liste n'est pas très exploitable telle quelle. Nous allons donc utiliser ce que nous avons déjà vu précédemment sur la création de cartes.
À faire vous-même 5
Testez le programme ci-dessous (une fois le programme Python exécuté, ouvrez avec un navigateur web le fichier "maCarte.html").
from pyroutelib3 import Router
import folium
####ATTENTION : les 4 lignes suivantes sont à conserver uniquement si vous exécutez ce programme depuis le lycée#####
import urllib.request
proxy = urllib.request.ProxyHandler({'https':'172.16.0.1:3128'})
opener = urllib.request.build_opener(proxy)
urllib.request.install_opener(opener)
#################
router = Router("car")
depart = router.findNode(46.078025, 6.409053)
arrivee = router.findNode(46.193253, 6.234158)
status, route = router.doRoute(depart, arrivee)
if status == 'success':
routeLatLons = list(map(router.nodeLatLon, route))
c= folium.Map(location=[46.078025, 6.409053],zoom_start=10)
for coord in routeLatLons:
coord=list(coord)
folium.Marker(coord).add_to(c)
c.save('maCarte.html')
Le programme ci-dessous ne devrait pas vous poser trop de problèmes. Seule nouveauté, la boucle "for" :
for coord in routeLatLons:
coord=list(coord)
folium.Marker(coord).add_to(c)
qui permet de parcourir la liste de coordonnées (contenue dans la variable "routeLatLons") et d'ajouter un marqueur pour chaque couple de coordonnées.
À faire vous-même 6
Modifiez le programme du "À faire vous-même 5" pour qu'apparaisse sur une carte un itinéraire de votre choix (en définissant le point de départ, le point d'arrivée et le type de véhicule).