Tout le monde ou presque a eu l’occasion d’utiliser Google Maps pour explorer un lieu ou pour obtenir un itinéraire. Dans cette simple application, nous avons la quintessence de plusieurs technologies de pointe dont le GPS n’est que la partie émergée de l’Iceberg.

En effet, comment fournir à l’utilisateur final la carte qui le concerne parmi les millions (milliards ?) de possibilités en un temps très court ? En somme, comment indexer les données cartographiques de la planète de façon rationnelle et efficace ?

C’est à cette dernière problématique à laquelle répond Google S2.

 

Comment stocker des données géographiques de façon optimale ?

Une approche naïve serait de stocker chaque objet  cartographique (point d’intérêt, route, montagne, arbre, etc.) d’après ses coordonnées géographiques : latitude et longitude. On pourrait, par exemple, dire que tel point d’intérêt est dans le quadrilatère ({Lat1, Lng1}, {Lat2, Lng2}).

Google S2 ou l’indexation de la planète

  • Problème 1 : cela fait 4 coordonnées de type double à stocker en base.
  • Problème 2 : si j’ai une zone de coordonnées ({LAT1, LNG1}, {LAT2, LNG2}), comment savoir quels sont les objets qui en font partie (cas A et B ci-dessous:)

Google S2 ou l’indexation de la planète

  • Problème 3 : comment traiter le cas de C ? L’objet fait-il partie de la zone ou pas ?
  • Problème 4 : l’objet A doit-il apparaître à notre niveau de zoom ?

On ne pourra résoudre ces problématiques qu’au prix de calculs trigonométriques, ce qui est loin d’être optimum pour une indexation !

Ces questions (et bien d’autres !), les ingénieurs de Google se les sont posées et les ont résolues en créant la librairie S2.

 

Pavage par cellule

En quoi cela consiste-t-il ?

Le globe terrestre est inscrit dans un cube dont chaque face constitue une cellule de plus haut niveau (S0) :

Google S2 ou l’indexation de la planète

Chaque cellule est projetée sur la sphère :

Google S2 ou l’indexation de la planète

 

En vert, une face du cube (une cellule S0), en rouge une subdivision en sous-cellules.

Chaque cellule est subdivisée en 4 sous-cellules sur 30 niveaux, ce qui donne 6 * 430 (6 917 529 027 641 081 856 !) cellules de 1 cm de côté environ.

Si on déplie le cube, avec la projection de la surface terrestre, cela donne ceci :

Google S2 ou l’indexation de la planète

La flèche du bas indique le début de la courbe de Hilbert (voir plus bas).

Selon la position sur le globe, les cellules peuvent être très déformées :

Google S2 ou l’indexation de la planète

 

Sur cette image, on devine le changement de face au niveau de Bordeaux. L’arrondi que l’on observe sur les cellules les plus au Nord est dû à la déformation de la projection de mercator utilisée pour le fond de carte.

Chaque objet cartographique appartient donc à une ou plusieurs cellules :

Google S2 ou l’indexation de la planète

(Par soucis de clarté, le niveau de granularité des cellules est “seulement” le niveau 17, sur les 30 disponibles…).

Donc, nous avons maintenant des objets cartographiques qui appartiennent à des cellules. Il serait facile d’indexer chaque cellule par ses coordonnées cartésiennes : Cellule {1547,1763}.

On progresse, mais il est possible de faire encore mieux.

 

Indexation linéaire

La librairie S2 indexe les cellules selon une courbe fractale de remplissage de surface : la courbe de Hilbert.

Google S2 ou l’indexation de la planète

Appliquée au globe terrestre (en se limitant au niveau 5), on obtient ceci :

Google S2 ou l’indexation de la planète

De par la nature fractale de la courbe de Hilbert, elle couvre chaque point de la planète (ou dans le cas de S2, chaque cm²).

Il est ensuite aisé de faire correspondre chaque point d’une face du cube à une coordonnée sur la courbe de Hilbert :

Google S2 ou l’indexation de la planète

La courbe de Hilbert a également une propriété intéressante. Deux points “proches” en coordonnées sont également proches dans le plan :

Google S2 ou l’indexation de la planète

Chaque cellule de la carte peut donc être représentée par un entier de 64 bits.

Chaque cellule, de différent niveau, est codée de la façon suivante :

Google S2 ou l’indexation de la planète

Codage d’une cellule de niveau 30 :

Google S2 ou l’indexation de la planète

Codage d’une cellule plus large, le 1 suivi de 0 indique le niveau de la cellule.

Mais S2 permet encore plus !

On a vu que pour un objet de type surface, le nombre de cellules utilisées peut être très élevé :

Google S2 ou l’indexation de la planète

(Pavage au niveau S19)

Il serait ruineux de stocker en base que tel objet appartient à ces centaines (milliers, millions, milliards !) de cellules !

Heureusement, S2 permet d’optimiser le pavage :

Google S2 ou l’indexation de la planète

La surface à indexer est la même, mais ici, on a plus qu’une dizaine de cellules à considérer !

On a donc une granularité très fine et très efficace de l’indexation de la terre avec cette méthode. Pour mémoire, les surfaces couvertes par les cellules en fonction de leur niveau :

NiveauSurface minimumSurface maximum
085011012 km²85011012 km²
123,31 km²6,38 km²
300,48 cm²0,93 cm²

 

Applications pratiques

Navigation aérienne

Imaginons un contrôleur aérien qui doit éviter la collision de 2 avions en plein ciel. Pour savoir s’il y a un risque de collision, on peut demander à S2 les cellules (du niveau qu’on jugera intéressant) traversées par chacun des avions. Il suffira ensuite de trouver les cellules communes pour déterminer où les avions doivent voler à des altitudes différentes et éviter la collision.

Google S2 ou l’indexation de la planète

Dans notre cas, on ne gagnera pas forcément de temps, mais si on a des milliers d’avions qui peuvent se croiser, le jeu en vaut la chandelle…

 

Chargement des données de navigation sur itinéraire

Avec une application d’itinéraire, il est intéressant d’envoyer au terminal mobile seulement les données le concernant. Pour cela, on détermine par quelles cellules (d’un niveau qui nous arrange) le trajet passe et il suffira de charger les données (qu’on appelle des tuiles) correspondant à ces cellules.

 

Application commerciales

A tout seigneur, tout honneur, c’est bien évidemment Google Map qui utilise la librairie S2 pour son indexation, mais également MongoDB, OpenStreetMap ou Foursquare.

Dans un domaine moins attendu, les jeux géolocalisés Ingress, Pokemon Go ou Delta T utilisent intensivement la librairie S2 dans leur fonctionnement.