Y’a-t-il un GPS dans le Donjon ?

Il était une fois…

L’Antiquité

3 000 av. J.-C.
12 ap. J.C.
150 ap. J.C.

1525
1550
1569

Cartographie moderne
(XV-XVIIIème siècle)

1749

1800
1827

La cartographie moderne
(XIX-XXème siècle)

1922
Année 50
1972

La cartographie de nos jours

La Géomatique

Contraction de géographie et informatique

2 types possibles:

• Données projetées > système de projection
• Données non projetées > Système de coordonnées

Les différents systèmes de projection

Cylindrique	Conique	Azimutale

Système de projection officiel

• Lambert 93 (conique) : en France métropolitaine
• Lambert 2 étendu (conique) : ancienne projection officielle
• UTM (cylindrique) :découpage mondial en 120 zones.

Systeme de coordonnées

• WGS84 : utilisé par les GPS

Comment on calcule une distance ?

Haversine

h = hav(d/r)

const d = haversineDistanceKM(42.806911, -71.290611, 42.741, -71.3161);

const haversineDistanceKM = (lat1Deg, lon1Deg, lat2Deg, lon2Deg) => {
    const toRad(degree) => degree * Math.PI / 180;

    const lat1 = toRad(lat1Deg);
    const lon1 = toRad(lon1Deg);
    const lat2 = toRad(lat2Deg);
    const lon2 = toRad(lon2Deg);

    const { sin, cos, sqrt, atan2 } = Math;

    const R = 6371; // earth radius in km
    const dLat = lat2 - lat1;
    const dLon = lon2 - lon1;
    const a = sin(dLat / 2) * sin(dLat / 2)
            + cos(lat1) * cos(lat2)
            * sin(dLon / 2) * sin(dLon / 2);
    const c = atan2(sqrt(a), sqrt(1 - a));
    const d = 2 * R * c;
    return d; // distance in km
}

La théorie des graphes

Leonard “the GOAT” Euler

1707 ~ 1783

🇨🇭

S – A + F = 2

Edsger Dijkstra

1930 ~ 2002

🇳🇱

Algorithme de Dijkstra

1959

Plus court chemin entre 2 points

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <-- 3 --> id2(F)
  id1(A) <-- 15 --> D <-- 2 --> E <-- 14 --> id2(F)
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B
  B <-- 4 --> E
  C <-- 3 --> id2(F)
  D <-- 5 --> C
  D <-- 2 --> E
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

Algorithme A*

Peter Hart, Nils Nilsson, Bertram Raphael

1968

Dijkstra++

On ajoute estimation “vol d’oiseau”

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <-- 3 --> id2(F)
  id1(A) <-- 15 --> D <-- 2 --> E <-- 14 --> id2(F)
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B == 16 ==> id2(F)
  id1(A) <-- 15 --> D == 13 ==> id2(F)
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <-- 3 --> id2(F)
  id1(A) <-- 15 --> D <-- 2 --> E <-- 14 --> id2(F)
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <== 3 ==> id2(F)
  E == 2 ==> id2(F)
  B <-- 4 --> E
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <-- 3 --> id2(F)
  id1(A) <-- 15 --> D <-- 2 --> E <-- 14 --> id2(F)
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B <-- 4 --> E
  D <-- 2 --> E
  E <-- 14 --> id2(F)
  D == 15 ==> id2(F)
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

flowchart LR
  id1(A) <-- 7 --> B <-- 13 --> C <-- 3 --> id2(F)
  id1(A) <-- 15 --> D <-- 2 --> E <-- 14 --> id2(F)
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

Bien plus rapide, non ?

flowchart LR
  id1(A) <-- 7 --> B <-- 4 --> E <-- 14 --> id2(F)
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

Comparaison

https://www.youtube.com/watch?v=BR4_SrTWbMw

Dijkstra

flowchart LR
  id1(A) <-- 7 --> B
  C <-- 3 --> id2(F)
  D <-- 2 --> E
  B <-- 4 --> E
  D <-- 5 --> C
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

=> 7 + 3 + 2 + 4 + 5 = 21

A*

flowchart LR
  id1(A) <-- 7 --> B <-- 4 --> E <-- 14 --> id2(F)
  style id1 fill:#0F0
  style id2 fill:#F00,color:#fff

=> 7 + 4 + 14 = 25

VRP

Aller d’un point A à un point B en passant par …

=> Permutations

Un système de positionnement global par satellite est composé par 3 éléments (appelés segments) :

• spatial : des satellites en orbite autour de la Terre
• contrôle : des stations de contrôle au sol
• utilisateur : les récepteurs GPS des utilisateurs

Un GPS fournit donc

• les coordonnées géographiques en 3D : longitude, latitude, altitude
• la vitesse de déplacement de l’utilisateur
• la date et heure.

Le plus connu

Un des plus vieux

Le plus utilisé

Le challenger

Les orientés Business

• ESRI
• GraphHopper
• MapBox

“Merci TomTom pour ton blabla, on va taper le boss maintenant ?”

“Allez, c’est parti !”

“Attends, j’ai plus de popo de soins, on peut faire un itinéraire qui va chez le marchand puis au boss ?”

“Pas de souci !”

🫶

Merci à tou•te•s