Lire une carte et Calculs d’itinéraires
Sciences numériques et technologie
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.
Entraînement 1
À l’aide de GéoPortail ou OpenStreetMap, indiquer sur le graphe ci-dessous le nom des villes manquantes de Grande Terre.
Entraînement 2
Compléter le tableau suivant avec les distances minimales.
| Ville | A | AB | G | M | LM | PAP | PC | PL | SA | SF |
|---|---|---|---|---|---|---|---|---|---|---|
| A | x | 12 | 9 | 5 | ||||||
| AB | X | 19 | 32 | 9 | ||||||
| G | 12 | X | 9 | 14 | ||||||
| M | 9 | 19 | X | 12 | 8 | 8 | ||||
| LM | 32 | 12 | X | 14 | ||||||
| PAP | 5 | 9 | X | |||||||
| PC | 20 | X | 43 | |||||||
| PL | 9 | 8 | 8 | X | ||||||
| SA | 14 | X | 15 | |||||||
| SF | 14 | 15 | X |
Après avoir compléter le tableau des distances ci-dessus, déterminer l’itinéraire le plus court entre Anse Bertrand et Saint Anne et Gosier et Le Moule.
Entraînement 3
C’est la période de la coupe de la Canne. Le temps de parcours entre Morne à l’eau et Le Moule est doublé (2 chargements de canne circulent). Un Jumbo s’est renversé entre Port Louis et Morne-à-l’eau (la route est donc actuellement coupée). Déterminer l’itinéraire le plus rapide entre Anse Bertrand et Saint Anne et Gosier et Le Moule..
Entraînement 4
Quels sont les autres critères qui pourraient être pris en compte pour choisir le « meilleur » itinéraire ?
Entraînement 5
Comparer les résultats donnés par GéoPortail, GoogleMaps et ViaMichelin pour le trajet Lille Marseille. Que pouvez-vous en conclure ?
Entraînement 6
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.
Expliquez en quelques lignes le principe de l'algorithme de Dijkstra.
Pour aller plus loin (Optionnel )
La bibliothèque Python pyroutelib3 propose des "outils" pour calculer des itinéraires à partir des données d'Open Street Map.
Entraînement 3
Créez un dossier, nommé "itin". Enregistrez ensuite le fichier pyroutelib3.py (clic droit, "Enregistrer sous") dans ce dossier "itin".
Entraînement 4
En utilisant le logiciel thonny, saisir le code ci-dessous. Enregistrez le fichier contenant ce code dans le dossier "itin". Testez ensuite ce programme.
from pyroutelib3 import Router
router = Router("car")
depart = router.findNode(16.470225, -61.514811)
arrivee = router.findNode(16.233625, -61.420184)
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 2" :
- 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)
Entraînement 5
Modifiez le programme du "À faire vous-même 2", 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.
Entraînement 6
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
router = Router("car")
depart = router.findNode(16.470225, -61.514811)
arrivee = router.findNode(16.233625, -61.420184)
status, route = router.doRoute(depart, arrivee)
if status == 'success':
routeLatLons = list(map(router.nodeLatLon, route))
c= folium.Map(location=[16.470225, -61.514811],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.
Entraînement 7
Modifiez le programme du "À faire vous-même 6" 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).