SFEIR

SFEIR

1 Fév, 2022

Comment résoudre l’algo geohash ?

Rubrique

CodeShake | Playoffs

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 : 

  1. s’assurer qu’il fonctionne correctement
  2. s’assurer qu’il fonctionne par rapport à nos cas d’usage
  3. 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 ? 

  1. partir de latitude et notre longitude
  2. faire l’étape de dichotomie pour arriver à un code binaire
  3. 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];

}

Restez informés

Recevez chaque mois nos dernières actus techs et événements à venir.

Social

Un peu de lecture

Rosalie Zandona nommée au poste de People and Culture Manager chez SFEIR

Actualités

  Paris, le 29 août 2022 - SFEIR, société de conseil en stratégie numérique et en développement d'innovations technologiques, annonce la nomination de Rosalie Zandona au poste de People and Culture Manager. RH Manager au sein de SFEIR depuis un...

Lire la suite

SFEIR partenaire de formation Google Cloud pour la région Benelux

Actualités

Après la France, le SFEIR Institute étend son offre de formations aux technologies de Google Cloud à l’international.   Paris, le 20 juillet 2022 – SFEIR, société de conseil en stratégie numérique et en développement d’innovations technologiques, étend son partenariat...

Lire la suite

Le cloud, poumon du SI des entreprises

Actualités

Le cloud, poumon du SI des entreprises Didier Girard, Co-CEO de SFEIR, nous partage sa vision dans une tribune publiée sur IT SOCIAL sur les questions stratégiques d’une entreprise liées au Cloud. Deux grandes tendances se dessinent : le « cloud only »...

Lire la suite

Rejoignez-nous

Première communauté Dev d’Europe
600 développeurs unis par la passion

Parlez à un expert

Social

Contact