How many points can you add to Virtual Earth?

I hear this question from time to time. Well, there is no hard limit in the API but since the points are added through JavaScript-methods on the client your application will have slower response times the more points you add. A reasonable upper limit depends on the performance of the client-machine as well as the methods you use. Hold on, is there more than one method to add VEShape-objects to a map? Not really but since version 6 you can add the shapes either individually or through bulk-methods.

Bulk-Loading of VEShape-Objects

I did some performance test on my standard laptop with an application where I retrieve increasing amounts of POI from a database. The general principle of the database access is explained in one of my previous postings.

image

In the first test, I used exactly this approach and the web handler will return a JavaScript which adds individual VEShape-Objects like this:

var shape0=new VEShape(VEShapeType.Pushpin, new VELatLong(51.46102, -0.98861));
shape0.SetCustomIcon('./IMG/blue.png');
shape0.SetTitle("My Title 1");
slPOI.AddShape(shape0);
var shape1=new VEShape(VEShapeType.Pushpin, new VELatLong(51.45506, -0.93939));
shape1.SetCustomIcon('./IMG/blue.png');
shape1.SetTitle("My Title 2");
slPOI.AddShape(shape1);
var shape2=new VEShape(VEShapeType.Pushpin, new VELatLong(51.45971, -0.97639));
shape2.SetCustomIcon('./IMG/blue.png');
shape2.SetTitle("My Title 3");
slPOI.AddShape(shape2);

In the second test I modified the web handler in a way that it returns an JavaScript which creates an array of VEShape-Objects and adds all of them at a time:

var myPOIArray = new Array();
var shape0=new VEShape(VEShapeType.Pushpin, new VELatLong(51.46102, -0.98861));
shape0.SetCustomIcon('./IMG/blue.png');
shape0.SetTitle("My Title 1");
myPOIArray.push(shape0);
var shape1=new VEShape(VEShapeType.Pushpin, new VELatLong(51.45506, -0.93939));
shape1.SetCustomIcon('./IMG/blue.png');
shape1.SetTitle("My Title 2");
myPOIArray.push(shape1);
var shape2=new VEShape(VEShapeType.Pushpin, new VELatLong(51.45971, -0.97639));
shape2.SetCustomIcon('./IMG/blue.png');
shape2.SetTitle("My Title 3");
myPOIArray.push(shape2);
slPOI.AddShape(myPOIArray);

The impact on performance is quite obvious and becomes more dramatically the more points you add:

image

However, there is another point to consider: the more points you have the less readable a map becomes. In the screenshot below you see a 800×600 pixel map with ~700 POI:

image

You see that the icons are in some places overlapping and hiding each other. To improve the readability you should consider clustering.

Clustering

There are 2 general approaches: Client-Side and Server-Side Clustering. Richard Brundritt has described the ‘client-side clustering‘ on ‘Via Windows Live‘. The advantage of this approach is, that you have no dependencies in the middleware and the backend but since the clustering itself is done on the client, it requires that all data are being transferred to the client in the first place. Thus performance decreases with the amount of points of interest.

image

You also see that there is a dependency on the zoom-level. This is because the clustering becomes the more CPU intensive the more points you have to group into one cluster. Thus Ricky introduced a threshold for the zoom-level in his code. This approach keeps the performance in reasonable limits but it also hides the POI for lower zoom-levels.

image

John O’Brien has published the code for server-side clustering on ‘Via Windows Live‘. John works with Virtual Earth from the very beginning and you can trace the sample back to it’s origins in earlier Virtual Earth versions. In the meantime it is incorporated in his own framework with lot’s of helper functions and JavaScript-classes.

Let’s have a look at the basic principle of clustering. We attach an event to the VEMap-object and re-create the cluster whenever we pan or zoom the map. To do so we execute an AJAX-call to a web handler which

  1. retrieves all POI on the visible map from the database.
  2. creates a virtual grid and groups all POI within this grid into a clustered POI.
  3. sends the clustered POI to the AJAX-call

image

For database access without clustering we use only the latitudes and longitudes of the bounding box of the map as URL-parameters in our AJAX-call. For the server-side clustering we also need the height and width of the map as well as the zoom-level to create the virtual grid.

As mentioned above we use Virtual Earth events to capture whenever we panned or zoomed the map and recreate the cluster. This would go through the complete procedure even if we pan the map for only 1 pixel. To remove some of this load we will introduce a threshold which only refreshes the map if we pan for more than this threshold. In the example below this threshold is set to 100 pixels. Here is my complete JavaScript:

