Problème(s) à résoudre

Quand on veut représenter de très nombreux points sur une carte (plusieurs milliers voire plusieurs dizaine de milliers), deux problèmes principaux se présentent :

1. Pour que la carte soit lisible, il faut limiter le nombre de points affichés. C’est un problème d’interface utilisateur.
2. Il faut aussi optimiser le temps de traitement, sur le serveur, sur le client et le temps de transfert des données sur le réseau, donc limiter le nombre de points transmis.

Lisibilité de la carte

Ce problème peut être pris en compte par un mécanisme de clustering côté client : la carte traite tous les points à représenter et regroupe les points proches en un seul repère visuel sur la carte. Sur Google Maps, des plugins existent pour effectuer ce travail.

Selon la façon dont le regroupement est présenté à l’utilisateur, ce mécanisme peut avoir des limites : comment sont représentés deux points qui sont extrêmement proche au plus important facteur de zoom ?
Google Earth résout le problème est représentant des marqueurs qui s"ouvrent en étoile quand on clique sur le point agrégé. Mais les plugin de clustering sur Google Maps ne s’y attaque pas : deux points très proches apparaîtront toujours sous la forme d’un agrégat sans qu’il y ait moyen de le dissocier.
Dans GMap, le problème est résolu par la fusion des info-bulle qui permet de naviguer dans les points agrégés même s’ils sont confondus. C’est une solution peu coûteuse (le traitement s’effectue côté client au moment où la bulle est affichée) et, à mon avis, très efficace.

Cette approche seule a également des limites du fait de la bande passante et des performances du client (en javascript, donc… pas vraiment performant et très consommateur de RAM). Je n’ai pas fait de tests, mais j’estime qu’un clustering côté client client peut être efficace sur quelques milliers de points mais les performances risques de s’effondrer sur plus de 10 000 points. Pour de tels volume d’information, il faut avoir recours à un clustering côté serveur.

Optimisation du nombre de points transmis

Pour limiter le volume d’information transmis entre le serveur et le client, il faut que ce dernier paramètre ses requêtes par le viewport de la carte, c’est-à-dire les coordonnées des extrémités nord-ouest et sud-est de la carte. Le serveur peut alors effectuer une requête en restreignant les résultats à la zone demandée et renvoyer ces résultats au client.

Si l’utilisateur déplace la carte ou change le zoom, le client devra envoyer une nouvelle requête au serveur pour obtenir les nouveaux points à représenter.

Cependant, si l’utilisateur dézoome complètement jusqu’à afficher le monde entier, il est également nécessaire que le serveur regroupe les points avant de les renvoyer, à défaut de quoi il devra renvoyer tous les points et l’optimisation des performances tombera à l’eau.

Composantes du clustering

Pour résumer les points ci-dessus, le clustering devrait se composer des éléments suivants :

• Sur le client, il faut un moyen de représenter des points agrégés, l’idéal est d’avoir une représentation spécifique des agrégats, éventuellement comportant une mention du nombre de points agrégés (mais ce n’est, à mon avis, pas indispensable), et de permettre d’accéder aux informations de chacun de ces points. La fusion des info-bulles de GMap me semble une bonne approche.
• Sur le client également, il faut que la requête envoyée contienne la zone représentée (coordonnées et zoom) pour permettre au serveur de ne renvoyer que les points qui seront effectivement affichés.
• Sur le serveur, il faut être capable de sélectionner les points correspondants à une zone.
• Sur le serveur également, on doit être capable de regrouper les points aux facteurs de zoom faible pour limiter la quantité d’information renvoyée.

La solution développée ci-dessous répond à chacune de ces exigences par les points suivants :

• Fusion des info-bulles sur le client (mécanisme de GMap) et représentation spécifique des agrégats.
• Le client envoie des requêtes sur des dalles à différentes échelles, ce qui permet d’exploiter efficacement un cache. Le client peut conserver les dalles en mémoire ou les détruire s’il consomme trop de mémoire.
• En base de données, les points sont indexés par des zones géographiques, le serveur peut ainsi directement passer une requête sur la zone correspondant à la dalle et au niveau de zoom demandé.
• Le serveur implémente un cache spécifique, plus pérenne que le cache de SPIP. Il peut éventuellement précalculer les dalles.

Exploiter un cache par des requêtes dallées

Construire des requêtes qui peuvent bénéficier du cache

Si le client envoie des requêtes paramétrées par le viewport (donc un interval de lat/long), il y a potentiellement un très grand nombre de requêtes : un déplacement d’un pixel sur le client, une taille de carte légèrement différente produit des requêtes différentes. Ce n’est pas théoriquement infini mais en tout cas indénombrable. Si on a un cache sur le serveur dont l’entrée est la requête paramétrée, ce cache fonctionnera rarement.

Pour profiter d’un cache, il faut limiter le nombres de requêtes possibles en utilisant un système de dalles : on demande au serveur la dalle n° X. Dans ce cas le cache fonctionnera chaque fois que cette dalle est demandée.

