Géocodage inversé

L'adresse postale reste de nos jours un moyen plus usuel de se repérer dans une ville. Les outils actuels permettant la géolocalisation nous offrent alors un moyen simple de se repérer dans l'espace par reverse geocoding. Ainsi, plutôt que de dire "je me trouve au point GPS 48.8322,2.356417", il sera plus aisé de dire "Je me trouve proche de la place d'Italie".

D'une manière étendue, le reverse geocoding offre aussi un moyen simple de savoir si une adresse se trouve dans un secteur préalablement délimité. En effet, dans ce cas particulier, l'adresse commencera par être géocodée, puis les coordonnées ainsi calculées seront utilisées dans un reverse géocoding pour déterminer le secteur auquel appartient cette adresse.

Finalement, le géocoage inversé est utile pour un certain nombre de services basés sur la localisation (Location-based service en anglais). Le processus permet de détecter les points d'intérêt autour de l'usager (magasins, restaurants, ...), ses destinations et ses activités[1].

Tout comme un géocodeur doit être capable de fournir le géocodage d'une adresse pour différents niveaux de qualité (voir Géocodage), un reverse geocoder doit être capable à partir de coordonnées de retourner :

1. un point d'intérêt, accompagné de son adresse. Par exemple, la Tour Eiffel.
2. une adresse complète, au numéro. À noter que le numéro peut dépendre du côté de la voie.
3. une adresse partielle, sans numéro.
4. un arrondissement ou une commune ou une municipalité régionale de comté
5. un département, une province, une région
6. un pays
7. tout autre zonage métier considéré. Par exemple, l'appartenance d'une adresse à une zone d'activité commerciale.

On distinguera ainsi parmi les éléments précédents la topologie suivante :

1. les adresses issues d'éléments ponctuels. Il s'agit notamment des points d'intérêt, mais aussi des plaques d'adresse que l'on trouve dans des référentiels tels que celui de l'IGN ou l'Institut d'études géologiques des États-Unis.
2. les adresses issues d'éléments linéaires. Il s'agit notamment des tronçons de voie, mais pourquoi pas des rivières ...
3. les adresses issues de zones. Il s'agit des communes, départements, provinces, etc ...

A contrario du géocodage, la recherche d'un élément s'effectue ici par requête topologique. Toutefois, d'une manière similaire aux solutions rencontrées pour le géocodage, les coordonnées proposées correspondent rarement aux coordonnées exactes du point recherché. Ainsi, la requête topologique porte sur les éléments les plus proches en distance du point sollicité. Selon la topologie d'éléments recherchés, la requête topologique peut alors s'exprimer sous différentes formes :

1. la distance entre deux points.
2. la distance entre un point et un segment (pour simplifier). Il s'agira alors de la distance entre ce point et sa projection sur le segment. À voir si la solution est retenue tout de même lorsque la projection du point est en dehors du segment.
3. l'inclusion d'un point dans un polygone. Il s'agira dans ce cas de la résolution d'un ensemble d'inéquations.

Une fois ces éléments identifiés pour une distance seuil spécifiée, on peut se poser la question de la pertinence de leur présentation. La présentation de ces résultats dépendra ici du contexte d'utilisation : vitesse, objet du géocodage inversé.

Par exemple, considérons le géocodage inverse de "48.8322,2.356417". Nous pourrions obtenir comme résultats :

1. 2 place d'Italie 75013 PARIS
2. place d'Italie 75013 PARIS
3. 75013 PARIS
4. PARIS
5. FRANCE

Un piéton s'attendra par exemple à retrouver les deux premiers résultats, et ignorera généralement le dernier. Leur pertinence pourrait être remise en cause aux frontières des arrondissements ou de la commune. Enfin, l'affichage des deux premiers résultats n'aurait pas de sens à bord d'un avion, à contrario des deux derniers.

Les techniques d'optimisation de reverse geocoding se rapprochent des techniques d'optimisation des moteurs physiques de calcul de collision. Une optimisation simple consiste à effectuer une recherche sur un objet simplifié dans un premier temps pour diminuer le nombre de candidats, puis à effectuer le calcul réel.

Ce principe est notamment efficace pour les recherches d'inclusion dans un polygone ou de collision avec un tronçon, l'un comme l'autre pouvant être simplifié sous la forme d'un rectangle englobant. Un rectangle englobant en 2D nécessite un maximum de 4 tests pour s'assurer de la collision. Des techniques d'indexation des rectangles englobants permettent alors d'assurer un bon niveau de performance.