I’ve recently been working on a project which makes extensive use of the Google maps API for flash (more about that once it launches). One of the things that was necessary for this project was clustering of markers when they were too close together. To understand what I mean by this click the image below to check out the example:
As you can see, the capital cities of the world are all displayed on the map as small red dots. I got the list of capital cities from here and converted them to XML for the example – note that some of them (e.g. Rome) appear to be slightly incorrectly positioned. If the cities are too close to each other for the current zoom level then they are clustered into larger red dots with numbers in the middle.
This has of course been done before (e.g. here and here) but the solutions didn’t work for my situation. The first is grid based (rather than distance based) which can give some strange results. And more importantly for my project I needed to use custom markers (for both the individual markers and the clusters) and that didn’t seem possible without changing the actual library code. And with the second solution the markers seem to “jiggle” as you drag the map and I wasn’t sure about whether the license permitted use in a commercial project.
So I found a post from Mika Tuupola. In it he explains the advantage of distance based (as opposed to grid based) clustering algorithms. He then provides some PHP sourcecode to implement distance based clustering.
I started off with a fairly straightforward port of the code from the article but I found that it needed to be optimised quite heavily so that it would work performantly in Flash (especially since it needs to re-calculate the clustering on every zoom change). My final Cluster class looked like this:
{
import com.google.maps.overlays.Marker;
import flash.geom.Point;
import flash.utils.Dictionary;
/**
* Distance based clustering solution for google maps markers.
*
* <p>Algorithm based on Mika Tuupola's "Introduction to Marker
* Clustering With Google Maps" adapted for use in a dynamic
* flash map.</p>
*
* @author Kelvin Luck
* @see http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps
*/
public class Clusterer
{
public static const DEFAULT_CLUSTER_RADIUS:int = 25;
private var _clusters:Array;
public function get clusters():Array
{
if (_invalidated) {
_clusters = calculateClusters();
_invalidated = false;
}
return _clusters;
}
private var _markers:Array;
public function set markers(value:Array):void
{
if (value != _markers) {
_markers = value;
_positionedMarkers = [];
for each (var marker:Marker in value) {
_positionedMarkers.push(new PositionedMarker(marker));
}
_invalidated = true;
}
}
private var _zoom:int;
public function set zoom(value:int):void
{
if (value != _zoom) {
_zoom = value;
_invalidated = true;
}
}
private var _clusterRadius:int;
public function set clusterRadius(value:int):void
{
if (value != _clusterRadius) {
_clusterRadius = value;
_invalidated = true;
}
}
private var _invalidated:Boolean;
private var _positionedMarkers:Array;
public function Clusterer(markers:Array, zoom:int, clusterRadius:int = DEFAULT_CLUSTER_RADIUS)
{
this.markers = markers;
_zoom = zoom;
_clusterRadius = clusterRadius;
_invalidated = true;
}
private function calculateClusters():Array
{
var positionedMarkers:Dictionary = new Dictionary();
var positionedMarker:PositionedMarker;
for each (positionedMarker in _positionedMarkers) {
positionedMarkers[positionedMarker.id] = positionedMarker;
}
// Rather than taking a sqaure root and dividing by a power of 2 to calculate every distance we
// do the calculation once here (backwards).
var compareDistance:Number = Math.pow(_clusterRadius * Math.pow(2, 21 - _zoom), 2);
var clusters:Array = [];
var cluster:Array;
var p1:Point;
var p2:Point;
var x:int;
var y:int;
var compareMarker:PositionedMarker;
for each (positionedMarker in positionedMarkers) {
if (positionedMarker == null) {
continue;
}
positionedMarkers[positionedMarker.id] = null;
cluster = [positionedMarker.marker];
for each (compareMarker in positionedMarkers) {
if (compareMarker == null) {
continue;
}
p1 = positionedMarker.point;
p2 = compareMarker.point;
x = p1.x - p2.x;
y = p1.y - p2.y;
if (x * x + y * y < compareDistance) {
cluster.push(compareMarker.marker);
positionedMarkers[compareMarker.id] = null;
}
}
clusters.push(cluster);
}
return clusters;
}
}
}
import com.google.maps.LatLng;
import com.google.maps.overlays.Marker;
import flash.geom.Point;
internal class PositionedMarker
{
public static const OFFSET:int = 268435456;
public static const RADIUS:Number = OFFSET / Math.PI;
// public properties are quicker than getters - speed is important here...
public var position:LatLng;
public var point:Point;
private var _marker:Marker;
public function get marker():Marker
{
return _marker;
}
private var _id:int;
public function get id():int
{
return _id;
}
private static var globalId:int = 0;
public function PositionedMarker(marker:Marker)
{
_marker = marker;
_id = globalId++;
position = marker.getLatLng();
var o:int = OFFSET;
var r:Number = RADIUS;
var d:Number = Math.PI / 180;
var x:int = Math.round(o + r * position.lng() * d);
var lat:Number = position.lat();
var y:int = Math.round(o - r * Math.log((1 + Math.sin(lat * d)) / (1 - Math.sin(lat * d))) / 2);
point = new Point(x, y);
}
}
You can download the class and the code for the example from it’s github repository. Note that the Clusterer class is all that you need to use – the rest of the classes are just for the sake of the example. I hope it’s useful – if you make anything cool with it then please post in the comments.
26 Comments, Comment or Ping
You have no idea how long I've been looking for something like this. I have not looked at the files yet but so far i am impressed. I'll let you know how it goes.
Dane
August 5th, 2009
WOW.
I was happy to see the previous marker cluster examples.
But this one has me doing flips - Im so excited.
You code is far the cleanest and most logical I have seen.
I've got something in the works I'm doing with your code - will post a url once I get everything done.
One question though - is this open source? I certainly will credit you as you've done half of the work for me. But are you cool with me modifying and reusing it?
August 6th, 2009
Hi guys,
Glad you both like it :)
@Acts7 - yes, the code is open source. MIT license (unless Mika's PHP code is under a different license - his site isn't loading for me now so I can't check). Looking forward to see your URL showing what you've built,
Cheers,
Kelvin :)
August 6th, 2009
QUESTION:
Im pretty new to the googlemaps api.
So I may be entirely missing something here.
But I cannot double click on the marker cluster to zoom in.
As a matter of fact I can't even achieve a trace statement on click for the cluster.
I can on the individual points (marker)s
August 6th, 2009
Nevermind. It was something stupid on my end.
August 6th, 2009
Kevin -
Im clustering markers with your solution and was wondering if there is a way to know what markers are in a cluster. For example - if you click on the cluster a list of the markers would appear.
thanks again
Dane
August 11th, 2009
Hi Dane,
Yes there is. All that the Clusterer returns is an array of markers clustered into sub-arrays. So you create a custom marker which accepts a sub-array of markers and you can easily do what you want. In my example I just use the length of the sub-array to put a number in the cluster marker but you also have access to it's child markers...
Hope that helps,
Kelvin :)
August 11th, 2009
Hello Kevin,
thank you for your post. I am attempting to add a border to my Google Map in Flash but cannot seem to display what I am looking for. Can you please offer an suggestions?
Thanks,
Richard
August 17th, 2009
Hi Richard,
If I understand you correctly you want to display a border around your map? There are a number of ways you could do this - the easiest would probably be to add a rectangle slightly bigger than the map to the DisplayList below the map... If you need a more detailed answer maybe check out the google maps for flash mailing list:
http://groups.google.com/group/google-maps-api-for-flash/
Hope that helps,
Kelvin :)
August 17th, 2009
This is being very nice. But when having I am problems to load xml file not Array. This is possible? How being use of xml file?
August 27th, 2009
Im not sure if its the same issue. But I can load XML data on the main class no problem. It traces perfectly into the ExampleSingleMarker.as class using the same push statement as the addMarkers();
But I can't get it to display beyond that. The points trace in ExampleSingleMarker. But they don't show up on the map.
Here is the code I'm using to load XML data
/* ------------------------ */
var xmlFileName:String = "clustercapitals.xml";
var xmlString:URLRequest = new URLRequest(xmlFileName);
var xmlLoader:URLLoader = new URLLoader(xmlString);
xmlLoader.addEventListener(Event.COMPLETE, parseXML, false, 0, true);
/* ------------------------ */
private function parseXML(event:Event):void {
markers = [];
var markersXML:XML = new XML(event.target.data);
var markerXMLList:XMLList = markersXML.*;
var markersCount:int = markerXMLList.length();
var i:Number;
for (i=0; i < markersCount; i++) {
var markerXml:XML = markerXMLList[i];
var locCountry:String = markerXml.country;
var locName:String = markerXml.name;
var loc:LatLng = new LatLng(markerXml.lat, markerXml.lng);
markers.push(new ExampleSingleMarker(loc, locName, locCountry));
}
}
August 27th, 2009
any guess what I'm doing wrong?
August 27th, 2009
Hi Acts7,
Is this a question about the marker clusterer specifically or just about the google maps api for flash in general? If it's the former please can you clarify how you are interacting with the marker clusterer, if it's the latter then please try the google group:
http://groups.google.com/group/google-maps-api-for-flash/
August 28th, 2009
Thanks Kelvin.
I've got the google maps running just fine. And can add points there with no issue.
But I was trying some experiments on changing the methodology on your clustering.
So when I ran into a snag I took it back to square one.
To answer your question, using your initial source code, I am avoiding the CapitalCity.as in favor of loading in an XML file on the main class. Then I am pushing the exact same data to ExampleSingleMarker.
I run a trace after the data is pushed to ExampleSingleMarker and the data is indeed being pushed in. However; it appears that ExampleSingleMarker is ignoring all data.
When I use the addMarkers function you have in place on Main.as, and run a trace in ExampleSingleMarkers the data is formatted the exact same way as when I trace it from the file I load.
So if they are formatted the same, why is data from an external file ignored but inline XML is utilized.
August 28th, 2009
Kelvin, I have modified the code slightly - so it utilizes the GetCapitals however it still fails to load the points as soon as I add any kind of Event to the addMarkers. Here is my new code:(notice I commented out addMarkers to first load the XML then when read, have called addMarkers.
/*START CODE SNIPPET FROM CLUSTEREXAMPLE.as */
// added variables so I could change the file if necessary from the html page.
var defaultXMLPath:String = "clustercapitals.xml";
var xmlFileName:String = root.loaderInfo.parameters.xmlFileName || defaultXMLPath;
/*---------------*/
private function onMapReady(event:MapEvent):void
{
map.addControl(new ZoomControl());
map.setCenter(new LatLng(51.32, 0), 3);
map.enableScrollWheelZoom();
map.addEventListener(MapZoomEvent.ZOOM_CHANGED, onMapZoomChanged);
//addMarkers();
loadXML();
clusterer = new Clusterer(markers, map.getZoom(), 30);
attachedMarkers = [];
attachMarkers();
}
private function loadXML():void {
var xmlString:URLRequest = new URLRequest(xmlFileName);
var xmlLoader:URLLoader = new URLLoader(xmlString);
xmlLoader.addEventListener(Event.COMPLETE, addMarkers);
}
private function addMarkers(event:Event):void {
markers = [];
var capitals:Array = CapitalCity.getCapitals(new XML(event.target.data));
for each (var capital:CapitalCity in capitals) {
markers.push(new ExampleSingleMarker(capital.location));
}
}
/*END CODE SNIPPET FROM CLUSTEREXAMPLE.as */
/*START CODE SNIPPET FROM CAPITALCITY.as */
package com.kelvinluck.gmaps.example
{
import com.google.maps.LatLng;
/**
* Quick example class to get a list of all the worlds capital cities.
*
* @author Kelvin Luck
*/
public class CapitalCity
{
public var name:String;
public var country:String;
public var location:LatLng;
public static function getCapitals(capitalXML:XML):Array
{
var capitals:Array = [];
var capital:CapitalCity;
for each (var capitalNode:XML in capitalXML.capital) {
capital = new CapitalCity();
capital.name = capitalNode.@name;
capital.country = capitalNode.@country;
capital.location = new LatLng(capitalNode.@lat, capitalNode.@lng);
capitals.push(capital);
}
return capitals;
}
}
}
/*END CODE SNIPPET FROM CAPITALCITY.as */
/*---------------*/
/*
So you can see there are very little modifications to the file. What is causing this not to work? When I do this I simply get an empty map with no dots.
*/
August 28th, 2009
http://myvideosnapshots.com/examples/googlemaps/KelvinLuckCluster.zip
You can download my complete source files here.
I'm setup in FlashDevelop so if you have that free program simply open the project file.
If not the code is exactly the same regardless of your editor program.
August 28th, 2009
Kelvin,
Am I missing some stupid-simple step here? Any guesses why loading external data would cause the points not to be rendered/plotted?
The data is indeed being sent to ExampleSingleMarker. And being its the same format as the internal array of points I cannot see why the points would fail to initiate.
August 31st, 2009
Hi Kelvin,
Just wanted to say thanks, I'm glad I didn't end up having to write this myself... although I do like a challenge this is working really well for me outright. Not to tell you what to do since you're obviously helping me :), but you should try and get this to the peeps at google code would be nice if they included this in the API (or start making a utilities package).
Thanks again really great class, took no work to make this do essentially what I want, now it's just a matter of updating the way it handles the clustered objects... the UI plan is to make it so when you click a cluster it shows a pop up with a zoomed in version of the map around the clustered points if you have any suggestions for this it'd be appreciated. I'll have to check, but if I'm allowed I'll post the code used for creating this map drill down, if/when I get it working.
Also if anyone is looking for how to do this with the javascript library there's a pretty good breakdown of available options at this site: http://www.svennerberg.com/2009/01/handling-large-amounts-of-markers-in-google-maps/
Thanks a bunch,
Shaun
September 4th, 2009
DOH I knew it would come down to a simple stupid thing.
clusterer = new Clusterer(markers, map.getZoom(), 30);
attachedMarkers = [];
attachMarkers();
needed to be moved after the loading of the xml.
September 7th, 2009
hi kevin, thanks for the code. notice a slight problem with the cluster marker picking up the rollover some distance below the graphic. i believe the default icon google is passing in the background is the cause. e.g. roll over near the "n" of yemen is picking up the cluster mark for saudi which is a considerable distance north... any ideas on how to constrain the original google marker size to over come this?
September 20th, 2009
after a wee bit o investigation... turns out the wierd rollover effect was being caused by the textField !
September 21st, 2009
Ii'm starting with Flex and Google Maps and i want to know how can i see the project in Flex. I'm talking about the mxml file.. Something have an mxml file that implements this clustering, because i can't see how it's working. regards.
October 29th, 2009
LEO - look at this comment I made:
http://www.kelvinluck.com/2009/08/google-maps-for-flash-marker-clustering/#comment-18158
It has the complete source files. ALSO I mention FlashDevelop. This is a free program for working with FLEX SDK. If you like the software, please consider donating on FlashDevelop.org (but donating is not required).
October 30th, 2009
Hi, i download your code and when i prove, flash cs4 say this when i made zoom:
ArgumentError: Error #2025: The supplied DisplayObject must be a child of the caller.
at flash.display::DisplayObjectContainer/removeChild()
at com.google.maps.wrappers::SpriteFactory/removeChild()
at com.google.maps.wrappers::ISpriteFactoryWrapper/removeChild()
at com.google.maps.overlays::Marker/renderMarker()
at com.google.maps.overlays::Marker/redraw()
at com.google.maps.overlays::Marker/onAddedToPane()
at com.google.maps.overlays::Overlay/set pane()
at com.google.maps.overlays::Pane/addOverlay()
at com.google.maps.core::MapImpl/addOverlay()
at com.google.maps.wrappers::IMapWrapper/addOverlay()
at ClusterExample/attachMarkers()
at ClusterExample/onMapZoomChanged()
January 28th, 2010
Curiously this happens with map_1_18.swc. With map_1_17.swc. runs ok.
January 28th, 2010
Hi Maosi,
That's strange, I guess google changed something between the releases... I am only using their public API though so there shouldn't be any problems...
When I have some spare time I'll investigate with the latest google maps swc and update the code if I get to the bottom of it. It may not be too soon though...
Cheers,
Kelvin :)
January 29th, 2010
Reply to “Google maps for flash marker clustering”