Introduction to Marker Clustering With Google Maps
November 4th, 2008
Static Maps API has URL length limit of around 2048 characters. You can hit this limit quickly when adding lot of markers. You can keep URL short by clustering markers together.
Square Based Clustering
Clustering is usually done by dividing map to squares. Square size depends on map zoom level. Markers inside a square are then grouped into cluster. This technique has some limitations. Look at the following image.
Two markers are close to each other. In fact they are so close they are overlapping. Both markers are also the only marker inside their square. Because markers are in separate square they wont be clustered.
Distance Based Clustering
We can also group markers together based on their distance from each other. We could cluster all markers inside 10 kilometer radius together. There is one problem with this approach. Kilometers (and miles) have different meaning in different zoom levels. In zoomed in map it might mean 100 pixels. In zoomed out maps one kilometer might be only one pixel.
There is only one distance unit which does not have this problem: pixels in current zoom level. One pixel on screen is always one pixel on screen. For example we want to cluster all markers which are 20 pixels from each other. I chose 20 pixels because it happens to be the distance after which markers start to overlap each other.
Now the two markers would be clustered since they are inside 20 pixel radius.
Distance Between Two Coordinates on Earth
Distance between two points on earth can be calculated in several ways. Haversine formula is reasonably accurate and widely used. It assumes earth is spherical (in reality earth is slightly ellipsoid). This causes accuracy to be +-2 km when calculating distances of around 20.000 km. 6371.0 km is used as average radius of earth.
Below is PHP implementation of Haversine formula:
function haversineDistance($lat1, $lon1, $lat2, $lon2) {
$latd = deg2rad($lat2 - $lat1);
$lond = deg2rad($lon2 - $lon1);
$a = sin($latd / 2) * sin($latd / 2) +
cos(deg2rad($lat1)) * cos(deg2rad($lat2)) *
sin($lond / 2) * sin($lond / 2);
$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
return 6371.0 * $c;
}
But didn’t wee need distance in pixels instead? For that we can use Pythagoras’ theorem. Pythagoras’ theorem uses cartesian (pixel) coordinates. Some Mercator magic can be used to convert latitude and longitude to pixel x and y values.
You might wonder where did number 268435456 come from? It is half of the earth circumference in pixels at zoom level 21. You can visualize it by thinking of full map. Full map size is 536870912 × 536870912 pixels. Center of the map in pixel coordinates is 268435456,268435456 which in latitude and longitude would be 0,0.
define('OFFSET', 268435456);
define('RADIUS', 85445659.4471); /* $offset / pi() */
function lonToX($lon) {
return round(OFFSET + RADIUS * $lon * pi() / 180);
}
function latToY($lat) {
return round(OFFSET - RADIUS *
log((1 + sin($lat * pi() / 180)) /
(1 - sin($lat * pi() / 180))) / 2);
}
function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) {
$x1 = lonToX($lon1);
$y1 = latToY($lat1);
$x2 = lonToX($lon2);
$y2 = latToY($lat2);
return sqrt(pow(($x1-$x2),2) + pow(($y1-$y2),2)) >> (21 - $zoom);
}
Now we have all needed mathematics in place. What to do with them?
Cluster Markers Together
Let’s write example clusterer function. It takes three parameters:
- Array of lat and lon locations.
- Distance in pixel inside which markers will be clustered.
- Current map zoom level.
Function will return another array where coordinates closer than $distance are clustered together.
function cluster($markers, $distance, $zoom) {
$clustered = array();
/* Loop until all markers have been compared. */
while (count($markers)) {
$marker = array_pop($markers);
$cluster = array();
/* Compare against all markers which are left. */
foreach ($markers as $key => $target) {
$pixels = pixelDistance($marker['lat'], $marker['lon'],
$target['lat'], $target['lon'],
$zoom);
/* If two markers are closer than given distance remove */
/* target marker from array and add it to cluster. */
if ($distance > $pixels) {
printf("Distance between %s,%s and %s,%s is %d pixels.\n",
$marker['lat'], $marker['lon'],
$target['lat'], $target['lon'],
$pixels);
unset($markers[$key]);
$cluster[] = $target;
}
}
/* If a marker has been added to cluster, add also the one */
/* we were comparing to and remove the original from array. */
if (count($cluster) > 0) {
$cluster[] = $marker;
$clustered[] = $cluster;
} else {
$clustered[] = $marker;
}
}
return $clustered;
}
We can now test clusterer function with array of coordinates.
$markers = array();
$markers[] = array('id' => 'marker_1',
'lat' => 59.441193, 'lon' => 24.729494);
$markers[] = array('id' => 'marker_2',
'lat' => 59.432365, 'lon' => 24.742992);
$markers[] = array('id' => 'marker_3',
'lat' => 59.431602, 'lon' => 24.757563);
$markers[] = array('id' => 'marker_4',
'lat' => 59.437843, 'lon' => 24.765759);
$markers[] = array('id' => 'marker_5',
'lat' => 59.439644, 'lon' => 24.779041);
$markers[] = array('id' => 'marker_6',
'lat' => 59.434776, 'lon' => 24.756681);
$clustered = cluster($markers, 20, 11);
print_r($clustered);
If you run the code you can see how marker_3, marker_4 and marker_6 are clustered together. This can better be visualized as map screenshot before and after clustering. Blue marker is a cluster.
Real Life Usage?
Obviously making an array of coordinates into a new array of coordinates is not really usefull. However the first clusterer for Static Maps I committed to GitHub uses previously described technique. Clustering a static map takes only two extra lines of code. First create a cluster. Then add it to the map object. Rest is taken care automatically.
$clusterer = Google_Maps_Clusterer::create('distance');
$map->setClusterer($clusterer);
You can see it in action in capital cities of the world map. City locations are parsed from KML file. Note that in closer zooms locations are slightly off. Coordinates have only two decimals of latitude and longitude.
Currently I have demo code only for Static Maps. Serverside clustering for Google Maps API will follow soon. Thats a promise. Cross my heart.
November 6th, 2008 at 07:41 PM
I’m looking forward to read about serverside clustering. I’ve been trying from months to cluster those damn markers directly from mysql or from the PHP script… :)
November 12th, 2008 at 11:19 AM
Its only been 1 month of my job,and i got this clustering marker assingment.Thanks a lot for this mind blowing code,as only i know that how much it cost to me.thanks thanks a lot for this.
November 14th, 2008 at 12:46 PM
gm, shilpi: Thanks! There are still some problems with the code. It is quite heavy on the math side which makes it go slower with big amount of markers. It all can be fixed with some caching and code optimization. But all that will come a bit later. I need to be happy with the API first.
November 14th, 2008 at 07:54 PM
As an alternative to the haversine formula, you could avoid the square root by using the spherical law of cosines to get the on-earth distance, as per http://www.movable-type.co.uk/scripts/latlong.html and then convert to pixels using the zoom level. Or, if you know the pixel locations for your markers and the desired clustering distance ahead of time, you can use the pythagorean method without the square root. i.e., just compare deltaX^2 + deltaY^2 < clusterDist^2
November 16th, 2008 at 08:33 AM
Great article, especially the math part, im using the square approach atm but would be nice to use distance…
Maybe its to computing intensive, we have ~100makers / map. But the other insights about pixels/zoom will help me too ;)
November 16th, 2008 at 11:05 PM
Karl: I read about law of cosines but it was mentioned as not recommended formula for calculating distances. FAQ described it this way:
Although this formula is mathematically exact, it is unreliable for small distances because the inverse cosine is ill-conditioned.
...
A computer carrying seven significant figures cannot distinguish the cosines of any distances smaller than about one minute of arc.
Now when I read your explanation I understand law of cosines actually is usable. At least if your programming language supports 64 bit floating-point numbers.
Will implement it and do some benchmarking.
November 16th, 2008 at 11:12 PM
grosser: It is math intensive and in no way optimized yet. I will try Karl’s suggestions above to make it faster. Aggressive caching helps too.
January 4th, 2009 at 11:50 PM
For the love of God – isn’t there some way for the Philistines to simply divide markers in Google Maps? Not all of us get the extreme joy out of math that you all do, nor does it come naturally….
January 11th, 2009 at 08:08 PM
Chris: Hey, I do not really understand the math part either. I just searched the Google and somehow tinkered it to work ;)
February 21st, 2009 at 01:30 AM
I am looking to implement this in a few days and I am thinking about clustering markers by the amount of times they have been clicked.
February 27th, 2009 at 01:00 PM
thats great. exactly what I was looking for. Thanks.
March 31st, 2009 at 05:44 AM
Hi. Thanks for the post. How did you get google maps zoom level conversions to earth circumference in pixels? Thank you.
March 31st, 2009 at 06:47 PM
Vasco: You mean the offset? You only need it for maximum zoom level 21.
“You might wonder where did number 268435456 come from? It is half of the earth circumference in pixels at zoom level 21. You can visualize it by thinking of full map. Full map size is 536870912 × 536870912 pixels. Center of the map in pixel coordinates is 268435456,268435456 which in latitude and longitude would be 0,0.”
For other zoom levels value is adjusted using arithmetic right shift (dividing). Something like:
April 2nd, 2009 at 07:08 AM
@mika: That was it! Thank you very much.
April 17th, 2009 at 06:48 AM
Great job! What licence do you publish this code under? Does it allow me to port it to python and/or modify it?
April 17th, 2009 at 06:51 AM
I can’t find rss/atom link to your blog. Is it just me or you don’t have it?
April 17th, 2009 at 07:26 PM
parxier: Everything I do is MIT licensed so you can do pretty much anything you want commercially on non commercially. Only thing you cannot do is to remove my name from the copyright header and claim it was done by somebody else.
If you port to another language then it is not my code and you can again do whatever you want. However it would give me nice fuzzy feeling if you would mention original source somewhere.
Atleast Safari and FireFox should show RSS icon on the address bar. If not for somereason you can grab the feed here
April 29th, 2009 at 06:46 PM
Seems this is some great code…I have a server with thousands of locations. Kind of a novice here so is there a simple “How to” somewhere that might show me where I should jump into this code (i.e. given the list of my locations, what function should I call on each location so this can plot them on the map)?
May 29th, 2009 at 02:18 PM
It is one great example.. but the only issue is number of clusters on the map. if you have very small number its fine.. speed is not an issue.. but consider 100,000 markers to display at North America level then as you keep zooming it will start decreasing. THis whole thing can be a huge performance issue. Isn’t it? Ajit
May 29th, 2009 at 02:24 PM
Matt: Google Static Maps documentation is a great place to start.
Ajit: Yes of course. Number of markers is always an issue. It does not matter if the markers are clusters or not.
June 21st, 2009 at 05:33 AM
Hello everyone!
Nice article for a novice on the subject. I read this article few months ago and it was very useful.
The problem I am facing now is that I need to handle more than 10,000 of markers and I have to manage them by clustering on the server side.
My main issue is that all my solution was developed using ASP.net 2.0 and I cannot find nothing related with this technology.
If someone can provide me with an example or someone who already has passed by the same situation will be really appreciated.
Thanks! Pablo from BA, Argentina
July 10th, 2009 at 11:29 PM
Hey, nice article.However, I have aquestion. I might be wrong since my PHP coding experience is almost null. Let’s consider this simple example:
3 markers M1->M3. M1 overlaps M2, M2 overlaps M3, M1 does NOT overlap M3.
Going over the cluster function I see this happening (again, my understanding of PHP might be wrong): - pop M3 out of the array - compare it with M1. no overlapping so continue - compare it with M2. Overlapping detected so now M2 is taken out of the initial array (unset?) and put into the first cluster together with M3. The end result being [Cluster1, M1]
My question: what happens to M1 now, since there is a big chance the cluster icon will overlap M1?
Thanks
August 4th, 2009 at 02:33 PM
Thanks for this post. It was really useful to me and I ported the code to flash for a project I’m working on:
http://www.kelvinluck.com/2009/08/google-maps-for-flash-marker-clustering/
August 4th, 2009 at 05:04 PM
Kelvin Luck: Absolutely cool stuff!
August 4th, 2009 at 05:29 PM
Catalin: You are correct. It is possible cluster might overlap with marker or another cluster. You can loop the markers+clusters array to avoid this. For simplicitys sake I have left it out from this example.
December 1st, 2009 at 09:04 PM
Hi,
I’m using Maptimize (www.maptimize.com), no code to write, someone as done it before :-p
Nice post anyway ;-)
January 3rd, 2010 at 09:04 PM
Thanks ever so much for this code Mike!
I have implemented a test version as a server-side filter for what comes out of my MySQL database.
Test site here: http://placebook.tv/index.php?cluster
(you need the cluster arg to turn on the clusterer at the moment)
I modified the code some, I just get it to throw away each clustered point rather than save them in an array. However, what I am unable to do yet is work out how to calculate the mid-point of clusters server-side.
I also added a little improvement – an extra var $mc is passed as a minimum amount of markers before we start clustering. If you are passing the bounds of the viewport to your point pull routine, then this will mean that a couple of very close markers will eventually unbunch if you zoom in close enough and there are less than $mc markers on screen.
Here is my code:
function cluster($markers, $distance, $zoom, $mc) { $clustered = array(); $markercount = count($markers); /* Loop until all markers have been compared. */ while (count($markers)) { $marker = array_pop($markers); //echo "<hr>processing ".$marker['name'].'<br>'; if (!isset($marker['cc'])){ $marker['cc'] = 1; $marker['nelat'] = -90; $marker['nelng'] = -180; $marker['swlat'] = 90; $marker['swlng'] = 180; } //print_r($marker); //$cluster = array(); /* Compare against all markers which are left. */ foreach ($markers as $key => $target) { $pixels = pixelDistance($marker['marker_point'][1], $marker['marker_point'][0], $target['marker_point'][1], $target['marker_point'][0], $zoom); /* If two markers are closer than given distance remove */ /* target marker from array and add it to cluster. */ if (($distance > $pixels) && ($markercount > $mc)) { // don't cluster if mincount (mc) is not reached //printf("Distance between %ss and %s is %d pixels.\n", $marker['name'], $target['name'], $pixels); //echo "removing ".$target['name'].'<br>'; $marker['cc'] += 1; // extend bounding box around cluster if ($target['marker_point'][1] > $marker['nelng']){ // is it further east? $marker['nelng'] = $target['marker_point'][1]; } if ($target['marker_point'][1] < $marker['swlng']){ // is it further west? $marker['swlng'] = $target['marker_point'][1]; } if ($target['marker_point'][0] > $marker['nelat']){ // is it further north? $marker['nelat'] = $target['marker_point'][0]; } if ($target['marker_point'][0] < $marker['swlat']){ // is it further south? $marker['swlat'] = $target['marker_point'][0]; } unset($markers[$key]); //$cluster[] = $target; } } /* If a marker has been added to cluster, add also the one */ /* we were comparing to and remove the original from array. */ if ($marker['cc'] > 1){ // preserve the info we want to keep... $nm = array(); $nm['marker_point'] = $marker['marker_point']; /* $nm['marker_point'] = array(); $nm['marker_point'][0] = $marker['nelat'] - $marker['swlat'] / 2; // set marker to middle of box. wrong math? $nm['marker_point'][1] = $marker['nelng'] - $marker['swlng'] / 2; */ $nm['cc'] = $marker['cc']; $nm['mtype'] = 'clu'; $nm['nelat'] = $marker['nelat']; $nm['nelng'] = $marker['nelng']; $nm['swlat'] = $marker['swlat']; $nm['swlng'] = $marker['swlng']; // return that and dump the rest $clustered[] = $nm; } else { unset($marker['cc']); unset($marker['nelat']); unset($marker['nelng']); unset($marker['swlat']); unset($marker['swlng']); //$marker['mtype'] = 'loc'; $clustered[] = $marker; } } return $clustered; }