Déjà plus de
1 million
d'inscrits !
Déjà plus de
1 million
d'inscrits !
Introduction :
Les réseaux de transport deviennent de plus en plus complexes, surtout dans les grandes métropoles. Les outils de calcul d’itinéraire sont une aide précieuse pour déterminer le plus court chemin à emprunter.
Dans ce cours, nous allons voir comment une carte numérique est un outil pratique pour le calcul d’itinéraire. Ensuite, nous allons découvrir OpenStreetMap, une carte numérique sous licence libre qui peut être éditée par tout internaute. Enfin, nous allons nous intéresser au calcul du plus court chemin entre deux points en utilisant l’algorithme de Dijkstra.
La cartographie numérique
La cartographie désigne la conception et la réalisation des cartes. Elle tend à représenter l’espace physique sous une forme réduite et simplifiée.
La cartographie numérique se distingue par son format numérique qui permet de déplacer la carte, de zoomer et dé-zoomer, de chercher une adresse, etc. Couplée avec un positionnement par GPS, la carte numérique permet aisément de se repérer et de se déplacer.
Toute carte est un modèle réduit de la réalité selon une échelle.
Échelle :
Mathématiquement, l’échelle est le rapport entre un objet réel et sa reproduction.
Sur une carte papier, l’échelle s’exprime sous la forme d’une fraction : distance sur la carte sur distance réelle.
1/50 000 signifie que 1 cm sur la carte représente 50 000 cm sur le terrain.
Le changement d’échelle par la fonction de zoom fait apparaître ou disparaître des informations.
On peut notamment le constater en observant les voies telles que les rues des villes et les routes des campagnes. Dans une vue globale, les voies secondaires ne sont pas dessinées ou pas nommées, seuls les grands axes apparaissent. Mais lorsqu’on zoome sur une portion plus réduite de la carte, des détails supplémentaires apparaissent : les voies de moindre importance qui n’étaient pas visibles en vue globale, ainsi que les noms des voies. La quantité d’informations affichées dépend donc du niveau de zoom. Le format numérique permet cette souplesse sans laquelle une carte comportant trop de détails deviendrait difficilement lisible. Le plus connu des services de cartographie en ligne est Google Maps mais il existe d’autres alternatives comme le Géoportail et OpenStreetmap.
Une superposition des couches d’informations
Le Géoportail est le portail national territorial français mis en œuvre par l’IGN (Institut Géographique National). Il est consultable à l’adresse web suivante : https://www.geoportail.gouv.fr/.
Cet outil cartographique français propose différents fonds de carte (cartes classiques, topographiques, géologiques parcelles cadastrales, photographies aériennes). Il est possible de superposer des fonds de carte et si nécessaire de moduler l’opacité de chaque couche de données pour les visualiser simultanément.
On peut choisir de superposer les fonds de carte « photographies aériennes » et « parcelles cadastrales ».
De nombreuses données thématiques sont également disponibles. Ces données permettent de compléter et d’enrichir les fonds de carte.
Les données thématiques sur l’éducation et la recherche permettent de matérialiser sur le fond de carte les différents établissements scolaires (écoles maternelles, collèges et lycées) ainsi que les établissements d’enseignement supérieur. Les données thématiques sur les sports et loisirs permettent de matérialiser sur le fond de carte les différents complexes sportifs, terrains de sport, piscines et stades. En juxtaposant sur une même carte les données d’éducation et celles sur les installations sportives, on peut évaluer la proximité entre les structures éducatives et les structures sportives.
La collaboration au service de la cartographie numérique
OpenStreetMap est un projet collaboratif qui a pour objectif de créer une base ouverte de données géographiques que des contributeurs volontaires dans le monde entier peuvent modifier et alimenter.
Le 12 janvier 2010 Haïti subissait un violent séisme, OpenStreetMap a décidé de porter secours à sa manière : les internautes ont mis à jour la carte de Port-au-Prince (la capitale d’Haïti) afin de la rendre la plus précise possible. En seulement 48 heures, la communauté OSM (abréviation d’OpenStreetMap) a créé une carte avec toutes les indications permettant aux ONG de se mobiliser. Des bénévoles sur place ont renseigné des données utiles comme la présence des barrières, l’emplacement des bâtiments effondrés et des centres de secours.
La carte de Port-au-Prince dans OpenStreetMap avant le séisme, Mikel Maron, 2010
La carte de Port-au-Prince dans OpenStreetMap après la mise à jour des internautes, Mikel Maron, 2010
Comment contribuer à OpenStreetMap ?
Pour cartographier en utilisant OpenStreetMap, le meilleur outil pour commencer est l’Editeur iD facile à manipuler. Il suffit de créer un compte sur openstreetmap.org (https://www.openstreetmap.org), ensuite, il faut cliquer sur « modifier avec iD ».
Si l’éditeur détecte des erreurs, une icône d’avertissement apparaît dans la partie droite de l’écran. Vous devrez alors vérifier toutes les modifications faites.
Enfin, lorsque vous êtes sûr des modifications cliquez sur « upload » ou « sauvegarder » et n’oubliez pas de préciser en commentaire toutes les modifications apportées.
Les cartes numériques nécessitent des actualisations régulières pour être maintenues à jour et refléter les changements survenant dans le monde réel. C’est un enjeu majeur pour les éditeurs de cartes, qui peut avoir des conséquences très directes dans le monde réel.
Si la fermeture d’un bureau de poste non reflétée sur la carte est un simple désagrément pour un usager, un changement de sens de circulation d’une rue non répertorié peut faire perdre un temps précieux à une ambulance.
L’un des plus grands avantages des cartes interactives est qu’elles permettent de calculer l’itinéraire le plus court ou le plus rapide entre une adresse de départ et une adresse d’arrivée. De nombreux outils tels que l’Open Source Routing Machine proposent cette fonctionnalité de calcul d’itinéraire. Ces outils reposent sur des algorithmes spécialisés comme celui de Dijkstra.
Calcul du plus court chemin : l’algorithme de Dijkstra
L’algorithme de Dijkstra est un algorithme qui sert à calculer le plus court chemin entre deux sommets dans un graphe pondéré, orienté ou non. Cet algorithme porte le nom de son inventeur, l’informaticien néerlandais Edsger Dijkstra. La notion de plus court chemin s’entend par rapport au poids des arêtes du graphe. Dans le cadre d’un itinéraire routier, ce poids peut représenter une distance kilométrique, un temps de parcours, ou encore une consommation de carburant. Cette même logique est applicable aux problématiques de routage de données informatiques sur des réseaux. Un graphe est un ensemble de sommets liés par des arêtes. Il est dit orienté lorsque ses arêtes ont une origine et une extrémité : ce sont alors des arcs, que l’on les schématise avec des flèches unidirectionnelles. Il est pondéré lorsque chaque arête ou arc est affecté d’un nombre réel positif nommé poids.
Soit un réseau routier reliant 5 villes. Nous voulons emprunter le plus court chemin à partir de la ville pour arriver à la ville .
Modélisation
Nous allons modéliser le réseau routier par un graphe orienté pondéré :
Algorithme
Notation : nous notons la case la case de la ligne et de la colonne .
On construit un tableau dont la ligne contient tous les sommets du graphe.
La ligne est une ligne d’initialisation : la case correspondant au sommet est initialisée à et les cases correspondant aux autres sommets sont initialisées à (infini).
La notation signifie que l’on peut atteindre le sommet après du sommet de départ.
La valeur minimale dans la ligne est . se trouve dans la case . On grise toutes les cases en dessous de cette case.
On remplit la case par le sommet de départ .
On met à jour la ligne .
Dans la case on note la distance . La notation signifie que l’on peut atteindre le sommet en parcourant à partir du sommet .
Dans les cases et on garde , car les sommets et ne sont pas liés à par un chemin direct.
Dans la case on note la distance . La notation signifie que l’on peut atteindre le sommet en parcourant à partir du sommet .
Griser, ou barrer, signifie que l’on a atteint le plus court chemin vers , il s’agit du chemin direct de distance .
On met le sommet dans la case .
Ici, les colonnes et ont été grisées. On ne s’intéressera plus à ces deux colonnes dans les étapes suivantes. Pour mettre à jour la case on calcule la distance séparant de en passant par . On a . On compare à la valeur qui se trouve dans la case .
Pour arriver en on dispose en effet de deux options.
Pour mettre à jour la case on calcule la distance séparant de en passant par .
On a . On compare à qui se trouve dans la case .
représente le plus court chemin, on garde cette valeur dans la case .
Pour mettre à jour la case on calcule la distance séparant de en passant par .
On a . On compare à qui se trouve dans la case . représente le plus court chemin, on garde cette valeur dans la case .
La valeur minimale dans la ligne est et elle correspond au sommet . On grise toutes les cases en dessous de la case contenant . Griser signifie que l’on a trouvé le plus court chemin vers ; il s’agit de la suite d’arêtes de distance .
On met le sommet dans la case .
Pour la case , il n’y a pas de chemin direct (arête unique) entre et . Le plus court chemin vers , à partir de , reste celui en passant par . La case garde la valeur déterminée à l’étape précédente.
Pour mettre à jour la case , on calcule la distance séparant de en passant par . On a . On compare à qui se trouve dans la case . Les deux distances sont égales, la case garde donc la valeur .
Pour mettre à jour la case , on calcule la distance séparant de en passant par . On a . On compare à qui se trouve dans la case . Le plus court chemin pour arriver à est celui passant par . On garde la valeur dans la case .
Interprétation du tableau
À partir du tableau ci-dessus nous pouvons générer tous les courts chemins dont le point de départ est et le point d’arrivée est , , ou .
Conclusion :
La cartographie repose sur toute une gamme de techniques et de connaissances. Grâce au format numérique, il est devenu plus aisé de cartographier, notamment, en améliorant des cartes open-source comme OpenStreetMap. Avec son éditeur iD basé sur un navigateur web rapide et facile à manipuler, OpenStreetMap est une excellente initiation à la cartographie numérique. En plus d’être accessibles, les cartes numériques permettent le calcul d’itinéraire. Ce calcul d’itinéraire est basé sur des algorithmes dont le plus célèbre est Dijkstra. Appliqué à une carte numérique, cet algorithme permet de proposer à l’utilisateur le chemin le plus court, le plus rapide ou le plus économique entre un point de départ et un point d’arrivée.