Home About Us Articles Blog Contact Us Links

Clustering Virtual Earth with MS AJAX and C#

This article explores the next generation clustering techniques for Virtual Earth. It builds on the article: Clustering a million points on Virtual Earth using AJAX and .Net

In the first article we learned why we need clustering for large numbers of points and also for smaller numbers of point in the close proximity.

not clustered

clustered

In this article we migrate to the newly release ASP.NET AJAX and migrate from vb.net to C#, we incorporate encoding of pin locations and use the power of popup content on demand to vastly reduce our data sent to the client and change our architecture significantly.

The application consists of three logical tiers:

The UI will be the aspx webpage, essentially a template with references to our UI logic JavaScript files and any styles or design elements. This all runs from the client browser.
The business layer is our web service and clustering logic. Using MS AJAX our web service has been enabled to be accessed directly from JavaScript from the clients browser. The business layer contains all our clustering logic and runs completely on the server.
The data layer is configurable, the example here accesses an xml file and caches it in memory. This could easily be changed to a database or web service.

Our webpage:


<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title>Clustering Virtual Earth</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <script type="text/javascript" 
    src="http://dev.virtualearth.net/mapcontrol/v4/mapcontrol.js"></script>
    <style type="text/css">
    .DefaultPinOffset {position:absolute;left:0px;top:-20px;}
    </style>
</head>
<body>
    <form id="form1" runat="server">
        <asp:ScriptManager ID="ScriptManager1" runat="server">
            <Scripts>
                <asp:ScriptReference Path="js/Default.aspx.js" />
                <asp:ScriptReference Path="js/UtilEncode.js" />
            </Scripts>
            <Services>
                <asp:ServiceReference Path="MapService.asmx" />
            </Services>
        </asp:ScriptManager>
        <div id="myMap" style="position: relative; width: 800px; height: 600px;"></div>
    </form>
</body>
</html>

We have a simple div to hold our map control and a MS AJAX script manager that references our web services that will return the data and our JavaScript for Virtual Earth. I have added the V4 reference to the VE JavaScript but notice I do not need to explicitly add my GetMap () function to the body, we do this in our JavaScript.

Our web service:


