Le labo

Bidouilles et prises de notes en vrac

Accueil > Docs > Server side clustering for GIS

Server side clustering for GIS

mardi 6 décembre 2011, par b_b

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

  1. ajouter un index sur les champs lat et lon de la table spip_gis ;
  2. r56086 réduire le nombre de boucles du squelette qui génère le JSON et utiliser les jointures SQL au maximum ;
  3. utiliser le critère MBRContains() de MySQL Spatial extension pour sélectionner les points contenus dans le viewport ;
  4. 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

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

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

https://github.com/yohanboniface/djangopeople/blob/clientclustering/djangopeople/djangopeople/clustering.py#L47

https://github.com/yohanboniface/djangopeople/blob/clientclustering/djangopeople/djangopeople/static/djangopeople/js/maps.js#L56

Solutions "lourdes" en java

Solr et Elasticsearch peuvent gérer plus de 100 000 points sans problème, mais elles tournent sous java.

http://blog.trifork.com/2013/08/01/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch/