Le laboPourquoi faire du clustering côté serveur ?
La carte du site lestaxinomes.org comporte à ce jour plus de 4 000 points. Le site utilise GIS2 et un squelette perso pour la génération du JSON qui alimente la carte en markers. Le clustering est réalisé côté client à l’aide la librairie MakerClusterer Plus.
Principe de fonctionnement de la carte :
- lors de l’initialisation, le contenu JSON de la carte est récupéré en ajax
- après récupération du JSON, les données sont analysées et traitées par MarkerClusterer Plus pour afficher les markers des clusters et des points
- lors du clic sur un point, le contenu de l’infobulle est récupéré en ajax
Points forts de cette solution :
- Le transfert des données de la carte n’a lieu qu’une seule fois (toutes les données sont envoyées au client au premier hit).
Points faibles de cette solution :
- le squelette qui génère le JSON génère une requête SQL qui doit renvoyer tous les points présents en base ;
- le JSON généré devient de plus en plus lourd et son temps de transfert trop important.
Améliorations possibles :
- extraire du fichier JSON le contenu des infobulles des points et le récupérer en ajax lors du clic sur le marker (appliqué dans le squelette géodiversité, à reporter dans GIS2)
- r56086 réduire le nombre de boucles du squelette qui génère le JSON et utiliser les jointures SQL au maximum
Mettre en place un clustering de markers côté serveur dans GIS
Une solution plus pérenne est de réaliser le clustering de marker directement sur le serveur. Ce genre de solution permet de prendre en charge un gros volume de markers (5 000, 10 000 et plus).
Un branche de test pour GIS2 est disponible sur la zone :
http://zone.spip.org/trac/spip-zone/browser/_plugins_/gis/branches/v2_cluster
Le travail de cette branche est basé sur l’article suivant :
http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps
Principe de fonctionnement de la branche v2_cluster :
- lors du premier affichage, on récupère les données JSON des markers en ajax. La requête passe en paramètre les limites du viewport affichée (coordonnées des points SW et NE de la zone affichée par la carte) ;
- le squelette qui génère le JSON sélectionne uniquement les points contenu dans le viewport (la requête est effectuée de nouveau à chaque changement de viewport, event dragend et zoomend) ;
- un filtre présent dans le squelette qui génère le JSON effectue le travail de clustering des markers en les regroupant suivant la distances qui les séparent.
Améliorations possibles :
- ajouter un index sur les champs lat et lon de la table spip_gis ;
- r56086 réduire le nombre de boucles du squelette qui génère le JSON et utiliser les jointures SQL au maximum ;
- utiliser le critère MBRContains() de MySQL Spatial extension pour sélectionner les points contenus dans le viewport ;
- optimiser le clustering : appliquer le clustering directement dans la requête SQL (possible uniquement avec postgresql) OU stocker les clusters en base.
Quelques liens au sujet du clustering côté serveur
Suite à une discussion avec Fabrice, voici ses notes à ce sujet :
http://www.loceanique.org/spip/article448.html
http://www.loceanique.org/spip/article452.html
Une solution intéressante qui utilise des champs et des fonctions géographiques sous postgre.
*** http://geotribu.net/node/125 ***
Une autre solution intéressante qui stock les clusters en base :
http://web.archive.org/web/20071011143643/http://forum.sydphp.org/?a=topic&t=1074
http://web.archive.org/web/20071121140547/http://trib.tv/tech/clustering-points-on-a-google-map/
D’autres liens en vrac :
http://www.soak.co.uk/blog/server-side-map-marker-clustering/
http://stackoverflow.com/questions/805072/server-side-google-markers-clustering-python-django
http://stackoverflow.com/questions/1434222/map-clustering-algorithm
This script can be used to generate points of an Hilbert curve. It generates points of an Hilbert curve and returns the point in an array. The script implements both the two and three dimension implementations.
http://www.phpkode.com/scripts/item/hilbert-curve/
Technique du plugin drupal Geocluster + geohash
- https://drupal.org/project/geocluster qui utilise la technique de geohash
- https://github.com/ahtih/Geoclustering
- http://drupalcode.org/project/geocluster.git
Well in this example features returned are not the real features (as I dont have the data). These features I create for each tile on ad hoc basis but each time in a tile features are same. This is achieved with Knuth algo, check the php code for simulated tile feature service here.
Résumé visuel de la thèse de l’auteur : http://dasjo.at/files/thesis-poster-dabernig.pdf
À propos de geohash
Fil disait :
les fonctions spécifiques de distance c’est peut-être plus propre comme même, mais l’avantage de geohash c’est que c’est assez naturel :
count(*) et group by substr(geohash,(précision))
et tu as tes clusters direct
- geohash mysql : https://github.com/nowelium/geohash-mysql-func/blob/master/geohash.sql
- geohash php : https://github.com/asonge/php-geohash
One of the techniques used was to use the stats component to compute an average lat/lon of all points in a geohash grid.
Mysql Spatial extension
http://dev.mysql.com/doc/refman/5.0/fr/spatial-extensions.html
http://markmaunder.com/2009/10/10/mysql-gis-extensions-quick-start/
http://www.mysqlfanboy.com/2010/08/mysql-gis-part-1/
Un post avec plein de liens sur le sujet : http://forums.mysql.com/read.php?23,184702,184702#msg-184702
http://dossy.org/2011/09/mysql-geo-distance-code-and-samples/
Calcul de distance avec Sphinx
http://pat.github.io/thinking-sphinx/geosearching.html
http://www.god-object.com/2009/10/20/geospatial-search-using-sphinx-search-and-php/
Quadtree & Slippy map
Slippy map tilenames with PHP : http://wiki.openstreetmap.org/wiki/Slippy_map_tilenames#PHP
Tile Coordinates and Quadkeys : http://msdn.microsoft.com/en-us/library/bb259689.aspx
Une solution d’index maison basée sur Quadtree : http://www.rooftopsolutions.nl/blog/229
https://github.com/ericfischer/datamaps
http://bafford.com/software/aggregate-map-tools/
https://github.com/MarkBaker/QuadTrees
Solutions avec d’autres SGBD
http://gis.stackexchange.com/questions/11567/spatial-clustering-with-postgis
Astuce de ybon
en gros je regroupe les points par tuile en les arrondissant à une grille, puis je prends un point au pif dans la tuile pour représenter le cluster
https://github.com/yohanboniface/djangopeople/commit/9ad5d27f26461ccef62b890bdabc44b1ed8cd320
Solutions "lourdes" en java
Solr et Elasticsearch peuvent gérer plus de 100 000 points sans problème, mais elles tournent sous java.