[WebService(Namespace = "http://soulsolutions.com.au/")]
[WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
[ScriptService]
public class MapService : WebService
{
    [WebMethod(Description = "Gets an optomised string of data for rendering on a 
            VE map based on the lat/lon bounds and Zoomlevel supplied")]
    [ScriptMethod(UseHttpGet = true)]
    public string GetClusteredMapData(string encodedBounds, int zoomLevel)
    {
        return ClusterBusinessLogic.GetClusteredMapData(encodedBounds, zoomLevel);
    }

    [WebMethod(Description = "Gets the content for a pushpin showing all data based 
            on the lat/lon bounds supplied")]
    [ScriptMethod(UseHttpGet = true, ResponseFormat = ResponseFormat.Json)]
    public PinData GetPushPin(string encodedBounds, int startIndex)
    {
        return ClusterBusinessLogic.GetClusteredPinData(encodedBounds, startIndex);
    }
}

We provide two methods:

GetClusteredMapData(string encodedBounds, int zoomLevel)
Based on the current view of the map this returns an optimised and encoded string of locations and bounds. The two parameters are the map view encoded for performance used to determine what needs to be shown and the current zoom level used to determine what to cluster. We process the returned string on the client to produce all the pins for the current view, the bounds for the pin represents the underlying data that is displayed for the pin and is passed to our second method.

GetPushPin(string encodedBounds, int startIndex)
Based on a set of bounds the function retrieves the actual content for the cluster as a JSON object. This can be highly optimised on the client depending upon the situation, here we simply return one record at a time with next / previous functionality.

Our Clustering Class:


public static class ClusterBusinessLogic
{
    private const int clusterwidth = 22; 
    //Cluster region width, all pin within this area are clustered
    private const int clusterheight = 27; 
    //Cluster region height, all pin within this area are clustered

    public static string GetClusteredMapData(string encodedBounds, int zoomLevel)
    {
        //decode the bounds into bounds object
        Bounds bounds = Utilities.DecodeBounds(encodedBounds);

        //get random locations in supplied bounds
        List<ClusteredPin> pins = PostcodeData.GetVisiblePins(bounds);

        //cluster the points based on the zoomlevel
        List<ClusteredPin> clusteredpins = cluster(pins, zoomLevel);

        //return the encoded data for the clusters
        return Utilities.EncodeCluster(clusteredpins);
    }

    public static PinData GetClusteredPinData(string encodedBounds, int startIndex)
    {
        //decode the bounds into bounds object
        Bounds bounds = Utilities.DecodeBounds(encodedBounds);

        //get random locations in supplied bounds
        return PostcodeData.GetPinbyBounds(bounds, startIndex);
    }

    private static List<ClusteredPin> cluster(List<ClusteredPin> pins, int zoomLevel)
    {
        //sort pins - must be ordered correctly.
        PinXYComparer pinComparer = new PinXYComparer();
        pins.Sort(pinComparer);

        List<ClusteredPin> clusteredPins = new List<ClusteredPin>();

        for (int index = 0; index < pins.Count; index++)
        {
            if (!pins[index].IsClustered) //skip already clusted pins
            {
                ClusteredPin currentClusterPin = new ClusteredPin();
                //create our cluster object and add the first pin
                currentClusterPin.AddPin(pins[index]);
                pins[index].IsClustered = true;

                //look backwards in the list for any points within the range  
                //that are not already grouped, as the points are in order  
                //we exit assoon as it exceeds the range.  
                addPinsWithinRange(pins, index, -1, currentClusterPin, zoomLevel);

                //look forwards in the list for any points 
                //within the range, again we short out.  
                addPinsWithinRange(pins, index, 1, currentClusterPin, zoomLevel);

                clusteredPins.Add(currentClusterPin);
            }
        }
        return clusteredPins;
    }


    private static void addPinsWithinRange(List<ClusteredPin> pins, 
        int index, int direction, ClusteredPin currentClusterPin, int zoomLevel)
    {
        bool finished = false;
        int searchindex;
        searchindex = index + direction;
        while (!finished)
        {
            if (searchindex >= pins.Count || searchindex < 0)
            {
                finished = true;
            }
            else
            {
                if (!pins[searchindex].IsClustered)
                {
                    if (Math.Abs(pins[searchindex].GetPixelX(zoomLevel) 
                            - pins[index].GetPixelX(zoomLevel)) < clusterwidth)
                    {
                        if (Math.Abs(pins[searchindex].GetPixelY(zoomLevel) 
                                - pins[index].GetPixelY(zoomLevel)) < clusterheight)
                        {
                            //add to cluster
                            currentClusterPin.AddPin(pins[searchindex]);

                            //stop any further clustering
                            pins[searchindex].IsClustered = true;
                        }
                    }
                    else
                    {
                        finished = true;
                    }
                }
                searchindex += direction;
            }
        }
    }
}

A rework of the V1 logic refactored and converted to C# you notice some key changes.

Sort our pins in to a location order for processing
Do a loop of the pins, now themselves of type clusteredpin to allow for any preclustering in the data layer if appropriate.
If the pin has not already been assigned to a cluster it becomes the first pin in a new cluster and rather simply any pins that also have not been clustered and are with the set number of pixels (determined by the current zoom level) are added to that cluster.

Note the initial sorting allows us to simply look back in the list until we move out of bounds and then forward in the list. Without this we would have to loop the set of pins n^2.

Our JavaScript:


//Constants
var mWidth = 800;
var mHeight = 600;
var PopupPrefix = "VPOP";

//public varibles
var map = null;  
var pins = new Array();
var CurrentPopupID = 0;

//class for clustered pin
function clusteredPin(loc, bounds) {
	this.loc = loc;
	this.bounds = bounds;
} 

//Map initialisation on page load.       
function GetMap()       
{        
    // Firefox support - see VE wiki.
    var ffv = 0;
    var ffn = "Firefox/"
    var ffp = navigator.userAgent.indexOf(ffn);
    if (ffp != -1) ffv = parseFloat(navigator.userAgent.substring(ffp + ffn.length));
    // If we're using Firefox 1.5 or above override 
    //the Virtual Earth drawing functions to use SVG
    if (ffv >= 1.5) {
      Msn.Drawing.Graphic.CreateGraphic=function(f,b) 
        { return new Msn.Drawing.SVGGraphic(f,b) }
    }
    //setup map over Australia
    map = new VEMap('myMap');    
    map.LoadMap(new VELatLong(-27.5, 137), 4 ,'h' , false); 
    map.SetScaleBarDistanceUnit(VEDistanceUnit.Kilometers);
    //setup the function to get new data whenever the map changes
    map.AttachEvent("onchangeview", GetPinData);
    //turn off the standard popup and attach our custom handler
    VEPushpin.ShowDetailOnMouseOver = false;            
    VEPushpin.OnMouseOverCallback = PinHover;
    //get the data for the default view
    GetPinData();
}  

//Whenever the map view changes call the webservice for the latest data
function GetPinData()
{  
    //encode the current map bounds
    var points = new Array();
    points.push(map.PixelToLatLong(0,0));
    points.push(map.PixelToLatLong(mWidth,mHeight));
    var bounds = createEncodings(points);
    
    //get zoomlevel
    var zoom = map.GetZoomLevel();
    
    //call webservice
    SoulSolutions.ClusterArticle.MapService.GetClusteredMapData(bounds, 
        zoom, OnMapDataSucceeded, OnFailed);
}

//callback when data returns from web service
function OnMapDataSucceeded(results, eventArgs)
{
    //decode pins
    var result=results.split(",")
    var locs = decodeLine(result[0]);
    
    //clear existing pins
    pins = new Array();
    map.DeleteAllPushpins();
    pinID = 0;
    
    //put data into memory
    for(x = 0; x < locs.length; x++)
    {
         pins.push(new clusteredPin(locs[x],result[x+1]));
         AddPin(x, locs[x])
    }
}

//helper to add a VE pin.
function AddPin(pinID, latlon)
{
    //we use the details field to store the pin ID.
    var pin = new VEPushpin(pinID, latlon, "", "", pinID + "", "DefaultPinOffset");
    map.AddPushpin(pin);
}   

// on pin hover   
function PinHover(x, y, title, details)
{
    //we sotred the pin ID in the details field            
    var ID = details;
    var DivID = PopupPrefix + ID;
    
    var e=document.getElementById(ID+"_"+map.GUID);
    if(e!=null&&e!="undefined")
    {    
        //create the default VE popup with loading text.
        window.ero.setBoundingArea(
        new Microsoft.Web.Geometry.Point(0,0),
        new Microsoft.Web.Geometry.Point(document.body.clientWidth,
            document.body.clientHeight));
        window.ero.setContent("<div id='" + DivID + "'>Loading...</div>");
        window.ero.dockToElement(e);
        //get the content for the pin.
        getAJAXContent(ID,pins[ID].bounds,0);
    }
}

//change to another pin hover index
function ChangeContentPage(ID, startIndex)
{
    getAJAXContent(ID,pins[ID].bounds,startIndex);
}

//request content for popup
function getAJAXContent(ID, bounds, startIndex)
{
    //store the current pin ID to validate what popup for what data 
    CurrentPopupID=ID;
    //call the web service
    SoulSolutions.ClusterArticle.MapService.GetPushPin(bounds, 
        startIndex, OnContentSucceeded, OnFailed, ID);
} 

//Receive content for popup
function OnContentSucceeded(result, ID)
{ 
    //verify this is the data for the current popup.
    if (ID==CurrentPopupID)
    {
        //set the content
        $get(PopupPrefix + ID).innerHTML = result.Title + " - " + result.Details;
    }
}

// This is the failed callback function for all webservices.
function OnFailed(error)
{
    var stackTrace = error.get_stackTrace();
    var message = error.get_message();
    var statusCode = error.get_statusCode();
    var exceptionType = error.get_exceptionType();
    var timedout = error.get_timedOut();
   
    // Display the error.    
    var RsltElem = 
        "Stack Trace: " +  stackTrace + "<br/>" +
        "Service Error: " + message + "<br/>" +
        "Status Code: " + statusCode + "<br/>" +
        "Exception Type: " + exceptionType + "<br/>" +
        "Timedout: " + timedout;
        
        alert(RsltElem);
}

//Clean up all objects
function MapDispose()
{
    pins = null;
    if (map!=null)
    {
        map.Dispose();
        map = null;
    }
}

//set map to run onload and dispose on exit
if (window.attachEvent) {
	window.attachEvent("onload", GetMap);
	window.attachEvent("onunload", MapDispose);	
} else {
	window.addEventListener("load", GetMap, false);
	window.addEventListener("unload", MapDispose, false);
}

if (typeof(Sys) !== "undefined") Sys.Application.notifyScriptLoaded();

The comments in the code tell the story

We setup a standard VE map with a custom popup handler. We attach to the map’s onchangeview event that fires whenever the user pans or zooms.
We call our GetPinData function that gets the current map view, encodes it, and puts that together with the current zoom level and calls our web service directly from JavaScript. If you haven’t seen this before I hope with this simply example you will be converted. With one line of code we are calling a web service that can return a string, xml or JSON. Forget about proxy pages, parsing geoRSS and start using this!
The last two parameters in our web service call specify the call back function and the error call back function.
OnMapDataSucceeded is our successful callback for pin data. In this case I have opted for a custom string that provides some comma separated values that represent the pins needed for the map. For your situation you may want to use XML or JSON (I use this later).
The custom string is split on the comma and parsed into a clusteredpin object and added to the map. Note that the title and details for the pin were not passed to the client at this time. We load this data on demand.
PinHover is fired when one of our pins in moused over. We retrieve the ID from the details field, prepare a VE popup using the default ERO (this is the place to make your custom popup) and call our web service to get the actual popup text.
OnContentSucceeded is our callback function here and receives a JSON object that allows us to do some very cool things like access our object’s properties directly with no parsing. Here I directly access the title and details and write them to the popup’s innerHTML.

Sample Source Code

Download Source Code Here

You must download and install MS ASP.NET AJAX to run this code.

The sample code for this article gets it data from an XML file of Australian postcodes. I have cached this generated data in memory for performance, for small sets of static data this maybe an option for you. For larger sets of data I recommend storing the data in a database allowing you to query based on the map bounds.

Conclusion:

This improved clustering logic integrated with load on demand pushpin content and some serious location encoding has been able to transmit large numbers of pins and their content to the client in very small pieces on demand. What this does is to significantly speed up the application and provides a better experience for the user.

Future thoughts:

The example code was trimmed down in functionality to keep it simple and focus on the basics.

A big part of clustering is the ability to cluster different data sources and merge different types of pins together. The JavaScript shown in this article has been kept as a simple set of JavaScript functions rather than the new "object oriented" approach of using JavaScript classes in MS AJAX.
Additionally extra performance can be gained by further reducing the amount of data returned by your data tier based on the zoom level, a simple round() function combined with a group by lat /long in SQL can group data to an insignificant number of places for the required zoom level. Importantly this is where the bounds property of the pins comes in, the bounds must be expanded to include all the pins for the popup logic to work.
The UI can also be improved by only applying differences in pins on panning rather than refreshing all pins as in the example here. I call this pin differentiation.
A caching strategy may be implemented that provides oversized and standardised map view bounds from the client allowing for a lower number of possible requests to the web service and the ability to cache the response in memory. (this is usually very effective for zoom levels 1-5 where the maximum quantity of data is clustered and there are many requests for the same bounds, it is less effective for street level where there are many possible requests.)

I hope to bring all these concepts to you in the future but stay tuned for my next article that looks at throttling AJAX web services to improve performance in applications like Virtual Earth.

Have a comment or used this code on your site? Why don't you tell me about it at my blog

Please use the Manage Form Option to Develop your Form

Submit

*Required