SFEIR

SFEIR

1 Fév, 2022

Comment résoudre l’algo geohash ?

Rubrique

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

SFEIR reconnu Google Cloud Training Partner of the Year 2024 pour la région EMEA

Actualités, Communiqués de presse

Neuilly-sur-Seine, le 8 Avril 2024 - Le Groupe SFEIR, leader en conseil en stratégie numérique et en développement d'innovations technologiques, est fier d'annoncer avoir reçu le prestigieux titre de Google Cloud Partner of the Year 2024 dans la catégorie Formations...

Lire la suite

Accélération sur la Data : Florent Legras devient CTO Data

Actualités, Communiqués de presse

Neuilly-sur-Seine, le 6 mars 2024 – Le Groupe SFEIR, cabinet indépendant de conseil et d’expertise technologique, est fier d'annoncer la nomination de Florent Legras au poste de CTO Data. Cette nomination souligne l'importance stratégique que le Groupe accorde à l'expertise...

Lire la suite

SFEIR devient partenaire de services AWS de niveau Advanced

Actualités, Communiqués de presse

Neuilly-sur-Seine, le 4 décembre 2023 - Le Groupe SFEIR, société de conseil en stratégie numérique et en développement d'innovations technologiques annonce avoir passé une nouvelle étape dans son partenariat avec le Cloud provider AWS via l’obtention du statut de Partenaire...

Lire la suite

Parlez à un expert

Social

Contact