window.onload = GetMap;
window.onresize = Resize;

//Map
var map = null;
var mapWidth = null;
var mapHeight = null;

//To query or not to query
var cpLatLongOld = null;
var panThresHold = 100;

//VEShapeLayer
var slPOI = new VEShapeLayer();
var slAllPOI = new VEShapeLayer();

function GetMap()
{
    map = new VEMap('divMap');
    map.LoadMap(new VELatLong(51.461962075378054, -0.9260702133178665), 18, VEMapStyle.Shaded, false);
    Resize();
    
    //Add VEShapeLayer
    map.AddShapeLayer(slPOI);
}

//Resize map and controls whenever the size of the browser window changes
//Also load the minimap
function Resize()
{
    var mapDiv = document.getElementById("divMap");
    var ctrlDiv = document.getElementById("divCtrl");
    var windowWidth = document.body.clientWidth;
    var windowHeight = document.body.clientHeight;
    mapWidth = windowWidth - 210;
    mapHeight = windowHeight  - 70;
    mapDiv.style.width = mapWidth + "px";
    mapDiv.style.height = mapHeight + "px";
    ctrlDiv.style.height = (windowHeight - 60) + "px";
    map.Resize(mapWidth, mapHeight);
    map.ShowMiniMap(mapWidth-205, 13, VEMiniMapSize.Large);
}

//Database Layers
function BulkAddShapeClusterServer(control)
{
    if (document.getElementById(control).checked == false) 
    {
        //Delete all Shaps in Layer
        slPOI.DeleteAllShapes();
        
        //Detach Map-Events
        map.DetachEvent("onstartpan", RememberCP);
        map.DetachEvent("onendpan", ToQueryOrNotToQuery);
        map.DetachEvent("onendzoom", ServerSideCluster);
        
        //Empty the Textboxes
        document.getElementById('txtNumPOI').value = "";
        document.getElementById('txtMyTime').value = ""; 
        document.getElementById('txtQuery').value = "";
    }
    else
    {
        //Attach Map-Events
        map.AttachEvent("onstartpan", RememberCP);
        map.AttachEvent("onendpan", ToQueryOrNotToQuery);
        map.AttachEvent("onendzoom", ServerSideCluster);
        ServerSideCluster();
    }
}

//Remeber centre point before the panning
function RememberCP()
{
    cpLatLongOld = map.GetCenter();
}

//To query or not to query
function ToQueryOrNotToQuery()
{
    var cpLatLongNew = map.GetCenter();
    var cpPixelOld = map.LatLongToPixel(cpLatLongOld);
    var cpPixelNew = map.LatLongToPixel(cpLatLongNew);
    var x = Math.abs(cpPixelOld.x - cpPixelNew.x);
    var y = Math.abs(cpPixelOld.y - cpPixelNew.y);
    
    if (x > panThresHold || y > panThresHold)
    {
        ServerSideCluster()
    }
    else
    {
        document.getElementById('txtNumPOI').value = "";
        document.getElementById('txtMyTime').value = ""; 
        document.getElementById('txtQuery').value = "FALSE";
    }
}

//Call the web service
function ServerSideCluster()
{
    slPOI.DeleteAllShapes();
    
    //Retrieve the boundaries of the mapview
    var ulPixel  = new VEPixel(0, 0);
    var brPixel  = new VEPixel(mapWidth, mapHeight);
    var ulLatLon = map.PixelToLatLong(ulPixel);
    var ulLat = ulLatLon.Latitude;
    var ulLon = ulLatLon.Longitude;
    var brLatLon = map.PixelToLatLong(brPixel);
    var brLat = brLatLon.Latitude;
    var brLon = brLatLon.Longitude;
    var lvl = map.GetZoomLevel();
    
    //Build URL to call the server
    var url="./LoadCluster.ashx?";
    url += "&ulLat=" + ulLat;
    url += "&ulLon=" + ulLon;
    url += "&brLat=" + brLat;
    url += "&brLon=" + brLon;
    url += "&lvl=" + lvl;
    url += "&width=" + mapWidth;
    url += "&height=" + mapHeight;

    //Get the appropriate XMLHTTP object for the browser
    var xmlhttp = GetXmlHttp();
    
    //if we have a valid XMLHTTP object
    if (xmlhttp)
    {
        xmlhttp.Open("GET", url, true); // varAsynx = true
        
        //set the callback
        xmlhttp.onreadystatechange = function()
        {
            if (xmlhttp.readystate ==4) //4 is a success
            {
                //server code creates JavaScript "on the fly"
                var result = xmlhttp.responseText;
                //start the timer
                var myStart = new Date();
                //execute using eval()
                eval(result);
                //stop the timer
                var myEnd = new Date();
                var myTime = myEnd-myStart;
                document.getElementById('txtNumPOI').value = slPOI.GetShapeCount();
                document.getElementById('txtMyTime').value = myTime; 
                document.getElementById('txtQuery').value = "TRUE";
            }
        }
        xmlhttp.send(null);
    }
}