Le problème avec ce fonctionnement est qu’il faudrait mettre sur le client la connaissance du système de dallage, ce qui n’est pas forcément sain puisque c’est avant tout le serveur qui choisit quelle dalles il est capable de servir. Il y a deux solutions pour coutourner ce problème :

• Soit le client envoie effectivement une requête paramétrée par son viewport, donc qui ne passera potentiellement pas aucun cache. Le serveur prétraite cette requête et la converti en n requêtes dallées, bénéficiant du cache, le résultat de ces requêtes est ensuite consolidé en un seul retour qui indique le rectangle effectivement couvert par les dalles.
• Soit le client effectue une première requête pour obtenir du serveur la définition des dalles. Ce peut être à chaque changement du viewport : il envoie son viewport et reçoit la liste des dalles à demander, l’inconvénient est alors qu’on ajoute un aller-retour client-serveur avant les requêtes de dalles. Mais on peut aussi le faire à chaque changement du zoom : pour un nouveau zoom, le client demande au serveur quelles sont les dalles, sur le monde entier, et stocke ces informations. Le volume d’information pour stocker les dalles n’est pas énorme, surtout qu’il peut être donné sous la forme d’une équation.

Je penche pour la solution d’ajouter une requête sur le client, à chaque premier changement de zoom, demandant la définition des dalles pour ce niveau de zoom sous forme paramétrique.

Problème du cache de SPIP

Le cache de SPIP est un peu sensible pour une application de cartographie : à chaque modification de la base de données, tout le cache est invalidé. C’est-à-dire que si vous ajouter une brève non géolocalisé sur votre site, toutes les requêtes de cartographie devront être calculées alors même qu’aucun point n’a été modifié, créé ou détruit.

Si l’on veut vraiment gérer un grand nombre de points avec un temps de réponse très rapide, il faut donc implémenter un système de cache plus pérenne.
Il pourrait y avoir deux solutions :

• Gérer un système de cache qui ne s’invalide que si un objet des tables qui contiennent les points a été modifié. L’inconvénient est que le contenu des bulles d’information peut, lui, être changé par une modification sur d’autres tables.
• Gérer un cache manuel : c’est au webmestre de décider que les dalles doivent être recalculées.

La première solution me semble assez complexe à mettre en oeuvre : il faudrait espionner chaque changement d’objet et déterminer ce que ça invalide, ce qui peut être très complexe vu qu’on ne sait pas, a priori, quelles sont les informations représentées sur un marqueur.
Comme toujours en développement, quand un fonctionnement automatisé est aléatoire, il vaut mieux l’abandonner et s’en remettre à l’intelligence de l’utilisateur. En l’occurence, on peut adopter une attitide mixte :

1. Le système invalide les dalles qui contiennent un point quand celui-ci est créé, modifié ou détruit. Si le point est déplacé, il faut invalidé la dalle dans laquelle il se trouvait et celle dans laquelle il arrive.
2. Dans l’interface privée, l’utilisateur a un moyen d’invalider toutes les dalles s’il estime que les informations sur les points ont été modifiées. On peut aussi proposer une second bouton pour forcer un recalcul du cache, évitant ainsi un recalcul à la première demande.

Pour que l’on puisse gérer ce cache spécifique sur le serveur, il faut que les requêtes soient nommées. C’est-à-dire que le client de désigne pas une requête spécifique (par exemple en indiquant quel squelette doit être appelé pour effectuer la requête), mais qu’il indique seulement un nom de requête connue par le serveur.
Dans la partie privée, on doit avoir une interface qui permet d’associer à un nom de requête tous les paramètres habituellement utilisés côté client.
À cette condition, le serveur est capable de gérer le cache, d’invalider ou de pré-calculer une requête.

Comment répartir les dalles ?

