How many pins can Bing Maps handle in a WP7 app - part 2

I wasn't planning this to span more than one post but it has and there's a good chance there'll be a third focusing back on the UI and how you can improve this further. This post is going to focus on what you can do with the service layer to improve the performance when loading a lot of pins into the Bing Maps control in a WP7 app.

To recap we reached a point where we are only showing the pins required for the bounding rectangle of the map control - even if the call to the service layer returned 500 hundred pins we were calculating which pins were actually visible and only adding them to the MapItemsControl class.

This was working well from a UI and general app perspective - we're no longer blocking the UI thread and we aren't chewing through to much memory. The main problem with this approach is the inefficiency in retrieving data from the UK crime web services. The data returned by these services is centred around the a geo-location for a radius of 1 mile, put simply they return all the reported crimes within a mile of a geo-location. The test location returns over 1000 crime geo-locations, we only want to show a subset of these, probably 150 or so. The screenshot from the last post shows this perfectly:

When I moved the map a request for more data is being made, even if I only move the map a couple of scrolls it is making a new request for data centred around the new geo-location. What became obvious was the actual data being displayed for this movement had already been requested previously. This forms the basis of the in-efficiency - requesting data that has already been requested by the app.

To recap we're getting the data when the ViewChangedEnd event is firing for the map control. We use the crime service in the service layer to request the data from the web services. It is then filtered before adding to the MapItemsControl class. I've shown a stripped down version of the call to the crime service in the service layer below:

private void HandleViewChangeEnd(object sender, MapEventArgs mapEventArgs)
{
    var criterion = new StreetLevelCrimeCriterion { Latitude = this.map.Center.Latitude, Longitude = this.map.Center.Longitude };
            
    this.crimeSubscriber = this.crimeService.SearchCrimeRelatedStreetLevelCrime(criterion)
        .ObserveOnDispatcher()
        .Subscribe(result =>
                        {
                            ...
                            ...
                            ...
                        });
}

What's required to prevent requesting the same data again and again (when scrolling) is caching in the service layer. The service layer should be able to workout what data you're requesting and then if the data has already been requested then it should return this already requested data instead of making a request to the back-end web services - standard caching pattern.

Now the service layer did have a caching pattern at the end of the first post. The problem is the cache key was based on an exact geo-location (contained in the Criterion class). So it would cache the crimes for a mile around an exact geo-location for every request. As you can imagine the chances of 2 requests being made with the same geo-location are very small:

var cacheKeyTuple = new CacheKeyTuple<NeighbourhoodCrimeCriterion>
    {
        Name = "SearchNeighbourhoodCrimes",
        Value = criterion.DeepClone()
    };

    var cachedResult = this.cacheProvider.Get<CacheKeyTuple<NeighbourhoodCrimeCriterion>, NeighbourhoodCrimeResult>(cacheKeyTuple);
    if (cachedResult != null)
    {
        this.log.Write("UkCrimeService: SearchNeighbourhoodCrimes results retrieved from cache, hash code - {0}", criterion.GetHashCode());
        return Observable.Return(cachedResult).AsObservable();
    }

The screen shot below shows how inefficient this is. When the app is started in location 1 all the crimes within a 1 mile are requested around the map centre point (shown by the pins inside the red circle). When the map is scrolled to locations 2 & 3 then it shouldn't have to request more data from the back-end web services it should be returned from the cache.

So the output in visual studio is shown below, you can see the inefficiency in the multiple requests to the web services, I've also highlighted the geo-location information sent to the web services.

To make this more efficient we have to apply some high school mathematics - Pythagorean Theorem. We're going to use this to calculate the largest square we can get inside the circle described by the crimes returned from the back-end web service. Once we know the length of the side of the square we can use trigonometry to calculate the geo-locations of the corners of the square. Finally when we know this we'll be able to calculate if the map control bounding rectangle is contained within the square, if it is then we don't need to make a request to the web services we can use the cached data, if not then a request will be made to the web services for more data.

First, applying Pythagorean Theorem, we are going to use metric units so instead of a radius of 1 mile it will be 1.60934 km.

By the symmetry of the diagram the center of the circle is on the diagonal AB of the square. The length of AB is 3.21868 km and the lengths of BC and CA are equal. The Pythagorean Theorem then says that

(BC * BC) + (AC * AC) = (AB * AB)

Hence

(BC * BC) + (CA * CA) = 10.35990

But since this is a square then BC is equal to AC, hence

2 * (BC * BC)  = 10.35990

and therefore

|(BC * BC)  = 5.17995

Taking the square root on my calculator I get

BC = 2.27595


The square has the sides of length 2.27595 Km.


Second, we use trigonometry to calculate the geo-locations of the 4 corners of the square. We use the following Haversine formula to calculate these, don't worry I've implemented this in code. It's shown here for completeness:

	lat2 = asin(sin(lat1)*cos(d/R) + cos(lat1)*sin(d/R)*cos(θ))
	lon2 = lon1 + atan2(sin(θ)*sin(d/R)*cos(lat1), cos(d/R)−sin(lat1)*sin(lat2))

θ is the bearing (in radians, clockwise from north);
d/R is the angular distance (in radians), where d is the distance travelled and R is the earth’s radius

Finally, these have been implemented in the CircularLocation class. It allows the setting of the radius and centre point and it will calculate the largest contained rectangle inside the described circle. The full implementation is shown below:

public sealed class CircularLocation
{
    private const double EarthRadius = 6371;

    private GeoCoordinate centerPoint;
    private double radius;

    private LocationRect containedRect;