//Helper-Function
function GetXmlHttp()
{
    var x = null;
    try
    {
        x = new ActiveXObject("Msxml2.XMLHTTP");
    }
    catch (e)
    {
        try
        {
            x = new ActiveXObject("Microsoft.XMLHTTP");
        }
        catch (e)
        {
            x = null;
        }
    }
    if (!x && typeof XMLHttpRequest != "undefined")
    {
        x = new XMLHttpRequest();
    }
    return x;
}

Now let’s move on to the web handler. When we process the request we first make sure that the culture is set to something which interprets the "." as a decimal separator before we fetch the URL-parameters. Then we set up an array for our virtual grid. The size of the array depends on the size of the map and the size of the grid (here: 40 pixels). Now we convert the latitudes and longitudes of the upper left corner into pixel coordinates. These pixel-coordinates will be the origin of our virtual grid and please note: this is not the same as a VEPixel-object where the upper-left corner of the visible area is always (0, 0). The pixel coordinates we calculate here are relative to an origin which covers the whole world. For the calculation we use the algorithm which has been published by Joe Schwartz. The code is listed at the bottom of this listing.

Now we set up our database-query and while we read the database records we calculate the pixel coordinates, determine the position in our virtual grid and append to our array of clustered pins. Finally we loop through our array and create the JavaScript which is then returned to the AJAX-call.

'Constants for the Clustering
'(addressable area in VE)
Private Const MinLatitude As Double = -85.05112878
Private Const MaxLatitude As Double = 85.05112878
Private Const MinLongitude As Double = -180
Private Const MaxLongitude As Double = 180
'Grid-Size
Private Const GridSize As Integer = 40

