A Linear Clustering Algorithm for Virtual Earth

by Gong Liu May 22, 2009 05:12

Official Tracker for Katie Visco's Run Across America   

A while ago a friend showed me a piece of news about a girl named Katie Visco who is about to become the youngest female ever to run solo across America. I thought her story was very inspirational and contacted her about tracking her run on the internet. She was thrilled about the idea and I ended up hosting and maintaining the following tracker about her run. I update the tracker every day based on the mileage log published on her blog site Pave Your Lane

Technical Notes

Linear Clustering Algorithm  

The above tracker is very similar to my workout tracker. However, one key difference is that her tracker shows every day on the map while my tracker only shows my workout days. In her case, the running days are marked by a little red square  and the resting days by a little yellow square . On some resting days she may stay at the same location and thus the day markers overlap. If you hover the mouse cursor on overlapped markers, only the infobox of the top most marker is shown, no matter how closely you zoom in. In the above tracker I have solved the problem by representing overlapped markers with a bigger yellow square . When you hover the mouse cursor on the bigger marker, you will see a list of days it represents. Clicking on one of the days will show that day's infobox at the same location. The technique behind the solution is called pushpin clustering. Pushpin clustering is a process of representing several nearby pushpins with a single pushpin. The original purpose of this is to reduce overcrowded pushpins that may obscure the map underneath. We use pushpin clustering to gain access to overlapped pushpins or markers. Overcrowding is not much of a concern here. Before Virtual Earth 6.2, developers using the Virtual Earth map control would have to either divide groups of pushpins into shape layers and manually control which layers to show and hide at different zoom levels, or just not show pushpins at zoom levels if there were too many on the screen. With Virtual Earth 6.2, it becomes a lot easier to control which pushpins are clustered and how a cluster is displayed.

There are two overloaded methods related to pushpin clustering in VE 6.2:

VEShapeLayer.SetClusteringConfiguration(type, options)
VEShapeLayer.SetClusteringConfiguration(algorithm, options)

The first method allows you to choose one of the pre-defined clustering algorithms. In VE 6.2, there is only one pre-defined clustering algorithm - the grid clustering algorithm. The grid clustering algorithm divides map screen into grids and pushpins falling in one grid are represented by a single pushpin at the grid center. The second method allows you to define your own clustering algorithm. The second parameter in both methods, options, is a VEClusteringOptions object that specifies how a pushpin cluster is displayed in terms of an icon and a callback function where you put your own code to do something about each cluster, such as rendering an infobox.

In our case, the day markers are along some line features (roads), and we are only interested in making overlapped markers into clusters. So the pre-defined grid algorithm is not applicable. We have to roll out our own algorithm, which I call a linear clustering algorithm because of the unique spatial distribution of our markers.

Simply stated, any two or more consecutive markers that overlap or are close enough form a cluster. The following figures show when markers form a cluster and when they don't according to our linear clustering algorithm.

The current marker (black square) in A) does not belong to any cluster because none of its consecutive markers (markers immediately before and after it) is close enough to it. By close enough we mean within a pre-defined square area (or a circle). The side d of the square area is measured in degrees same as latitude/longitude, instead of pixels, and thus the clustering does not change with different zoom levels. By our definition the current marker in B) forms a cluster with its next marker. Backtracking and loop as shown in C) and D) do not form a cluster, because the two markers in the square are not consecutive.

Now let's take a look at some code snips.

    //load day markers to the third layer
    var layer3 = new VEShapeLayer(); 
    var co = new VEClusteringOptions();
    var customIcon = new VECustomIconSpecification();
    customIcon.CustomHTML = "<div style='margin-top: 10px; margin-left: 10px'><img src='images/yellowsquarelarge.gif' width='8' height='8'></div>";
    co.Icon = customIcon;
    co.Callback = ClusterCallback;
    layer3.SetClusteringConfiguration(LinearClusterAlgorithm, co);
    var shapes = new Array();
    for (var i = 0; i < days.length; i++)
        var sh = new VEShape(VEShapeType.Pushpin, days[i].CityCenter);
        sh.SetTitle(days[i].Date.toDateString() + " - Day " + (i + 1));
        if (days[i].RunningDay)
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/redsquare.gif' width='5' height='5'></div>");
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/yellowsquare.gif' width='5' height='5'></div>");   
        shapes[i] = sh;

The above code snip shows that a shape layer is created for day markers. The SetClusteringConfiguration method indicates that the layer is configured to do clustering. The clustering algorithm is defined by a function called LinearClusterAlgorithm and any cluster is going to be dispayed according to the way specified in a VEClusteringOptions object, which includes a display icon (the bigger yellow square ) and a callback function ClusterCallback. The for loop creates day markers as an array of shapes, which is then added to the layer in a batch.

