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.

 (More)