Introduction
Suite à notre évènement Test d’algo, mode d’emploi du 25 janvier, nous avons voulu faire un focus sur le talk de Gérôme Grignon, comment présenter l’algo geohash dans un cas concret.
Pour plus d’informations, nous vous invitons à consulter le replay.
Suite à une reconversion professionnelle, Gérôme Grignon, développeur Front-End chez SFEIR Nantes, nous partage ses connaissances à travers la vulgarisation de l’algo geohash.
Lorsque l’on créé un algorithme, il y a plusieurs étapes d’itération :
- s’assurer qu’il fonctionne correctement
- s’assurer qu’il fonctionne par rapport à nos cas d’usage
- s’assurer que son exécution soit la plus rapide possible
Nous allons prendre le cas concret d’un avertisseur de radar pour montrer comment utiliser l’algorithme geohash.
Un utilisateur en déplacement dans l’espace se retrouve dans différentes positions géographiques. L’objectif de l’avertisseur de radar est de fournir rapidement la localisation des radars à proximité de sa position géographique.
Quand on pense à un accès très rapide à une base de données, on pense directement aux bases de données de type colonne comme Cassandra.
Avec ces bases de données, nous ne pouvons pas comparer plusieurs colonnes, or dans notre cas, nous avons une longitude et une latitude.
Nous devons donc passer d’une représentation de l’espace en 2 dimensions (longitude/ latitude) à 1 dimension.
L’algorithme geohash est un système d’encodage de localisation géographique, il permet de passer d’une longitude et latitude à une chaîne de caractère par exemple.
Pour plus d’informations, vous pouvez retrouver la définition sur wikipédia.
Comment coder un geohash ?
- partir de latitude et notre longitude
- faire l’étape de dichotomie pour arriver à un code binaire
- convertir en base 32 pour arriver à notre chaîne de caractère
Plus que des mots, voici la réalisation
const DECODING_TRANSLATION_MAP = new Map(
[['0', [0]], ['1', [1]], /* ... */ ]);
exports.decode = function(geohash) {
let [minLat, maxLat, minLong, maxLong] = [-90.0, 90.0, -180.0, 180.0];
let computeLong = true;
for (let char of geohash) {
const hashChunk = DECODING_TRANSLATION_MAP.get(char);
for (let bit of hashChunk) {
if (computeLong) {
const midLong = (maxLong + minLong) / 2.0;
if (bit) {
// on garde la partie droite
minLong = midLong;
} else {
// on garde la partie gauche
maxLong = midLong;
}
} else {
const midLat = (maxLat + minLat) / 2.0;
if (bit) {
// on garde la partie inférieure
minLat = midLat;
} else {
// on garde la partie supérieure
maxLat = midLat;
}
}
computeLong = !computeLong;
}
}
return [minLat, maxLat, minLong, maxLong];
}
