Client Side Clustering

Author: Richard Brundritt


Applies to: Virtual Earth 6.0


Suppose you have a few thousand points of interest that you would like to display on a Virtual Earth map. If the POIs are all relatively close to one another, as they often are, it can become difficult to select or hover over specific icons on the map because they are constantly hidden behind other icons. One common solution to this problem is server side clustering, in which code is written on the server side to handle grouping of close-together icons to improve usability. However, not everyone has the need for or time to develop a server side application solely for this purpose. As an alternative, when there are less than a few thousand locations on a map, client side clustering can be implemented instead of server side clustering, with limited performance issues.


Clustering basics


Clustering is the process of representing several nearby locations with a single location icon. Clustering is typically done using either a grid model clustering method or an icon overlap algorithm. In this article, we will look at the grid model clustering method, which involves breaking the viewable map into a grid and representing all locations within any given cell of the grid with a single icon.


Importing data


For the example in this article, we are going to load the map data from a GeoRSS file and store the locations in a hidden shape layer. This method makes storing the location data on the client side relatively easy. We also want to create a second layer that will store the clustered data.


The code in Listing 1 loads a Virtual Earth map without displaying any data, stores the data in a hidden layer (baseLayer), and also defines a few global variables which we will need later. 



<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
 <title>Client Side Clustering</title>
 <script type="text/javascript" src="http://dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=6"></script>
 <script type="text/javascript">
 var map = null;
 var mapStyle;
 var baseLayer = new VEShapeLayer();
 var clusterLayer = new VEShapeLayer();
 var zoomLimit = 15;
 var gridSize = 30
 var maxDescription = 5;

 function GetMap()
 {
 map = new VEMap('myMap');
 map.LoadMap();
 var veLayerSpec = new VEShapeSourceSpecification(VEDataType.GeoRSS, "georsstest.xml", baseLayer);
 map.ImportShapeLayerData(veLayerSpec, cluster);
 baseLayer.Hide();
 map.AddShapeLayer(clusterLayer);
 }

 function cluster()
 {}
 </script>
 </head>
 <body onload="GetMap();">
 <div id='myMap' style="position:relative; width:600px; height:450px;"></div>
 </body>
</html>

Listing 1 Importing data into baseLayer


Map Events


When the map is zoomed or panned, we want to catch the appropriate events and ensure that the map displays the clustered locations rather than displaying locations normally. We can catch the two necessary events using the code in Listing 2. 



map.AttachEvent("onchangeview", cluster);
map.AttachEvent("onresize", cluster);

Listing 2 Map events


Both of these events will be thrown when the map is zoomed or panned, or when the map style is changed. We will handle the last scenario later, since there is no need to re-cluster the data if the map style is changed.


Clustering Algorithm


Now that we have the map data stored in a hidden layer, we can implement the clustering algorithm. The first thing we want our clustering function to do is handle the map events that occurred due to the map style changing. If the map style is changed we do not want the function to cluster the data, so we can start out by checking whether the map style was changed and, if so, doing nothing, as shown in Listing 3. 



function cluster()
{
 var theStyle = map.GetMapStyle();
 if(mapStyle != theStyle)
 {
 // The style has changed, so just store the current map style
 mapStyle = theStyle;
 return true;
 }
 .
 .
 .
}

Listing 3 Handle map style change


If the clustering function is called by a map event other than the map style change (i.e. a zoom or a pan) then we want to populate the cluster shape layer with data. First, we need to make sure we are working with an empty layer. This can be done by calling the 



clusterLayer.DeleteAllShapes();

Listing 4 Clearing the cluster layer


In some cases, application designers may setup their application so that the size of the map can be changed by the user. If this is the case then we will need to calculate the size of the viewable map before we can continue. 



var mapView = map.GetMapView();
var bottomRight = map.LatLongToPixel(mapView.BottomRightLatLong);
var mapWidth = parseInt(Math.ceil(bottomRight.x));
var mapHeight = parseInt(Math.ceil(bottomRight.y));

Listing 5 Calculating the map size