Public Sub ProcessRequest(ByVal context As HttpContext) Implements IHttpHandler.ProcessRequest
    'set culture to en-UK to avoid potential problems with decimal-separators
    System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.CreateSpecificCulture("en-UK")

    'Get the URL-Parameters
    Dim ulLat As String = context.Request.Params("ulLat")
    Dim brLat As String = context.Request.Params("brLat")
    Dim ulLon As String = context.Request.Params("ulLon")
    Dim brLon As String = context.Request.Params("brLon")
    Dim lvl As Integer = context.Request.Params("lvl")
    Dim mapWidth As Integer = context.Request.Params("width")
    Dim mapHeight As Integer = context.Request.Params("height")
    
    'Set up a grid for the Clustering
    Dim numXCells = CInt(Math.Ceiling(mapWidth / GridSize))
    Dim numYCells = CInt(Math.Ceiling(mapHeight / GridSize))
    Dim numCells As Integer = numXCells * numYCells - 1
    Dim gridCells()() As Object = New Object(numCells)() {}
    
    'Determine PixelX and PixelY of upper left corner
    Dim ulTotalX As Integer
    Dim ulTotalY As Integer
    LatLongToPixel(ulLat, ulLon, lvl, ulTotalX, ulTotalY)

    'Query database(s) and create JavaScript
    Dim poiTotalX As Integer
    Dim poiTotalY As Integer
    Dim poiMapX As Integer
    Dim poiMapY As Integer
    Dim settings As ConnectionStringSettings
    settings = ConfigurationManager.ConnectionStrings("HannesPOI")
    Dim sb As StringBuilder = New StringBuilder
    sb.Append("var myPOIArray = new Array();")
    Dim i As Integer = 0
    Dim myConn As New SqlConnection(settings.ConnectionString)
    myConn.Open()
    Dim myQuery As String = "SELECT Latitude, Longitude, Name FROM UK_low_bridges_all WHERE (Latitude BETWEEN " + brLat + " AND " + ulLat + ") AND (Longitude BETWEEN " + ulLon + " AND " + brLon + ")"
    Dim myCMD As New SqlCommand(myQuery, myConn)
    Dim myReader As SqlDataReader = myCMD.ExecuteReader()
    While myReader.Read()
        'Determine PixelX and PixelY of POI
        LatLongToPixel(myReader(0), myReader(1), lvl, poiTotalX, poiTotalY)
        poiMapX = poiTotalX - ulTotalX
        poiMapY = poiTotalY - ulTotalY
        'Populate the array with clustered pins
        For x = 0 To numXCells - 1
            If (x * GridSize <= poiMapX) And (poiMapX < (x + 1) * GridSize) Then
                For y = 0 To numYCells - 1
                    If (y * GridSize <= poiMapY) And (poiMapY < (y + 1) * GridSize) Then
                        Dim myClusteredPin(2) As Object
                        If gridCells(x * y) Is Nothing Then
                            myClusteredPin(0) = 1
                            myClusteredPin(1) = myReader(0).ToString + ", " + myReader(1).ToString
                            myClusteredPin(2) = myReader(2).ToString
                        Else
                            myClusteredPin = gridCells(x * y)
                            myClusteredPin(0) = myClusteredPin(0) + 1
                            myClusteredPin(2) = myClusteredPin(2) + "<hr>" + myReader(2).ToString
                        End If
                        gridCells(x * y) = myClusteredPin
                    End If
                Next
            End If
        Next
    End While
    myReader.Close()
    myConn.Close()
    
    'Create the pins
    Dim myPins As String = ""
    For j = 0 To numCells
        If gridCells(j) IsNot Nothing Then
            Dim myClusteredPin = gridCells(j)
            myPins = myPins + _
                "var shape" + i.ToString + "=new VEShape(VEShapeType.Pushpin, new VELatLong(" + myClusteredPin(1) + "));" + _
                "shape" + i.ToString + ".SetTitle(" + """" + "There are " + myClusteredPin(0).ToString + " POI" + """" + ");"
            If myClusteredPin(0) > 5 Then
                myPins = myPins + "shape" + i.ToString + ".SetDescription(" + """" + "There are more than 5 POI in this cluster zoom closer to see the details." + """" + ");"
            Else
                myPins = myPins + "shape" + i.ToString + ".SetDescription(" + """" + myClusteredPin(2).ToString + """" + ");"
            End If
            If myClusteredPin(0) > 1 Then
                myPins = myPins + "shape" + i.ToString + ".SetCustomIcon('./IMG/red.png');"
            Else
                myPins = myPins + "shape" + i.ToString + ".SetCustomIcon('./IMG/blue.png');"
            End If
            myPins = myPins + "myPOIArray.push(shape" + i.ToString + ");"
            i = i + 1
        End If
    Next
    
    sb.Append(myPins)
    sb.Append("slPOI.AddShape(myPOIArray);")
    context.Response.Write(sb.ToString())
End Sub

    'Clips a number to the specified minimum and maximum values
    Private Shared Function Clip(ByVal n As Double, ByVal minValue As Double, ByVal maxValue As Double) As Double
        Return Math.Min(Math.Max(n, minValue), maxValue)
    End Function
    
    'Determine the offset off the map
    Public Shared Function Offset(ByVal lvl As Integer) As UInt32
        Return 256 << lvl
    End Function

    'Convert Latitude and Longitude to VEPixel
    Public Shared Sub LatLongToPixel(ByVal latitude As Double, ByVal longitude As Double, ByVal lvl As Integer, ByRef pixelX As Integer, ByRef pixelY As Integer)
        latitude = Clip(latitude, MinLatitude, MaxLatitude)
        longitude = Clip(longitude, MinLongitude, MaxLongitude)
 
        Dim x As Double = (longitude + 180) / 360
        Dim sinLatitude As Double = Math.Sin(latitude * Math.PI / 180)
        Dim y As Double = 0.5 - Math.Log((1 + sinLatitude) / (1 - sinLatitude)) / (4 * Math.PI)
 
        Dim mapSize As UInt32 = Offset(lvl)
        pixelX = CType(Clip(x * mapSize + 0.5, 0, mapSize - 1), Integer)
        pixelY = CType(Clip(y * mapSize + 0.5, 0, mapSize - 1), Integer)
    End Sub

That’s it. In my tests I never exceeded 200 milliseconds to render the POI in the client (this is without the processing in the web handler and the database query).

image

The complete sample application is available here.

Advertisements
This entry was posted in Virtual Earth. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s