5
06 juin 2009


Introduction


Les solutions de clusterisation pour afficher un grand nombre d'objets sont peu nombreuses et parfois même payantes :

Nous allons voir dans ce tutoriel comment produire notre propre solution de clusterisation.

Comment faire ?


Avant de se lancer dans le développement, je vais essayer de vous expliquer le processus mis en oeuvre afin de clusteriser des éléments stockés en base de données.

Découpage de la carte

Pour clusteriser les données, nous allons découper la carte visible à l'écran (plus un petit peu sur les côtés) en un certain nombre de 'petites' cartes - la carte centrale correspond à la partie visible (le navigateur de l'internaute n'affichera que cette partie centrale).
Le but étant de charger les marqueurs qui sont proches des bords de la carte, afin de fluidifier l'application.

Processus

Le but est de calculer pour chaque 'petite' carte le nombre de marqueurs qu'elle comporte.
Il est nécessaire de définir un nombre à partir duquel nous afficherons un marqueur qui invitera à zoomer (et indiquera le nombre d'éléments contenu dans la 'petite' carte). Si il y a moins de marqueur que ce nombre prédéfini, alors nous pourrons afficher l'ensemble des marqueurs de ce 'petit' bout de carte.

Gestion des événements

A chaque zoom ou chaque déplacement - supérieur à la distance du bord de la carte centrale au bord de l'extension, un appel Ajax demandera au serveur de recalculer les nouveaux éléments.
Le calcul des éléments sur les bords de la carte permet de pré-charger les POI et d'anticiper le déplacement de l'internaute afin de fluidifier l'application.

Passage de paramètres

A chaque événement, il faudra donc envoyer au serveur les coordonnées des bords de la carte afin que celui-ci puisse calculer les POI et les marqueurs et puisse renvoyer le XML correspondant.

Côté client



Création et affichage des marqueurs

Tout d'abord il faut créer une fonction de création de marqueurs. Celle-ci différencie les marqueurs 'simples' des marqueurs 'cluster' avec une affichage différent et un événement spécifique à chacun.

function createMarker(lat,lng,title,icon,cluster){
var point = new GLatLng(lat,lng);
if (!cluster){
icon.image = "./icon/marker/pic.png";
icon.shadow = "./icon/marker/shadow.png";
var mark = new GMarker(point,{icon: icon, title: title});
var infowindow = title;
GEvent.addListener(mark, 'click', function() {
mark.openInfoWindowHtml(infowindow);
});
map.addOverlay(mark);
}
else{
icon.image = "./icon/marker/cluster_marker.png";
icon.shadow = "./icon/marker/shadow.png";
var mark = new GMarker(point,{icon: icon, title: title});
var infowindow = "";
GEvent.addListener(mark, 'click', function() {
map.setCenter(mark.getLatLng(),map.getZoom()+1);
});
map.addOverlay(mark);
}
}

Récupération des marqueurs via Ajax

L'API Google Maps permet d'utiliser la méthode XmlHttpRequest pour faire des appels à un serveur - il s'agit de la méthode GDownloadUrl déjà utilisée dans le tutoriel n°10.

Il faut commencer par supprimer les overlays présents sur la carte :

map.clearOverlays();

Puis récupérer les bords de la carte et le niveau de zoom que nous allons passer en paramètre lors de l'appel au serveur :

var maxY = map.getBounds().getNorthEast().lat();
var minY = map.getBounds().getSouthWest().lat();
var maxX = map.getBounds().getNorthEast().lng();
var minX = map.getBounds().getSouthWest().lng();

Les paramètres sont définis dans l'url :

var urlstr = "./function/getObj.php?maxY="+maxY+"&minY="+minY+"&maxX="+maxX+"&minX="+minX+"&zoomLevel="+zoomLevel;

Enfin la méthode GDownloadUrl qui récupère le XML construit côté serveur en fonction des paramètres et qui appelle la fonction de création de marqueurs ci-dessus.

GDownloadUrl(urlstr, function(data, responseCode){
if (responseCode == 200){
var xmlDoc = GXml.parse(data);
var markers = xmlDoc.documentElement.getElementsByTagName("marker");

var icon = new GIcon();
icon.iconSize = new GSize(24.0,38.0);
icon.shadowSize = new GSize(44.0,38.0);
icon.iconAnchor = new GPoint(12.0,38.0);
icon.infoWindowAnchor = new GPoint(12.0,19.0);

for (i=0;i var latMarker = parseFloat(markers[i].getAttribute("lat_object"));
var lngMarker = parseFloat(markers[i].getAttribute("lng_object"));
if (markers[i].getAttribute("cluster") == 0){
var title = markers[i].getAttribute("title_object");
createMarker(latMarker,lngMarker,title,icon,false);
}
else{
var title = markers[i].getAttribute("nb_marker")+' items - zoom to view (click on marker)';
createMarker(latMarker,lngMarker,title,icon,true);
}
}
}
});

Initialisation de la carte et création des événements

Nous remarquerons qu'après la déclaration des options, nous appelons la méthode getMarker() afin d'afficher les marqueurs pour le niveau de zoom et l'extend par défaut.
Le but de ce tutoriel étant la clusterisation, il est nécessaire de déclarer un événement qui appelle la fonction getMarker() chaque fois que l'utilisateur modifie le zoom de la carte :

GEvent.addListener(map, 'zoomend', function() {
getMarker();
});

Il faut ensuite définir une méthode pour faire une requête au serveur chaque fois que l'utilisateur se déplace sur la carte en dépassant les limites de la 'grande' carte (cf. Comment faire ?).
Pour cela, il faut voir à chaque fin de déplacement (moveend) si la distance entre le nouveau centre et l'ancien centre et supérieure au pourcentage de carte défini - cf. la 'grande' carte et la carte du centre.
Si c'est le cas, alors nous réinitialisons les coordonnées des extend et nous appelons la fonction getMarker().

var centerLat = map.getCenter().lat();
var centerLng = map.getCenter().lng();
var north = map.getBounds().getNorthEast().lat();
var south = map.getBounds().getSouthWest().lat();
var west = map.getBounds().getNorthEast().lng();
var east = map.getBounds().getSouthWest().lng();

GEvent.addListener(map, 'moveend', function() {
var north = map.getBounds().getNorthEast().lat();
var south = map.getBounds().getSouthWest().lat();
var west = map.getBounds().getNorthEast().lng();
var east = map.getBounds().getSouthWest().lng();

var centerMoveLat = map.getCenter().lat();
var centerMoveLng = map.getCenter().lng();

var extendY = Math.abs(north - south)*extendPercent;
var extendX = Math.abs(west - east)*extendPercent;

if ((centerMoveLng > (centerLng + extendX)) || (centerMoveLng < (centerLng - extendX))){
centerLat = map.getCenter().lat();
centerLng = map.getCenter().lng();
north = map.getBounds().getNorthEast().lat();
south = map.getBounds().getSouthWest().lat();
west = map.getBounds().getNorthEast().lng();
east = map.getBounds().getSouthWest().lng();
getMarker();
}

if ((centerMoveLat > (centerLat + extendY)) || (centerMoveLat < (centerLat - extendY))){
centerLat = map.getCenter().lat();
centerLng = map.getCenter().lng();
north = map.getBounds().getNorthEast().lat();
south = map.getBounds().getSouthWest().lat();
west = map.getBounds().getNorthEast().lng();
east = map.getBounds().getSouthWest().lng();
getMarker();
}
});

La variable extendPercent est le pourcentage qui définit les bornes de la 'grande' carte :

var extendPercent = 50 / 100;

Il faudra veiller à ce que ce pourcentage soit le même côté serveur.

Côté serveur



Initialisation des variables

Avant de commencer à aller chercher les éléments en base de données, il convient de préparer le terrain à la construction du fichier XML.
Tout d'abord, définir le pas, l'extend de la carte (cf. côté client) et le nombre max d'objets par cellule à partir duquel on affiche un marqueur clusterisé :

$extendPercent = 50 / 100;
$cluster_number = 5;
$pas = 10;

Notons que nous avons défini également l'extend de carte supplémentaire dans le côté client afin de gérer l'événement sur le déplacement à la souris.

Puis vient le tour des paramètres passés via la fonction GDownloadUrl côté client - les bords de la carte - et profitons-en pour calculer l'extend réel :

$addExtendY = ($_GET['maxY'] - $_GET['minY']) * $extendPercent;
$addExtendX = ($_GET['maxX'] - $_GET['minX']) * $extendPercent;

Reste la partie un peu délicate de calcul des bornes de la 'grande' carte - tout en faisant attention aux coordonnées parfois négatives :

($_GET['maxY'] > 0 ) ? ((($_GET['maxY'] + $addExtendY) > 90) ? $maxY = 90 : $maxY = $_GET['maxY'] + $addExtendY ) : $maxY = $_GET['maxY'] - $addExtendY ;
($_GET['maxX'] > 0 ) ? ((($_GET['maxX'] + $addExtendX) > 180) ? $maxX = 180 : $maxX = $_GET['maxX'] + $addExtendX ) : $maxX = $_GET['maxX'] - $addExtendX ;
($_GET['minY'] > 0 ) ? $minY = $_GET['minY'] - $addExtendY : ((($_GET['minY'] - $addExtendY) < -90) ? $minY = -90 : $minY = $_GET['minY'] - $addExtendY) ;
($_GET['minX'] > 0 ) ? $minX = $_GET['minX'] - $addExtendX : ((($_GET['minX'] - $addExtendX) < -180) ? $minX = -180 : $minX = $_GET['minX'] - $addExtendX) ;

Ainsi nous avons les bornes de la 'grande' carte dans les variables $maxY, $minX, etc.
La syntaxe un peu particulière - ? : - est juste un opérateur ternaire qui évite de faire des longs if then else - http://www.phpsources.org/tutoriel-conditionnel-if-else.htm#part_2. Ici il y en a deux imbriqués.

Enfin il reste à calculer le pas en X et en Y - c'est-à-dire la taille d'une petite cellule :

$pas_largeur = $largeur / $pas;
$pas_hauteur = $hauteur / $pas;

Et l'initialisation du XML via les fonctions du dom :

$dom = new DomDocument('1.0', 'iso-8859-1');
$node = $dom->createElement("markers");
$parnode = $dom->appendChild($node);

Construction du XML

Une fois toutes les étapes précédentes effectuées, il ne reste plus qu'à éditer le fichier XML correspondant à la requête passée côté client.
Le processus est simple : pour chaque cellule - dont nous avons maintenant les bornes - calculer le nombre d'éléments qu'elle contient puis ajouter des marqueurs dans le XML - soit un cluster calculé au centroïde des points de la cellule ou les marqueurs si le nombre de marqueurs dans la cellule est inférieur à la variable définie un peu plus haut.
Parcourons toutes les cellules :

for ($i=0;$i<$pas;$i++){
for ($j=0;$j<$pas;$j++){

Paramétrons la requête spatiale (ici avec PostGIS) pour ne récupérer que les éléments dans la cellule :

$temp1 = $minY + $pas_hauteur * $i;
$temp2 = $minX + $pas_largeur * $j;
$temp3 = $minY + $pas_hauteur * ($i + 1);
$temp4 = $minX + $pas_largeur * ($j + 1);
$coord1 = strval($temp2)." ".strval($temp1);
$coord2 = strval($temp4)." ".strval($temp1);
$coord3 = strval($temp4)." ".strval($temp3);
$coord4 = strval($temp2)." ".strval($temp3);

$sql = "SELECT x(geom_object) as x, y(geom_object) as y, title_object FROM object WHERE ";
$sql .= "Contains (GeometryFromText('POLYGON(($coord1,$coord2,$coord3,$coord4,$coord1))',4326),object.geom_object)";

Là j'avoue n'avoir pas été super efficace : je calcule 4 chaînes de caractères qui définissent les coordonnées de la cellule pour PostGIS. C'est pas la meilleure solution : il y a moyen de se passer du GeometryFromText.

Puis construisons enfin le XML - on différencie le cas où le nombre d'objets par cellule est supérieur à la variable (où on construit un marqueur 'cluster' qui invitera à zoomer dans la partie cliente) :

$res = pg_query($sql) or die(pg_last_error());
$nb_object = pg_num_rows($res);

if ($nb_object <> 0){
if ($nb_object > $cluster_number){
$node = $dom->createElement("marker");
$newnode = $parnode->appendChild($node);

$polygone = "POLYGON((";
$a = 0;
while ($result = pg_fetch_array($res)){
if ($a == 0){
$firstPoint = $result['x']." ".$result['y'];
}
$polygone .= $result['x']." ".$result['y'].",";
$a++;
}
$polygone .= $firstPoint;
$polygone .= "))";

$sql2 = "select x(Centroid(GeometryFromText('".$polygone."',4326))) as x, y(Centroid(GeometryFromText('".$polygone."',4326))) as y";
$res2 = pg_query($sql2) or die(pg_last_error());
$result2 = pg_fetch_array($res2);

$lat = $result2['y'];
$lng = $result2['x'];

$newnode->setAttribute("lat_object", $lat);
$newnode->setAttribute("lng_object", $lng);
$newnode->setAttribute("nb_marker", $nb_object);
$newnode->setAttribute("cluster", 1);
}
else{
while($result = pg_fetch_array($res)){
$node = $dom->createElement("marker");
$newnode = $parnode->appendChild($node);
$newnode->setAttribute("lat_object", $result['y']);
$newnode->setAttribute("lng_object", $result['x']);
$newnode->setAttribute("title_object", stripslashes($result['title_object']));
$newnode->setAttribute("cluster", 0);
}
}
}

Pour la construction du XML se reporter au tutoriel n°10.

Il suffit pour conclure de fermer le XML et de l'écrire :

$xmlfile = $dom->saveXML();
echo $xmlfile;


Code complet






<br /> [Google Maps] 19. Clusterisation côté serveur<br />








pg_connect("host=localhost dbname=****** user=****** password=******");

$extendPercent = 50 / 100;
$cluster_number = 5;
$pas = 10;

$addExtendY = ($_GET['maxY'] - $_GET['minY']) * $extendPercent;
$addExtendX = ($_GET['maxX'] - $_GET['minX']) * $extendPercent;

($_GET['maxY'] > 0 ) ? ((($_GET['maxY'] + $addExtendY) > 90) ? $maxY = 90 : $maxY = $_GET['maxY'] + $addExtendY ) : $maxY = $_GET['maxY'] - $addExtendY ;
($_GET['maxX'] > 0 ) ? ((($_GET['maxX'] + $addExtendX) > 180) ? $maxX = 180 : $maxX = $_GET['maxX'] + $addExtendX ) : $maxX = $_GET['maxX'] - $addExtendX ;
($_GET['minY'] > 0 ) ? $minY = $_GET['minY'] - $addExtendY : ((($_GET['minY'] - $addExtendY) < -90) ? $minY = -90 : $minY = $_GET['minY'] - $addExtendY) ;
($_GET['minX'] > 0 ) ? $minX = $_GET['minX'] - $addExtendX : ((($_GET['minX'] - $addExtendX) < -180) ? $minX = -180 : $minX = $_GET['minX'] - $addExtendX) ;

$dom = new DomDocument('1.0', 'iso-8859-1');
$node = $dom->createElement("markers");
$parnode = $dom->appendChild($node);

$largeur = $maxX - $minX;
$hauteur = $maxY - $minY;

$pas_largeur = $largeur / $pas;
$pas_hauteur = $hauteur / $pas;

for ($i=0;$i<$pas;$i++){
for ($j=0;$j<$pas;$j++){
$temp1 = $minY + $pas_hauteur * $i;
$temp2 = $minX + $pas_largeur * $j;
$temp3 = $minY + $pas_hauteur * ($i + 1);
$temp4 = $minX + $pas_largeur * ($j + 1);
$coord1 = strval($temp2)." ".strval($temp1);
$coord2 = strval($temp4)." ".strval($temp1);
$coord3 = strval($temp4)." ".strval($temp3);
$coord4 = strval($temp2)." ".strval($temp3);

$sql = "SELECT x(geom_object) as x, y(geom_object) as y, title_object FROM object WHERE ";
$sql .= "Contains (GeometryFromText('POLYGON(($coord1,$coord2,$coord3,$coord4,$coord1))',4326),object.geom_object)";

$res = pg_query($sql) or die(pg_last_error());
$nb_object = pg_num_rows($res);

if ($nb_object <> 0){
if ($nb_object > $cluster_number){
$node = $dom->createElement("marker");
$newnode = $parnode->appendChild($node);

$polygone = "POLYGON((";
$a = 0;
while ($result = pg_fetch_array($res)){
if ($a == 0){
$firstPoint = $result['x']." ".$result['y'];
}
$polygone .= $result['x']." ".$result['y'].",";
$a++;
}
$polygone .= $firstPoint;
$polygone .= "))";

$sql2 = "select x(Centroid(GeometryFromText('".$polygone."',4326))) as x, y(Centroid(GeometryFromText('".$polygone."',4326))) as y";
$res2 = pg_query($sql2) or die(pg_last_error());
$result2 = pg_fetch_array($res2);

$lat = $result2['y'];
$lng = $result2['x'];

$newnode->setAttribute("lat_object", $lat);
$newnode->setAttribute("lng_object", $lng);
$newnode->setAttribute("nb_marker", $nb_object);
$newnode->setAttribute("cluster", 1);
}
else{
while($result = pg_fetch_array($res)){
$node = $dom->createElement("marker");
$newnode = $parnode->appendChild($node);
$newnode->setAttribute("lat_object", $result['y']);
$newnode->setAttribute("lng_object", $result['x']);
$newnode->setAttribute("title_object", stripslashes($result['title_object']));
$newnode->setAttribute("cluster", 0);
}
}
}
}
}

$xmlfile = $dom->saveXML();
echo $xmlfile;
?>


Démonstration