Cours : Calcul d'itinéraire

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.

Définition

É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.

Exemple

1/50 000 signifie que 1 cm sur la carte représente 50 000 cm sur le terrain.

• Pour une carte interactive, l’échelle varie d’une manière continue selon le niveau du zoom.

À retenir

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.

Exemple

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.

Exemple

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.

• OpenStreetMap est l’équivalent de Wikipédia en cartographie libre.

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.

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 ».

• L’interface permet d’ajouter des points (parking à vélo, borne incendie, distributeur de billets), des polygones (bâtiment résidentiel, bibliothèque, clinique) ou des lignes (voie cyclable, route).
• On peut également afficher les tags relatifs à un point, une ligne ou un polygone. Les tags ou attributs sont toutes les informations utiles dont l’adresse ou le type.
• L’échelle est affichée.
• Le site recense également toutes les personnes ayant contribué à la carte.
• Des paramètres de réglage sont disponibles : activation de la localisation, zoom, le fond de la carte ou l’aide.

Comment ajouter un chemin, un point ou un polygone ?

• Pour ajouter un nœud, il suffit de cliquer sur l’icône « point » puis de placer votre curseur à l’emplacement désiré. En même temps, un formulaire à gauche apparaît. Vous pouvez y renseigner les tags associés au point.
• Pour ajouter une ligne cliquez sur le bouton « line » ou « ligne ». Il est possible de dérouler un menu d’options en cliquant sur le bouton droit de la souris, vous aurez la possibilité de diviser le chemin, de le rendre circulaire ou de le déplacer.
• Pour ajouter un polygone (parc, hôpital, bâtiment), cliquez sur le bouton « area » ou « polygone ». Les couleurs du bâtiment changeront en fonction des attributs ajoutés.

Attention

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.

À retenir

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 $A$ pour arriver à la ville $C$.

Modélisation

Nous allons modéliser le réseau routier par un graphe orienté pondéré :

• chaque sommet porte la lettre initiale de la ville ;
• chaque arc est affecté d’un poids qui représente la distance en kilomètres séparant les deux villes reliées par l’arc.

Algorithme

Notation : nous notons la case $[i][j]$ la case de la ligne $i$ et de la colonne $j$.

• Initialisation

On construit un tableau dont la ligne $0$ contient tous les sommets du graphe.
La ligne $1$ est une ligne d’initialisation : la case correspondant au sommet $A$ est initialisée à $0$ et les cases correspondant aux autres sommets sont initialisées à $\infty$ (infini).

• Cette initialisation sert à distinguer le sommet de départ des autres sommets.

La notation $0(A)$ signifie que l’on peut atteindre le sommet $A$ après $0\ \text{km}$ du sommet de départ.
La valeur minimale dans la ligne $0$ est $0(A)$. $0(A)$ se trouve dans la case $[1][1]$. On grise toutes les cases en dessous de cette case.

• Mise à jour de la ligne $2$

On remplit la case $\lbrack 2\rbrack \lbrack0\rbrack$ par le sommet de départ $A$.
On met à jour la ligne $2$.

Dans la case $\lbrack2]\lbrack2]$ on note la distance $AB = 11$. La notation $11(A)$ signifie que l’on peut atteindre le sommet $B$ en parcourant $11\ \text{km}$ à partir du sommet $A$.
Dans les cases $\lbrack2]\lbrack3]$ et $\lbrack2]\lbrack4]$ on garde $\infty$, car les sommets $C$ et $D$ ne sont pas liés à $A$ par un chemin direct.
Dans la case $\lbrack2]\lbrack5]$ on note la distance $AE = 6$. La notation $6(A)$ signifie que l’on peut atteindre le sommet $E$ en parcourant $6\ \text{km}$ à partir du sommet $A$.

• La valeur minimale dans la ligne 2 est 6(A) et elle correspond au sommet E. On grise toutes les cases en dessous de la case contenant $6(A)$.

Astuce

Griser, ou barrer, signifie que l’on a atteint le plus court chemin vers $E$, il s’agit du chemin direct $AE$ de distance $6\ \text{km}$.

On met le sommet $E$ dans la case $\lbrack 3]\lbrack0]$.

• Mise à jour de la ligne $3$

Ici, les colonnes $1$ et $5$ ont été grisées. On ne s’intéressera plus à ces deux colonnes dans les étapes suivantes. Pour mettre à jour la case $\lbrack 3]\lbrack 2]$ on calcule la distance séparant $B$ de $A$ en passant par $E$. On a $AE + EB = 6 + 4 = 10\ \text{km}$. On compare $10(E)$ à la valeur $11(A)$ qui se trouve dans la case $\lbrack2]\lbrack 2]$.