We now need to break the map into a grid. We also want to define an array to keep track of the shapes within each grid cell. A structure is used to store the shape data. The code for implementing a clustering grid is shown in Listing 6. 



// Break the map up into a grid
var numXCells = parseInt(Math.ceil(mapWidth / gridSize));
var numYCells = parseInt(Math.ceil(mapHeight / gridSize));

// Create an array to store all the of grid data
var gridCells = new Array(numXCells*numYCells);

// Initialize the grid array with a structure to store the data
for(var i = 0; i < numXCells; i++)
{
 for(var j = 0; j < numYCells;j++)
 {
 gridCells[i+j*numXCells] = {latlong:new VELatLong(0,0), title:"", description:"", length:0};
 }
}

Listing 6 Clustering Grid


We must now iterate through the data in the base layer and populate the gridCells array with shape data. Converting the VELatLong locations in the base layers into Pixel locations makes it easy figure out which grid cell each shape belongs to. If there is more than one location in a grid cell then we will need to combine the title and description information from all the locations.


In theory, the more zoomed out you are the more clustered points there should be in a grid cell. With this in mind, if you are zoomed far out, it makes sense to only display the number of locations represented by a single pushpin in the description of that pushpin. However, if you are zoomed further in, we will want to display all the description information for all the points that are clustered in within a grid cell. All these things are accomplished in the loop shown in Listing 7. 



//Iterate through the shapes in the base layer
for(var cnt = 0; cnt < baseLayer.GetShapeCount(); cnt++)
{
 //convert the shapes latlong to a pixel location
 var shape = baseLayer.GetShapeByIndex(cnt);
 var latLong = (shape.GetPoints())[0];
 var pixel = map.LatLongToPixel(latLong);
 var xPixel = pixel.x;
 var yPixel = pixel.y;

 // Check whether the shape is within the bounds of the viewable map
 if(mapWidth >= xPixel && mapHeight >= yPixel && xPixel >= 0 && yPixel >= 0)
 {
 // Calculate the grid position on the map where the shape is located
 var i = Math.floor(xPixel/gridSize);
 var j = Math.floor(yPixel/gridSize);

 // Calculate the grid location in the array
 var key = i+j*numXCells;

 // Define a standard way to display an individual shape
 if(gridCells[key].length == 0)
 {
 gridCells[key].latlong = latLong;
 gridCells[key].title = shape.GetTitle();
 gridCells[key].description = shape.GetDescription();
 }

 gridCells[key].length++;

 // Allow the contents of all the points in a grid to be 
 // displayed in the infobox of the shape if the user is zoomed 
 // to the predefined limit. This is done to prevent massive 
 // amounts of data from being displayed inside of the infobox.
 if(gridCells[key].length > 1 && map.GetZoomLevel() >= zoomLimit)
 {
 if(gridCells[key].length == 2)
 {
 gridCells[key].description = "<br /><b>" + 
 gridCells[key].title +
 "</b><br />" + 
 gridCells[key].description + 
 "<br /><hr />";
 }

 gridCells[key].title = "There are " + gridCells[key].length + 
 " pins clustered here<br /><hr />";

 gridCells[key].description = gridCells[key].description + 
 "<b>" + shape.GetTitle() + 
 "</b><br />" + 
 shape.GetDescription() + 
 "<br /><hr />";
 }
 }
}

Listing 7 Clustering data into an array


Now that we have all the clustered data stored in an array, we want to iterate through the array and add the clustered data to our cluster layer. If the user is not zoomed in, we want the popup of the clustered pins to display a default message that will consist of the number of clustered locations that pin represents. In the code shown in Listing 8, we also display a different pushpin icon depending upon whether the grid cell contains a single location or clustered locations.


Note that one way of determining where to place the pushpin that represents a cluster of locations is to simply place it at the center of the grid cell. However, if the user zooms in or out or pans the map, the center location of the grid cells will change, thereby changing the location of the clustered push pins. This causes a “jumpy” effect, which can reduce user experience. Instead, what we do in Listing 8 is set the location of the pushpin representing the cluster to the location of the first pushpin in the grid, preventing the “jumpy” effect by ensuring that the location of the cluster pushpin is not tied to the center of the grid cell. 



