Google S2 ou l’indexation de la planète

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}).

• 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:)

• 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) :

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

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 * 4³⁰ (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 :

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 :

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 :

(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.

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

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 :

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

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 :

Codage d’une cellule de niveau 30 :

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é :

(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 :

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 :

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.

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.