kelvinluck.com

a stroke of luck

Google maps for flash marker clustering

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:

Google Maps for Flash Clustering Screenshot

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:

package com.kelvinluck.gmaps
{
   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.

41 Comments, Comment or Ping

Reply to “Google maps for flash marker clustering”