Pour arriver en $B$ on dispose en effet de deux options.

• Option n°1 : $11(A)$ signifie qu’on peut atteindre $B$ directement à partir de $A$ en $11\ \text{km}$.
• Option n°2 : $10(E)$ signifie qu’on peut atteindre $B$ à $10\ \text{km}$de $A$ en passant par $E$.
• $10(E) $représente le plus court chemin, on garde donc cette valeur dans la case $\lbrack3]\lbrack2]$.

Pour mettre à jour la case $\lbrack3]\lbrack3]$ on calcule la distance séparant $C$ de $A$ en passant par $E$. On a $AE + EC = 6 + 10 = 16\ \text{km}$. On compare $16(E)$ à $\infty$ qui se trouve dans la case $\lbrack2]\lbrack3]$.
$16(E)$ représente le plus court chemin, on garde cette valeur dans la case $\lbrack3]\lbrack3]$. Pour mettre à jour la case $\lbrack3]\lbrack4]$ on calcule la distance séparant $D$ de $A$ en passant par $E$.
On a $AE + ED = 6 + 3 = 9\ \text{km}$. On compare $9(E)$ à $\infty$ qui se trouve dans la case $\lbrack2]\lbrack4]$. $9(E)$ représente le plus court chemin, on garde cette valeur dans la case $\lbrack3]\lbrack4]$. La valeur minimale dans la ligne $3$ est $9(E)$ et elle correspond au sommet $D$. On grise toutes les cases en dessous de la case contenant $9(E)$. Griser signifie que l’on a trouvé le plus court chemin vers $D$ ; il s’agit de la suite d’arêtes $AE –> ED$ de distance $9\ \text{km}$.
On met le sommet $D$ dans la case $\lbrack4]\lbrack0]$.

• Mise à jour de la ligne $4$

Pour la case $\lbrack4]\lbrack2]$, il n’y a pas de chemin direct (arête unique) entre $D$ et $B$. Le plus court chemin vers $B$, à partir de $A$, reste celui en passant par $E$. La case $\lbrack4]\lbrack2]$ garde la valeur $10(E)$ déterminée à l’étape précédente.
Pour mettre à jour la case $\lbrack4]\lbrack3]$, on calcule la distance séparant $C$ de $A$ en passant par $D$. On a $AD + DC = 9 + 7 = 16\ \text{km}$. On compare $16(D)$ à $16(E)$ qui se trouve dans la case $\lbrack3]\lbrack3]$. Les deux distances sont égales, la case $[4][3]$ garde donc la valeur $16(E)$.

• La valeur minimale dans la ligne $4$ est $10(E)$ et elle correspond au sommet $B$. On grise toutes les cases en dessous de la case contenant $10(E)$ puisqu’on a trouvé le plus court chemin menant vers $B$ : la suite d’arêtes $AE->EB$ de distance $10\ \text{km}$.((fleche)) On met le sommet $B$ dans la case $\lbrack5][0]$.

• Mise à jour de la ligne $5$

Pour mettre à jour la case $\lbrack5]\lbrack3]$, on calcule la distance séparant $C$ de $A$ en passant par $B$. On a $AB + BC = 10 + 2 = 12\ \text{km}$. On compare $12(B)$ à $16(E)$ qui se trouve dans la case $\lbrack4]\lbrack3]$. Le plus court chemin pour arriver à $C$ est celui passant par $B$. On garde la valeur $12(B)$ dans la case $\lbrack5]\lbrack3]$.

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 $A$ et le point d’arrivée est $B$, $C$, $D$ ou $E$.

• Pour atteindre $E$ il suffit de se placer à la valeur en bleu $6(A)$ et on sait que l’on va atteindre $E$ directement à partir de $A$ en $6\ \text{km}$.
• Pour atteindre $D$, on se place à la valeur en bleu $9(E)$ et on apprend que l’on doit passer par $E$. Le chemin le plus court vers $D$ est alors : $A-E-D$, sa longueur est $9\ \text{km}$.
• Pour atteindre $B$, on se place à la valeur en bleu $10(E)$ et on apprend que l’on doit passer par $E$. Le chemin le plus court vers $B$ est alors : $A-E-B$, sa longueur est $10\ \text{km}$.
• Pour atteindre $C$, on se place à la valeur en bleu $12(B)$ et on apprend que l’on doit passer par $B$. Le chemin le plus court vers $C$ est alors : $A-E-B-C$, sa longueur est $12\ \text{km}$.