SFEIR

SFEIR

1 Fév, 2022

Comment résoudre l’algo geohash ?

Rubrique

CodeShake

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

SFEIR devient partenaire Databricks

Actualités

SFEIR devient partenaire de Databricks   Grâce à ce partenariat, SFEIR renforce son expertise sur la Data, le Machine Learning et l’Intelligence Artificielle.   Paris, le 13 avril 2022 - SFEIR, société de conseil en stratégie numérique et en développement...

Lire la suite

SFEIR poursuit son développement et ouvre une filiale en Belgique 

Actualités

SFEIR poursuit son développement et ouvre une filiale en Belgique    Paris, le 14 février 2022 - SFEIR, société de conseil en stratégie numérique et en développement d’innovations technologiques, annonce la création de sa filiale SFEIR Belgium. Ce sont Nicolas...

Lire la suite

SFEIR accueille Estelle Boyer  au poste de Directrice d’Envision by SFEIR 

Actualités

SFEIR accueille Estelle Boyer au poste de Directrice de Envision by SFEIR    Neuilly sur Seine, le 11 janvier 2021 – SFEIR, société de conseil en stratégie digitale et en développement d’innovations technologiques, annonce l’arrivée d’Estelle Boyer au poste de...

Lire la suite

Rejoignez-nous

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

Parlez à un expert

Social

Contact