31 January, 2010 19:39
Clustering points for Silverlight Bing maps control
Posted by mimo under [ C# .net development ][ (0) Comment ] | [ (0) Trackbacks ]
We are now finally underway building the first version of what will become the Menome system.
One of the things we needed was a way of clustering points on a map. The idea is to reduce the number of points as the user zooms out by combining points together to keep performance up and to reduce map clutter.
The algorithm operates by creating a 'screen grid' and passing this to the server. As the user zooms and moves around the map, the boundary window they are looking at in lat/long, the height and width of the current window in pixels and the zoom level are passed to the server.
The first level of filtering happens on the SQL server by doing an intersection of the boundary window with the point geography stored in the SQL server.
Points inside the boundary are returned to the web server, where above a given zoom threshold (10 for now), they are passed through the clustering class. The clustering class works by creating a grid out of the current window. Two nested loops are created, which loop through the grid cells. Each points coordinates converted from lat/long to pixel, and checked against the current grid cell. Points found in the same grid cell are grouped together into a single point, and stored into the grid cell list indexed by the X and Y cell index multiplied together.
Fortunately, Johannes Kebeck has posted an algorithm for doing this on his fantastic blog The algorithm he presents is setup to return javascript, and is written in VB, so we changed it slightly to return a SiteLocationPoint object and to operate in C#, since that is the language we are using for the application we are building.
We have turned this into a class, which takes a list of points, and returns a list of clustered points. The main change we had to make to the algorithm itself was modifying the it to use a Dictionary to store the clustered points in the gridCells object instead of a jagged array, which cannot be declared dynamically in C#.
We used a dictionary with the X*Y grid cell as a key for storing/extracting points in a given grid cell. The other modification we need to make, which I will post once we figure it out, is a way of changing the clustering density.
Click more to get the source code.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Collections;
namespace Matrix.Web.SiteManager
{
public class ClusterSitePoints
{
private const int GridSize = 40;
//Constants for the Clustering
//(addressable area in Bing Maps)
private const double MinLatitude = -85.05112878D;
private const double MaxLatitude = 85.05112878D;
private const double MinLongitude = -180D;
private const double MaxLongitude = 180D;
public ClusterSitePoints(double north, double west, double south, double east, long mapWidth, long mapHeight, long mapZoomLevel, List<MatrixSiteLocationPoint> pointsToCluster)
{
this.east = east;
this.west = west;
this.north = north;
this.south = south;
this.mapHeight = mapHeight;
this.mapWidth = mapWidth;
this.mapZoomLevel = mapZoomLevel;
this.pointsToCluster = pointsToCluster;
}
public List<MatrixSiteLocationPoint> ClusterPoints()
{
List<MatrixSiteLocationPoint> clusteredPoints = new List<MatrixSiteLocationPoint>();
long numberOfCellsX = Convert.ToInt64(Math.Ceiling(Convert.ToDouble(this.MapWidth) / GridSize));
long numberOfCellsY = Convert.ToInt64(Math.Ceiling(Convert.ToDouble(this.MapHeight) / GridSize));
long numberOfCells = numberOfCellsX * numberOfCellsY -1;
//MatrixSiteLocationPoint[numberOfCells][] gridCells = new MatrixSiteLocationPoint[][] { };
//ArrayList gridCells = new ArrayList();
Dictionary<int, MatrixSiteLocationPoint> gridCells = new Dictionary<int, MatrixSiteLocationPoint>();
//Array MatrixSiteLocationPoint = Array.CreateInstance(typeof(MatrixSiteLocationPoint),
long ulTotalX = 0;
long ulTotalY = 0;
LatLongToPixel(this.North, this.West, this.MapZoomLevel, ref ulTotalX, ref ulTotalY);
long poiTotalX = 0;
long poiTotalY = 0;
long poiMapX = 0;
long poiMapY = 0;
foreach (MatrixSiteLocationPoint point in this.PointsToCluster)
{
LatLongToPixel(Convert.ToDouble(point.Latitude), Convert.ToDouble(point.Longitude), this.MapZoomLevel, ref poiTotalX, ref poiTotalY);
poiMapX = poiTotalX - ulTotalX;
poiMapY = poiTotalY - ulTotalY;
// populate array with clustered points
for (int x = 0; x < numberOfCellsX - 1 ; x++)
{
if(( x * GridSize <= poiMapX) && (poiMapX < (x + 1) * GridSize))
{
for (int y = 0; y < numberOfCellsY - 1 ; y++)
{
if ((y * GridSize <= poiMapY) && (poiMapY < (y + 1) * GridSize))
{
MatrixSiteLocationPoint clusterPoint = null;
if (gridCells.ContainsKey(x * y))
{
clusterPoint = gridCells[x * y];
clusterPoint.NumberOfPointsInCluster += 1;
clusterPoint.Location = clusterPoint.Location + " : " + point.Location;
clusterPoint.LocationDescription = "Site Point Cluster";
if (point.MatrixSiteKey.MatrixSiteCountOfProjects != null)
{
//clusterPoint.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite += point.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite;
clusterPoint.NumberOfProjectsInCluster += point.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite;
}
}
else
{
clusterPoint = point;
clusterPoint.NumberOfPointsInCluster = 1;
if (point.MatrixSiteKey.MatrixSiteCountOfProjects != null)
{
//clusterPoint.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite += point.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite;
clusterPoint.NumberOfProjectsInCluster += point.MatrixSiteKey.MatrixSiteCountOfProjects.NumberOfProjectsInSite;
}
clusterPoint.IsClustered = true;
clusterPoint.Location = clusterPoint.Location + " : " + point.Location;
clusterPoint.LocationDescription = "Site Point Cluster";
}
gridCells[x * y] = clusterPoint;
}
}
}
}
}
// extract point clusters
foreach (MatrixSiteLocationPoint point in gridCells.Values)
{
clusteredPoints.Add(point);
}
return clusteredPoints;
}
private void LatLongToPixel(double latitude, double longitude, long lvl, ref long pixelx, ref long pixely)
{
latitude = Clip(latitude, MinLatitude, MaxLatitude);
longitude = Clip(longitude, MinLongitude, MaxLongitude);
double x = (longitude + 180) / 360;
double sinLatitude = Math.Sin(latitude * Math.PI / 180);
double y = 0.5 - Math.Log((1 + sinLatitude) / (1 - sinLatitude)) / (4 * Math.PI);
UInt32 mapSize = Offset(Convert.ToInt32(lvl));
pixelx = Convert.ToInt64(Clip(x * mapSize + 0.5, 0, mapSize - 1));
pixely = Convert.ToInt64(Clip(y * mapSize + 0.5, 0, mapSize - 1));
}
private double Clip(double n, double minValue, double maxValue)
{
return Math.Min(Math.Max(n, minValue), maxValue);
}
private UInt32 Offset(int level)
{
UInt32 bit = new UInt32();
bit = 256;
return bit << level;
}
#region (Property) North
private double north;
/// <summary>
/// Gets/Sets Northern coordinate of map window
/// </summary>
public double North
{
get
{
return north;
}
set
{
north = value;
}
}
#endregion
#region (Property) South
private double south;
/// <summary>
/// Gets/sets Southern coordinate of map window
/// </summary>
public double South
{
get
{
return south;
}
set
{
south = value;
}
}
#endregion
#region (Property) East
private double east;
/// <summary>
/// Gets/Set eastern coordinate of map window
/// </summary>
public double East
{
get
{
return east;
}
set
{
east = value;
}
}
#endregion
#region (Property) West
private double west;
/// <summary>
/// Gets/Sets Western coordinate of map window
/// </summary>
public double West
{
get
{
return west;
}
set
{
west = value;
}
}
#endregion
#region (Property) MapWidth
private long mapWidth;
/// <summary>
/// Gets width of map
/// </summary>
public long MapWidth
{
get
{
return mapWidth;
}
set
{
mapWidth = value;
}
}
#endregion
#region (Property) MapHeight
private long mapHeight;
/// <summary>
/// Gets/Sets height of map
/// </summary>
public long MapHeight
{
get
{
return mapHeight;
}
set
{
mapHeight = value;
}
}
#endregion
#region (Property) MapZoomLevel
private long mapZoomLevel;
/// <summary>
/// Gets/Sets zoom level of map
/// </summary>
public long MapZoomLevel
{
get
{
return mapZoomLevel;
}
set
{
mapZoomLevel = value;
}
}
#endregion
#region (Property) PointsToCluster
private List<MatrixSiteLocationPoint> pointsToCluster;
/// <summary>
/// List of points to cluster
/// </summary>
public List<MatrixSiteLocationPoint> PointsToCluster
{
get
{
return pointsToCluster;
}
set
{
pointsToCluster = value;
}
}
#endregion
}
}
