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

vignette vidéo best of 2022 SFEIR

Best of SFEIR 2022 : la vidéo !

Actualités

Découvrez notre Best of 2022 en vidéo Pas facile de faire tenir en un peu plus de 2 min une année d’events, de talks, de certifications, de formations, de partages open source, de nouveaux sites web, de partenariats technologiques toujours...

Lire la suite

L'Oréal x SFEIR : Un Data Catalog pour profiter du potentiel maximal de la data

Actualités, Témoignages

L’Oréal est leader mondial de la cosmétique avec un historique de plus de 110 ans, une présence dans 150 pays, un éventail de produits représentant 35 marques vendues sur la marché international et plusieurs petites marques vendues localement.   Les...

Lire la suite

Le Groupe SFEIR signe un partenariat stratégique avec dbt Labs pour parfaire son expertise dans les outils de transformation de la donnée

Actualités, Communiqués de presse

PARIS, le 09 Janvier 2023 - Le Groupe SFEIR, société de conseil en stratégie numérique et en développement d'innovations technologiques, annonce un partenariat avec dbt Labs, le pionnier de l'ingénierie analytique qui propose une solution de transformation de données, accessible...

Lire la suite

Rejoignez-nous

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

Parlez à un expert

Social

Contact