Fiche de révision : 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. Mathématiquement, l’échelle est le rapport entre un objet réel et sa reproduction.
• Pour une carte interactive, l’échelle varie d’une manière continue selon le niveau du zoom.
• Le plus connu des services de cartographie en ligne est Google Maps mais il existe d’autres alternatives.
• Le Géoportail est le portail national territorial français mis en œuvre par l’IGN (Institut Géographique National), il propose différents fonds de carte (cartes classiques, topographiques, géologiques parcelles cadastrales, photographies aériennes) et de nombreuses données thématiques (établissements scolaires, complexes sportifs, etc.).
• En juxtaposant sur une même carte les données d’éducation et celles sur les installations sportives, on peut par exemple évaluer la proximité entre les structures éducatives et les structures sportives.
• 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, les internautes ont mis à jour la carte de Port-au-Prince sur OpenStreetMap afin de la rendre la plus précise possible pour permettre aux ONG de se mobiliser.
• Pour cartographier en utilisant OpenStreetMap, l’outil pour commencer est l’Editeur 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.
• 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.

Calcul du plus court chemin : l’algorithme de Dijkstra

• 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.
• 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.
• 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.
• La notion de plus court chemin s’entend par rapport au poids des arêtes du graphe (distance kilométrique, temps de parcours, ou consommation de carburant dans le cadre d'un itinéraire routier).
• On peut 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.
• On commence par l’initialisation : on construit un tableau dont la ligne $0$ contient tous les sommets du graphe.
• Cette initialisation sert à distinguer le sommet de départ des autres sommets.
• Mise à jour de chaque ligne : on met à jour les lignes une par une en remplissant la première case par le sommet de départ et en notant les distances entre chaque sommet.
• À partir d’un tableau comme celui-ci nous pouvons déterminer le plus court chemin entre deux points.