Vaste problème… Je propose d’utiliser un sous-ensemble des dalles indiquées en annexe de la norme WMTS de l’OGC (http://www.opengeospatial.org/stand…), pages 104 et 105 :

Zoom	Scale Denominator	Pixel Size (m)	Pixel Size (degrees)
0	559082264,0287180	156543,0339280410	1,4062500000E+00
1	279541132,0143590	78271,51696402050	7,0312500000E-01
2	139770566,0071790	39135,75848201020	3,5156250000E-01
3	69885283,00358970	19567,87924100510	1,7578125000E-01
4	34942641,50179490	9783,939620502560	8,7890625000E-02
5	17471320,75089740	4891,969810251280	4,3945312500E-02
6	8735660,375448710	2445,984905125640	2,1972656250E-02
7	4367830,187724360	1222,992452562820	1,0986328125E-02
8	2183915,093862180	611,4962262814100	5,4931640625E-03
9	1091957,546931090	305,7481131407050	2,7465820313E-03
10	545978,7734655450	152,8740565703530	1,3732910156E-03
11	272989,3867327720	76,43702828517620	6,8664550781E-04
12	136494,6933663860	38,21851414258810	3,4332275391E-04
13	68247,34668319310	19,10925707129410	1,7166137695E-04
14	34123,67334159650	9,554628535647030	8,5830688477E-05
15	17061,83667079830	4,777314267823520	4,2915344238E-05
16	8530,918335399140	2,388657133911760	2,1457672119E-05
17	4265,459167699570	1,194328566955880	1,0728836060E-05
18	2132,729583849780	0,5971642834779390	5,3644180298E-06

Ce système de dalle, défini par des degrés, fonctionnera sur toutes représentation pour laquelle un rectangle de cartes représenté correspond à un rectangle de lat/long. Pour des client comme OpenLayers qui permet de traiter des projections exotiques, on pourrait avoir des trous sur le bord des cartes.

Je parle d’un sous-ensemble de ces dalles parce qu’il me semblerait lourd de calculer 18 niveaux de dalles.
Au zoom 0, le monde entier est représenté sur un carré de 256 pixels de côté. Au zoom 1, on a 2x2 dalles de 256x256, au zoom 2 4x4 dalles, au zoom Un marqueur de point faisant usuellement 32 pixels de côté, on peut représenter 8x8 marqueurs côte à côte sans qu’ils se superposent. Donc utiliser des dalles aux zooms 0, 3, 6, 9, 12, 15 & 18 suffirait à s’assurer que les marqueur ne se superposent pas en supposant qu’à un niveau de zoom n, les marqueurs sont agrégés sur la dalle n+1.
À noter que, au zoom 18, il n’y a aucun regroupement. Donc ce système de dalles ne requiert de 6 niveaux de regroupement.

En fonction du niveau, les dalles sont donc définies par (chaque dalle fait 256x256 pixels) :

Niveau	Zoom	taille du pixel (degrees)
0	0	1,4062500000E+00
1	3	1,7578125000E-01
2	6	2,1972656250E-02
3	9	2,7465820313E-03
4	12	3,4332275391E-04
5	15	4,2915344238E-05
6	18	5,3644180298E-06

Fonctionnement du regroupement sur le serveur

Le serveur reçoit donc une requête demandant les points sur une dalle. La désignation de la dalle inclu un zoom et un interval en deux dimensions. Ces informations lui permettent de sélectionner les points qui doivent être renvoyés.
Mais après la sélection, les points proches doivent être agrégés. Comment cette agrégation fonctionne-t-elle ?

Il y a en gros deux approches, à laquelle nous allons ajouter un fonctionnement plus original :

• La première approche est de calculer quels points peuvent être regroupés en calculant la distance entre chaque points : dès que deux points sont plus proches qu’un seuil déterminé en fonction du zoom, on les regroupe. C’est théoriquement la meilleure méthode mais elle peut être assez lourde en calcul.
• La seconde approche est de considérer que les points sont associés à des cases et de les regrouper selon ces cases. C’est beaucoup plus rapide puisque le seul calcul est de déterminer dans quelle case se situe un point. C’est aussi moins parfait au niveau de l’interface utilisateur puisque deux points très proches peuvent néanmoins se trouver dans des cases différentes.

Je privilégie la seconde approche pour des raisons de performance : si de plus une indexe les points sur les dalles des différents niveaux indiqués ci-dessus, le traitement se résume à regrouper les points qui sont sur la même dalle de niveau inférieur à celle qui est demandée dans la requête.
Le traitement serait donc le suivant :

1. Quand un point est créé (ou modifié), on l’associe immédiatement aux sept niveaux de dalles suscités,
2. La requête demande les points de la dalle X de niveau n,
3. Le serveur fait une requête sur la base de données pour récupérer les points en incluant seulement un critère de n° de dalle,
4. Le serveur retraite les points en regroupant ceux qui sont sur la même dalle de niveau n+1.

À ce fonctionnement, j’ajouterai une approche plus originale. Pour les points situés sur terre, on peut utiliser un geocoder pour récupérer une adresse "administrative". Le regroupement me semble plus pertinent si, au niveau de zoom adéquat, les points sont regroupés par quartier, ville, département, région, pays, continent. Ainsi, avec un zoom permettant de visualiser l’Europe, on peut voir qu’il y a tant de point en France, tant de point en Allemagne, etc.
Ce mécanisme peut fonctionner exactement de la même façon que celui des dalles indiqué ci-dessus, pour peu que l’on fasse également porter par chaque point différents niveaux de découpage administratif, et pour peu que le geocoder fonctionne bien…
Il comporte l’inconvénient que les découpages adminsitratifs peuvent être imprévisibles et ne correspondent pas forcément à un niveau de zoom homogène au niveau mondial : deux points pourraient être indiqués dans des villes ou des quartier différents alors qu’ils seront indiscernables sur la carte. Il faudra tester ce que ça donne dans différents endroits du monde.