Globe, de Robin, publié sous licence Creative Commons by-nc-nd 2.0.

Cartes et Calcul d'itinéraire

Cartes numériques

De nombreux services en ligne permettent de visualiser et manipuler des cartes :

Nous allons manipuler dans cette partie ce dernier service : Géoportail.

Répondez aux questions suivantes. Cherchez bien la réponse avant de regarder la solution ! Sinon, votre travail sera inutile.

  1. Rendez-vous sur Géoportail, et « jouez » un peu avec : recherchez votre maison, le lycée, la maison de vos grands-parents, etc.
  2. Regardez ce tutorial, puis mesurez la superficie de la parcelle cadastrale du lycée. Environ 38000 m²
  3. On souhaite organiser une sortie vers le belvédère de Pipet. En utilisant le menu outils (avec lequel vous avez mesuré la surface du lycée), répondez aux questions suivantes.
    1. Quelle est la distance à vol d'oiseau entre le portail du lycée et le belvédère ? Environ 1,3 km
    2. Quelle est le dénivelé entre le portail du lycée et le belvédère ? Environ 100 m.
  4. En regardant les bons fonds de carte :
    1. Le pont Delattre de Tassigny (devant le musée) existait-il au milieu de XIXᵉ siècle ? Il n'apparait pas sur la carte de l'état-major (1820-1866), donc il n'existait pas encore.
    2. Ce même pont existait-il en 1950 ? Il apparait sur la carte de 1950, donc il existait.
  5. Recherchez ce qu'il y avait à la place de votre maison ou immeuble en 1950 et au XIXᵉ siècle : des champs, des forêts, des habitations, autre chose ?

Calcul d'itinéraire

La plupart des services en ligne de cartes proposent une fonction de recherche d'itinéraire. Entre deux endroits distincts, il existe des milliers, des millions ou des milliards d'itinéraires possibles. Comment l'ordinateur fait-il pour déterminer aussi rapidement le plus court ?

On modélise les cartes par des graphes, où les sommets sont des intersections, et les arêtes sont des routes, et on utilise l'algorithme de Dijkstra (du nom d'un informaticien et mathématicien néerlandais du XXᵉ).

Par exemple, le graphe suivant représente les distances des trajets entre les sept villes de Bourg-en-Bresse, Annecy, Chambéry, Lyon, Grenoble, Saint-Étienne et Valence (les villes ne sont pas correctement positionnées les unes par rapport aux autres, mais cette information n'est pas nécessaire ici). Par exemple, Valence est à 90 km de Grenoble, et à 120 km de Saint-Étienne.

  1. En regardant ce graphe, déterminez l'itinéraire le plus court pour aller de Bourg-en-Bresse jusqu'à Valence ? Bourg-en-Bresse — Annecy — Chambéry — Grenoble — Valence : 330 km.

  2. Regardez la vidéo suivante pour comprendre un algorithme qui permet de résoudre ce problème pour d'énormes graphes.

  3. Retrouvez l'itinéraire le plus court pour aller de Bourg-en-Bresse à Valence en utilisant l'algorithme de Dijkstra expliqué dans la vidéo.