The function LinearClusterAlgorithm is defined as:

function LinearClusterAlgorithm(sLayer)
    var arrCSs = new Array();
    var n = sLayer.GetShapeCount();
    if (n > 0) 
        var shape0 = sLayer.GetShapeByIndex(0);
        var pt0 = shape0.GetPoints()[0];
        var clusterSpec = null;
        for(var i = 1; i < n; i++)
            var shape1 = sLayer.GetShapeByIndex(i);
            var pt1 = shape1.GetPoints()[0];
            if (Overlap(pt0, pt1))
                if (clusterSpec == null)
                    clusterSpec = new VEClusterSpecification();
                    clusterSpec.Shapes = new Array();
                clusterSpec.LatLong = pt1;
                if (i == n-1)
                if (clusterSpec != null)
                    clusterSpec = null;
            shape0 = shape1;
            pt0 = pt1;     
    return arrCSs;

function Overlap(pt0, pt1)
    var dd = 0.0001;
    return (Math.abs(pt0.Latitude - pt1.Latitude) < dd && 
            Math.abs(pt0.Longitude - pt1.Longitude) < dd);

Here, sLayer is a VEShapeLayer object that the algorithm is going to apply to. The main part of the algorithm consists of a for loop that compares first two consecutive shape points, points 0 and 1, then points 1 and 2, and so on. If any two consecutive points overlap, they form a cluster and are added to the Shapes property of a VEClusterSpecification object. Otherwise, the VEClusterSpecification object is added to an array, which is returned to caller at the end of the loop. The function Overlap is used to determine if two points overlap. "Overlap" does not necessarily mean the two points have to have the same coordinates, but rather their differences are within a pre-defined range.

The ClusterCallback function is as follow:

function ClusterCallback(CSs)
    for (var i=0; i < CSs.length; ++i)
        var clusterSpec = CSs[i];
        var clusterShape = clusterSpec.GetClusterShape();
        var shapes = clusterSpec.Shapes;
        clusterShape.SetTitle(shapes.length + " Days");
        var html = "";
        for (var j = 0; j < shapes.length; j++)
            var shape = shapes[j];
            var icon = (shape.GetDescription().indexOf("alt='run'") > 0)? "redsquare.gif" : "yellowsquare.gif";
            html += "<img border='1' src=\"Images/" + icon + "\"> ";
            html += "<a href=\"Javascript: map.HideInfoBox(); ShowInfo('" + shape.GetID() + "')\">" + shape.GetTitle() + "</a><br>"

It accepts an array of VEClusterSpecification objects as parameter, each of which represents a cluster. Each cluster has at least two shape points. The inner for loop uses the info of these points to construct a html snip that is to be used as the description of the cluster's infobox.

When there are overlapped day markers, the touring feature is affected. This is because the ShowInfoBox method is normally called immediately after the map is panned from one point to the next (in the onendpan event handler). But if two or more points overlap, there is no pan action and the onendpan event will not fire, and thus the corresponding infoboxes will not show. To overcome this, we have to call the handler directly at the time an overlap is detected.

Image Overlay

The above tracker has a title image along the top side. Notice that the image is on top of the map layer but under the map control panel, and that the portion of the map that is under the image is still responsive to mouse drag. To overlay the image, I add an image tag just before the myMap div tag:

<img src="images/title.jpg" id="overlay" style="z-index:50; opacity: 0.7; filter: alpha(opacity=70); position:absolute; left:0px; top:0px" alt="pave your lane" />
<div id="myMap" style="width:800;height:600;position:relative;"></div> 

The style opacity: 0.7 works for Firefox and filter: alpha(opacity=70) works for IE 7.0+. So I use both. They make the image semi-transparent. z-index must be > 0, otherwise the image is put behind the map and thus can't be seen. 

The problem with the image tag itself is that it sits on top of both the map layer and the map control panel and make them not responsive to mouse actions. To solve this problem we have to add the image tag as a child node of the myMap div tag:

var veLayer = document.getElementById('myMap');
var imageOverlay = document.getElementById('overlay');

Finally we have to make sure that the z-index of the image tag is between 1 and 99. A z-index value greater than 99 will put the title image above the map control panel, making it unusable.

Another possible way to overlay an image is to use a custom layer, a feature newly available in VE 6.2.  I tried this way but was unable to anchor the image to the top left corner - the image moves as the map is panned. If you know how to do this using custom layer, please let me know.


A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud


<<  April 2017  >>

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.