// Iterate through the clustered data in the grid array
for(var key = 0; key < gridCells.length; key++)
{
 // Set the default infobox message for clustered points that are zoomed out
 if((gridCells[key].length > 1 && map.GetZoomLevel() < zoomLimit) 
 || gridCells[key].length > maxDescription) 
 {
 gridCells[key].title = "There are " + gridCells[key].length + 
 " pins clustered here";
 gridCells[key].description = "";
 }

 // Add a shape to the cluster layer
 if(gridCells[key].length > 0) 
 {
 var clusterShape = new VEShape(VEShapeType.Pushpin, 
 gridCells[key].latlong);
 clusterShape.SetTitle(gridCells[key].title);
 clusterShape.SetDescription(gridCells[key].description);

 if(gridCells[key].length == 1)
 {
 clusterShape.SetCustomIcon("<img src=\'orange_pin.png\'/>");
 }
 else
 {
 clusterShape.SetCustomIcon("<img src=\'orange_pin_cluster.png\'/>");
 }

 clusterLayer.AddShape(clusterShape);
 }
}

Listing 8 Adding clustered data to Cluster Layer


Figure 2 and Figure 3 below show our client-side clustering code in action. Notice how hovering over a pin that represents a cluster of locations gives a list of all the locations in that cluster if there are just a few, but if there are too many locations it simply gives a count.



Figure 2 Zoomed in Clustered Point



Figure 3 Zoomed out Clustered Point


Conclusion


Client Side Clustering works well for scenarios in which you have less than a few thousand locations. If client side clustering is used for extremely large sets of data there is a noticeable performance loss. Client side clustering is ideal when importing your data from collections (GeoRSS, KML, and Windows Live Collections). These collections can only a store a limited number of locations before they become too large for Virtual Earth to handle. When extremely large amounts of data are to be displayed on Virtual Earth maps the data is normally stored in a database. In this case Server Side Clustering is a better solution.


This article was written by Richard Brundritt from Infusion Development. 



