Geohash

Geohash est le nom d'un algorithme, créé en 2008 et déposé dans le domaine public, qui transforme un couple (latitude, longitude) de coordonnées GPS en un code de lettres et chiffres.

L'algorithme de geohash utilise une variante de la base32 avec ces 32 caractères 0123456789bcdefghjkmnpqrstuvwxyz. Le geohash peut donc être traité comme une valeur en base 32, convertible en binaire.

Exemple : dc0de peut se convertir 12,11,0,12,13 (en base 32) soit 01100,01011,00000,01100,01101 en binaire (5 bits)

La valeur binaire est découpée en distinguant 1 bit sur 2 afin de créer 2 autres nombres binaires, le premier étant associé à la longitude, le second la latitude.

Exemple : 0110001011000000110001101 devient 0_1_0_1_1_0_0_0_1_0_0_1_1 (longitude) et _1_0_0_0_1_0_0_0_1_0_1_0_ (latitude)

Les valeurs sont ensuite traitées comme un indicateur de dichotomie selon l'intervalle -180;180 pour la longitude et -90:90 pour la latitude. L'idée est de scinder l'intervalle en 2 à chaque étape et de prendre 0 pour la partie droite et 1 pour la partie gauche. Plus il y a des bits, plus la valeur est précise.

Exemple : La longitude 0101100010011

Exemple : La chaine geohash dc0de correspond à +6.08642578125 ; -55.39306640625

A partir des coordonnées GPS, le géohash se calcule en créant 2 chaines binaires, une pour la longitude et une pour la latitude, par dichotomie des intervalles correspondant. En scindant en 2 parties égales chaque intervalle et en notant 0 l'intervalle de gauche et 1 l'intervalle de droite.

Exemple : Coder une latitude de +12.34 en partant de l'intervalle -90;+90, prendre l'intervalle de droite (noté 1), soit 0;+90, puis l'intervalle de gauche (noté 0) soit 0;+45, puis encore l'intervalle de gauche 0 soit 0;+22.5, etc... jusqu'à obtenir la précision désirée. Idem pour la longitude +12.34 avec l'intervalle -180;+180. Les 2 nombres obtenus sont respectivement 10010001100011001 et 100010001100011001.

A partir des 2 nombres binaires, recomposer un unique nombre binaire composé alternativement d'un bit de la longitude puis d'un bit de latitude

Exemple : 100010001100011001 et 10010001100011001 font 11000001100000011110000001111000011

Convertir le nombre binaire obtenu en base 32 en utilisant les caractères 0123456789bcdefghjkmnpqrstuvwxyz

Exemple : 11000001100000011110000001111000011 en base 2 vaut s60y0y3 dans cette base 32 spéciale