Services sur smartphone

Sur Iphone: Réglages > Confidentialité > Services de localisation.

On peut paramétrer les permissions pour chacune des app de son smartphone.

• Booking, Expedia: “pour trouver des hébergements et hôtels près de chez vous”
• Facebook, Instagram: “pour aider à indiquer votre présence dans un lieu, pour être notifié des évènements locaux, pour personnaliser du contenu”
• météo: “quand des épisodes de pluie ou de neige commencent”
• …

Par défaut, de nombreuses applications sont susceptibles de traquer vos données de géolocalisation, afin d’étbalir au mieux votre profil. Voir la video ci-dessous: Un espion dans ma poche?

Voici un exemple de la promesse faite à l’utilisateur: l’incrustation des recommandations en réalité augmentée…

Les cartes numériques

Les services de cartographie numérique, comme geoportail ou openstreetmap mettent à disposition des images géoréférencées, avec plusieurs profondeur de zoom disponibles. A ces cartes sont ajoutés des repères avec des lieux d’intérêt.

Comment gère t-on la profondeur de zoom? Pour une même zone géographique, le service stocke des tuiles: ce sont les images assemblées, centrées autour du point central, proposées à certaines échelles. Seules certaines échelles sont disponibles:

images issue de geoservices.ign.fr

Une carte est donc constituée:

• d’un fond de carte constitué avec des tuiles: il s’agit d’images figurant un fragments de la carte, qui, rassemblées à la façon d’un puzzle, forment le fond de carte.
• des calques, qui ajoutent certaines informations pour enrichir la carte (altimétrie, cadastre,…). Ils ont une transparence.
• de POI: points of interest d’un repère de coordonnées, dont la norme est Dgrés décimaux (DD).

Dans ce dernier exemple, chaque tuile est une image matricielle: elle peut être agrandie mais sans détails supplémentaires jusqu’au chargement d’une nouvelle tuile. Alors que les quadrillages sont toujours aussi nets: ce sont des images vectorielles ajoutées.

image issue de: geoservices.ign.fr

Voir l’activité compléte ici: Lien vers pdf

Géoportail

Les cartes de Géoportail Elles permettent de zoomer, et ainsi de modifier dynamiquement l’echelle, mais aussi de mesurer une surface, créer un itinéraire, … voir ici

Openstreetmap

Les fichiers d’itinéraires sont un autre exemple de données standardisées afin de pouvoir être échangées entre applis de cartes numériques: c’est le format .GPX

Carte et image numérique

Activité sur la structure des cartes numériques

Travaux pratiques

• TP1 Cartographie numerique, marqueurs et cadastre
• TP2 itinéraire et croisière

Calcul d’initéraire

L’ensemble des itinéraires peut être représenté à l’aide d’un graphe pondéré. Les noeuds sont des intersections, souvent des villes, croisements, points d’interêt. Les arêtes sont les routes. Le calcul d’itinéraire se fait à l’aide d’algorithmes prenant de nombreux paramétres en compte. L’itinéraire est alors une liste de coordonnées de noeuds dans ce graphe.

Exemple naïf:

fonction recherche_itineraire(depart, arrivee, graphe):
  ville_courante <- depart
  itineraire.ajouter(ville_courante)
  tant que ville_courante != arrivee:
    ville_courante <- ville_voisine_plus_proche(ville_courante, graphe)
    itineraire.ajouter(ville_courante)
  retourner itineraire

Questions:

1. Quel itineraire est retourné par l’appel de la fonction avec les paramètres suivants: recherche_itineraire("Montpellier", "Lyon", graphe) ?

   

   2. Quel autre itineraire est retourné par l’appel de la fonction avec les paramètres suivants: recherche_itineraire("Lyon", "Montpellier", graphe) ?

   

   3. Cet algorithme donne t-il à coup sûr le chemin le plus court? Pourquoi?

L’algorithme de Dijkstra

On a vu que l’algorithme précédent n’est pas efficace pour trouver le meilleur itineraire. Celui-ci n’assure pas non plus de trouver un itinéraire, car il n’y a pas de retour en arrière possible.

L’algorithme le plus efficace pour la recherche de l’itinéraire le plus court est l'algorithme de Dijkstra (voir ici pour une description plus formelle).

L’idée de cet algorithme est de procéder comme pour un parcours de graphe en largeur. On tient à jour une liste de sommets adjacents, qu’il faudra visiter dans l’ordre. Pour un noeud N visité dans la liste, on ajoute les sommets adjacents à N en fin de liste. Puis on progresse dans la liste.

Mais ici:

• Le graphe est pondéré (les arêtes ont un poids qui correspond à la distance)
• La liste contient pour chaque sommet visité: le noeud et sa distance cumulée au sommet de départ.
• la liste des sommets à visiter est remise à jour, triée par ordre croissant de distance cumulée.

Une présentation en vidéo de cet algorithme:

Documents et liens

• Livre Delagrave, activité 5 page 89 Cartographie numérique pour débutant: blog
• HTTP request make your own map: geoservices.ign.fr

Suite du cours

principe de la geolocalisation