<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
 <head>
 <title>Client Side Clustering</title>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">

 <script type="text/javascript" src="http://dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=6"></script>

 <script type="text/javascript">
 var map = null;
 var mapStyle;
 var baseLayer = new VEShapeLayer();
 var clusterLayer = new VEShapeLayer();

 // zoom level where all data is displayed (1-15)
 var zoomLimit = 15;

 // size, in pixels, of the grid
 var gridSize = 30;

 // Limit the number of data discriptions that can be displayed in an infobox
 var maxDiscription = 5; 
 
 function GetMap()
 {
 map = new VEMap('myMap');
 map.LoadMap();

 // Store mapStyle to not reload the data when style changes
 mapStyle = map.GetMapStyle();
 
 // Import GeoRSS data from source
 // All data is stored in a hidden shape layer
 var veLayerSpec = new VEShapeSourceSpecification(VEDataType.GeoRSS, "georsstest.xml", baseLayer); 
 map.ImportShapeLayerData(veLayerSpec, cluster);
 baseLayer.Hide();

 // Second shape layer to store the clustered data
 map.AddShapeLayer(clusterLayer);
 
 // Events caught from map changes
 map.AttachEvent("onchangeview", cluster);
 map.AttachEvent("onresize", cluster);
 }
 
 function cluster()
 {
 // Check to see whether event is due to map style change
 if(mapStyle != map.GetMapStyle())
 {
 // Store the current map style
 mapStyle = map.GetMapStyle();
 return true;
 }
 
 // Remove all pins from the cluster layer
 clusterLayer.DeleteAllShapes(); 
 
 // Calculate the size, in pixels, of the map 
 var mapView = map.GetMapView();
 var bottomRight = map.LatLongToPixel(mapView.BottomRightLatLong);
 var mapWidth = parseInt(Math.ceil(bottomRight.x));
 var mapHeight = parseInt(Math.ceil(bottomRight.y));
 
 // Break the map up into a grid
 var numXCells = parseInt(Math.ceil(mapWidth / gridSize));
 var numYCells = parseInt(Math.ceil(mapHeight / gridSize));
 
 // Create an array to store all the grid data
 var gridCells = new Array(numXCells*numYCells);

 // Initialize the grid array with a structure to store all the data
 for(var i = 0; i < numXCells; i++)
 {
 for(var j = 0; j < numYCells;j++)
 {
 gridCells[i+j*numXCells]={latlong:new VELatLong(0,0), title:"", description:"", length:0};
 }
 }

 // Iterate through the shapes in the base layer
 for(var cnt = 0; cnt < baseLayer.GetShapeCount(); cnt++)
 {
 // Convert the shapes latlong to a pixel location
 var shape = baseLayer.GetShapeByIndex(cnt);
 var latLong = (shape.GetPoints())[0];
 var pixel = map.LatLongToPixel(latLong);
 var xPixel = pixel.x;
 var yPixel = pixel.y;

 // Check to see whether the shape is within the bounds of the viewable map
 if(mapWidth >= xPixel && mapHeight >= yPixel && xPixel >= 0 && yPixel >= 0) 
 {
 // Calculate the grid position on the map of where the shape is located
 var i = Math.floor(xPixel/gridSize);
 var j = Math.floor(yPixel/gridSize);
 
 // Calculate the grid location in the array
 var key = i+j*numXCells;

 // Define a standard way to display an individual shape 
 if(gridCells[key].length == 0)
 {
 gridCells[key].latlong = latLong;
 gridCells[key].title = shape.GetTitle();
 gridCells[key].description = shape.GetDescription();
 }

 gridCells[key].length++;

 // Allow the contents of all the points in a grid to be 
 // displayed in the infobox of the shape if the user is zoomed 
 // into a predefined limt. This is done to prevent massive 
 // amounts of data from being displayed inside of the infobox.
 if(gridCells[key].length > 1 && map.GetZoomLevel() >= zoomLimit)
 {
 if(gridCells[key].length == 2)
 {
 gridCells[key].description = "<br /><b>" + gridCells[key].title + 
 "</b><br />" + gridCells[key].description + "<br /><hr />"; 
 }

 gridCells[key].title = "There are " + gridCells[key].length + " pins clustered here<br /><hr />";
 gridCells[key].description = gridCells[key].description +
 "<b>" + shape.GetTitle() + "</b><br />" + shape.GetDescription() + "<br /><hr />";
 }
 }
 }

 // Iterate through the clustered data in the grid array
 for(var key = 0; key < gridCells.length; key++)
 {
 gridCells[key] = gridCells[key];

 // Set the default infobox message for clustered points that are zoomed out
 if((gridCells[key].length > 1 && map.GetZoomLevel() < zoomLimit) 
 || gridCells[key].length > maxDiscription) 
 {
 gridCells[key].title = "There are " + gridCells[key].length+ " pins clustered here";
 gridCells[key].description = "";
 }

 // Add a shape to the cluster layer
 if(gridCells[key].length > 0) 
 {
 var clusterShape = new VEShape(VEShapeType.Pushpin, gridCells[key].latlong);
 clusterShape.SetTitle(gridCells[key].title);
 clusterShape.SetDescription(gridCells[key].description);
 
 if(gridCells[key].length == 1)
 clusterShape.SetCustomIcon("<img src=\'orange_pin.png\'/>");
 else
 clusterShape.SetCustomIcon("<img src=\'orange_pin_cluster.png\'/>");
 
 clusterLayer.AddShape(clusterShape);
 }
 }
 }
 </script>
 </head>
 <body onload="GetMap();">
 <div id='myMap' style="position:relative; width:600px; height:400px;"></div>
 </body>
</html>

Listing 9 Complete Client Side Clustering code


Copyright 2008. Sponsored by Aptovita   |  Terms Of Use  |  Privacy Statement
Content on this site is generated from the developer community and shared freely for your enjoyment and benifit. This site is run independantly of Microsoft and does not express Microsoft's views in any way.