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.

Exemple de grille Geohash

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

Le but du service geohash.org, lancé en février 2008, 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

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

En utilisant le hash ezs42 à titre d'exemple, voici comment il est décodé en une latitude et longitude.

Décodage en base 32

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

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é

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:

$\mathrm {min} \leq \mathop {round} (\mathrm {value} )\leq \mathrm {max}$

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

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

Le géocode Geohash a été mis dans le domaine public par son inventeur le 26 février 2008[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

Références

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.