    public GeoCoordinate CenterPoint
    {
        get
        {
            return centerPoint;
        }
        set
        {
            this.centerPoint = value;
            this.containedRect = null;
        }
    }
        
    public double Radius
    {
        get
        {
            return this.radius;
        }
        set
        {
            this.radius = value;
            this.containedRect = null;
        }
    }

    public LocationRect ContainedRect
    {
        get
        {
            if (this.containedRect == null)
            {
                this.containedRect = this.CalculateContainedRect();
            }

            return this.containedRect;
        }
    }

    public bool IsRectangleContained(LocationRect boundingRectangle)
    {
        var containedRect = this.ContainedRect;

        if (boundingRectangle.North > containedRect.North)
        {
            return false;
        }

        if (boundingRectangle.East > containedRect.East)
        {
            return false;
        }

        if (boundingRectangle.South < containedRect.South)
        {
            return false;
        }

        if (boundingRectangle.West < containedRect.West)
        {
            return false;
        }
            
        return true;
    }

    private LocationRect CalculateContainedRect()
    {
        var hypotenuse = 2 * this.radius;

        var side = Math.Sqrt(hypotenuse * hypotenuse / 2);
        var halfSide = side / 2;

        var directNorth = this.CalculateDestination(this.centerPoint, halfSide, 0);
        var directSouth = this.CalculateDestination(this.centerPoint, halfSide, 180);
        var directEast = this.CalculateDestination(this.centerPoint, halfSide, 90);
        var directWest = this.CalculateDestination(this.centerPoint, halfSide, 270);

        return new LocationRect(directNorth.Latitude, directWest.Longitude, directSouth.Latitude, directEast.Longitude);
    }

    private GeoCoordinate CalculateDestination(GeoCoordinate startLocation, double distance, double bearing)
    {
        var lat1 = DegreeToRadian(startLocation.Latitude);
        var long1 = DegreeToRadian(startLocation.Longitude);

        var bar1 = DegreeToRadian(bearing);
        var angularDistance = distance / EarthRadius;

        var lat2 = Math.Asin(Math.Sin(lat1) * Math.Cos(angularDistance) + Math.Cos(lat1) * Math.Sin(angularDistance) * Math.Cos(bar1));

        var lon2 = long1 + Math.Atan2(Math.Sin(bar1) * Math.Sin(angularDistance) * Math.Cos(lat1),
                                        Math.Cos(angularDistance) - Math.Sin(lat1) * Math.Sin(lat2));


        var destinationLocation = new GeoCoordinate(RadianToDegree(lat2), RadianToDegree(lon2));

        return destinationLocation;
    }

    private double DegreeToRadian(double angle)
    {
        return Math.PI * angle / 180.0;
    }

    private double RadianToDegree(double angle)
    {
        return angle * (180.0 / Math.PI);
    }
}

This class is then used in the modified crime service as the key for an item added to the cache. When a request is made to the crime service it will recurse the keys added to the cache looking for an instance that
can contain the requested bounding rectangle of the map control - simple!

Obviously how the key is created and added to the cache has been modified, but this is nothing more than creating of an instance of the CircularLocation class and setting the required properties. Shown below is the crime service method.

public IObservable<StreetLevelCrimeResult> SearchStreetLevelCrime(StreetLevelCrimeCriterion criterion)
{
    try
    {
        var centrePoint = criterion.BoundingRectangle.Center;
                
        var keys = this.cacheProvider.Keys<CircularLocation>();
        var key = keys.FirstOrDefault(k => k.IsRectangleContained(criterion.BoundingRectangle));

        if (key != null)
        {
            var cachedResult = this.cacheProvider.Get<CircularLocation, StreetLevelCrimeResult>(key);

            this.log.Write("UkCrimeService: SearchStreetLevelCrime results retrieved from cache, hash code - {0}", criterion.GetHashCode());
            return Observable.Return(cachedResult).AsObservable();
        }

        object[] @params = new[] { propertyEncoder.Encode(centrePoint.Latitude), propertyEncoder.Encode(centrePoint.Longitude) };
                
        return resourceHandlerFactory.Create()
            .ForType(ResourceType.Json)
            .UseUrlForGet(this.settings.StreetCrimeUrl)
            .WithBasicAuthentication(this.settings.Username, this.settings.Password)
            .Get<List<CrimeRelated.StreetLevel.Resources.Result>>(@params)
            .Select(response =>
            {
                var result = ProcessResponse(response);

                var circularLocation = new CircularLocation { CenterPoint = centrePoint, Radius = SearchDistance };
                var containedRect = circularLocation.ContainedRect;
                this.log.Write("UkCrimeService: SearchStreetLevelCrime contained rectangle - {0}", containedRect);

                this.cacheProvider.Add(circularLocation, result, this.cacheTimeout);

                return result;
            });
    }
    catch (Exception exn)
    {
        var message = string.Format(FailedPoliceStreetLevelCrime, exn.Message);
        this.log.Write(message);
        throw new Exception(message, exn);
    }
}

Now when I run the app I get better performance when scrolling within the calculated contained rectangle. Only when you're no longer inside the contained rectangle is a request for more data made to the back-end web services. This can be observed in the output window of visual studio. The highlighted area shows the cached results being returned, eventually I scroll outside of the contained rectangle and another request to the back-end web services is made.

Back to the original question - How many pins can Bing Maps handle in a WP7 app?

This post hasn't really changed the answer to this question from the previous post, it has shown you how you can be more efficient with your requesting of data when you're only showing a subset of the returned data.

Part3 will focus back on the UI and how conflation of pins can will help the user experience.

I've put the code for this version up on SkyDrive, you'll need a username & password for the UK crime stats service to run the code.