Geohash
Geohash est un système de géocodage des coordonnées géographiques (latitude / longitude) inventé par Gustavo Niemeyer lors de l'écriture du service Web geohash.org, et mis dans le domaine public. Le système est basé sur une fonction de hachage qui subdivise la surface terrestre selon une grille hiérarchique.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Les Geohashes offrent des propriétés telles que la précision arbitraire et la possibilité d'éliminer progressivement les caractères de la fin du code pour réduire sa taille, en perdant peu à peu de la précision.
Conséquence de la dégradation progressive de précision, les lieux à proximité présentent souvent (mais pas toujours) des préfixes similaires: plus un préfixe partagé est similaire, plus les deux endroits sont proches.
Service modifier
Le but du service geohash.org, lancé en , est d'offrir des URLs courts qui identifient les positions sur la Terre, de sorte que leur référencement dans des emails, forums, et sites web soit plus commode.
Pour obtenir le Geohash, l'utilisateur fournit une adresse pour en faire le géocodage, ou les coordonnées de latitude et longitude dans une boîte d'entrée unique, et effectue la demande.
En plus de montrer la latitude et la longitude correspondant au Geohash, le site montre une carte intégrée et permet aux utilisateurs de télécharger un fichier GPX, ou de transférer le point directement à certains récepteurs GPS. Des liens vers des sites extérieurs qui peuvent fournir plus de détails sur l'emplacement sont aussi fournis.
Par exemple, la paire de coordonnées '46.5197601,6.5656802 '(de l'EPFL en Suisse) produit le hash u0k8tksvprv, qui peut être utilisé dans l'URL http://geohash.org/u0k8tksvprv
Utilisation modifier
Les utilisations principales des Geohashes sont :
- Comme identifiant unique ;
- Représenter les points géographiques dans les bases de données.
Les Geohashes ont également été proposées pour être utilisés comme géotags.
Lorsqu'ils sont utilisés dans une base de données, la structure des données geohashées présente deux avantages.
Premièrement, tous les points dans une zone rectangulaire donnée produiront des geohashs en tranches contiguës (le nombre de tranches dépend de la précision requise et la présence de "lignes de faille" geohash). Ceci est particulièrement utile dans les systèmes de bases de données où les requêtes sur un seul indice sont beaucoup plus rapides que plusieurs requêtes distinctes. Deuxièmement, cette structure de l'index peut être utilisé pour une recherche de proximité rapide car les points les plus proches sont souvent parmi les plus proches geohashes.
Exemple modifier
En utilisant le hash ezs42 à titre d'exemple, voici comment il est décodé en une latitude et longitude.
Décodage en base 32 modifier
La première étape est le décodage en Base32 à l'aide de la carte de caractères suivants:
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g | |||
| Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | |||
| Base 32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z | |||
Le résultat donne le code binaire 01101 11111 11000 00100 00010. En comptant à partir de la gauche (le premier bit étant considéré comme 0, soit pair), les bits pairs correspondent à la longitude (0111110000000), tandis que les bits impairs donnent la latitude (101 111 001 001).
Décodage binaire en décimal modifier
Chaque code binaire est ensuite utilisé dans une série de divisions, un bit à la fois, à nouveau de la gauche vers la droite. Pour la valeur de latitude, l'intervalle -90 à 90 est divisé par 2, ce qui produit deux intervalles: -90 à 0, et 0 à 90. Comme le premier bit est égal à 1, l'intervalle choisi est le second, et devient l'intervalle courant. La procédure est répétée pour tous les bits dans le code. Lorsque le code est épuisé, la valeur de la latitude est le milieu du dernier intervalle. Les longitudes sont traitées d'une manière équivalente, en gardant à l'esprit que l'intervalle initial est de -180 à 180.
À la fin de la procédure, on obtient environ 42.6, -5.6 pour ezs42.
Exemple détaillé modifier
Voici un exemple de décodage détaillé de 101111001001 en 42.6. Pour commencer, nous savons que la latitude est quelque part dans la gamme de -90 à 90. En l'absence de bits, nous supposerions une latitude de 0, nous donnant une erreur de ± 90. Avec un seul bit, on peut décider si la latitude se situe dans la gamme de -90 à 0, ou de 0 à 90. Le premier bit étant fort (=1), nous savons que notre latitude est quelque part entre 0 et 90. Sans bits de plus, nous supposerions que la latitude est de 45, avec une erreur de ±45.
Chaque bit suivant réduit de moitié cette erreur. Ce tableau montre l'effet de chaque bit. À chaque étape, la moitié concernée de la gamme est surligné en vert - un bit faible sélectionne la gamme inférieure, un bit fort de la gamme supérieure.
La dernière colonne indique la latitude, il suffit de la valeur moyenne de la plage. Chaque bit suivant rend cette valeur plus précise.
| bit | min | mid | max | val | err |
|---|---|---|---|---|---|
| 1 | -90.000 | 0.000 | 90.000 | 45.000 | 45.000 |
| 0 | 0.000 | 45.000 | 90.000 | 22.500 | 22.500 |
| 1 | 0.000 | 22.500 | 45.000 | 33.750 | 11.250 |
| 1 | 22.500 | 33.750 | 45.000 | 39.375 | 5.625 |
| 1 | 33.750 | 39.375 | 45.000 | 42.188 | 2.813 |
| 1 | 39.375 | 42.188 | 45.000 | 43.594 | 1.406 |
| 0 | 42.188 | 43.594 | 45.000 | 42.891 | 0.703 |
| 0 | 42.188 | 42.891 | 43.594 | 42.539 | 0.352 |
| 1 | 42.188 | 42.539 | 42.891 | 42.715 | 0.176 |
| 0 | 42.539 | 42.715 | 42.891 | 42.627 | 0.088 |
| 0 | 42.539 | 42.627 | 42.715 | 42.583 | 0.044 |
| 1 | 42.539 | 42.583 | 42.627 | 42.605 | 0.022 |
(Les nombres dans le tableau ci-dessus ont été arrondis à 3 décimales pour plus de clarté)
L'arrondi final doit être fait avec soin de façon que:
Donc, si l'arrondi de 42.605 à 42,61 ou 42.6 est correct, l'arrondi à 43 ne l'est pas.
| longueur du geohash | lat bits | long bits | erreur lat | erreur long | erreur en km |
|---|---|---|---|---|---|
| 1 | 2 | 3 | ±23 | ±23 | ±2500 |
| 2 | 5 | 5 | ± 2.8 | ± 5.6 | ±630 |
| 3 | 7 | 8 | ± 0.70 | ± 0.7 | ±78 |
| 4 | 10 | 10 | ± 0.087 | ± 0.18 | ±20 |
| 5 | 12 | 13 | ± 0.022 | ± 0.022 | ±2.4 |
| 6 | 15 | 15 | ± 0.0027 | ± 0.0055 | ±0.61 |
| 7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 |
| 8 | 20 | 20 | ±0.000085 | ±0.00017 | ±0.019 |
Limitations modifier
Une limitation de l'algorithme Geohash apparaît en tentant de l'utiliser pour trouver des points situés à proximité les uns des autres en se basant sur un préfixe commun. Il existe des cas limites ou des endroits proches, mais sur les côtés opposés de l'équateur ou d'un méridien peuvent entraîner des codes Geohash sans préfixe commun[1]
Deuxièmement, un geohash définit essentiellement une zone rectangulaire où se trouve un endroit, donc deux emplacements peuvent être spatialement très proches mais avoir des geohashes différents. Afin d'être utile à des recherches de proximité, les huit zones entourant celle d'un geohash doivent être calculées et les emplacements correspondant à ces zones extraits, ce qui complique l'utilisation pour la recherche de proximité.
En dépit de ces problèmes, il y a des contournements possibles et l'algorithme a été utilisé avec succès dans MongoDB pour les recherches de proximité[2].
Licence et brevets modifier
Le géocode Geohash a été mis dans le domaine public par son inventeur le [3].
Bien que des algorithmes comparables aient été brevetés avec succès [4] ou sont protégés par copyright [5],[6], le Geohash est basé sur un algorithme et une approche complètement différents.
Liens externes modifier
Voir aussi modifier
- le code "OLC" (Open Location Code) / Code Plus
Références modifier
- announcement post in groundspeak.com forum
- Geospatial Indexing in MongoDB
- annonce de geohash.org dans le forum groundspeak.com
- Compact text encoding of latitude/longitude coordinates -Patent 20050023524
- Does Microsoft Infringe the Natural Area Coding System?
- The Natural Area Coding System - Legal and Licensing
