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

I've finally got round to finishing this 3 part series about manipulating push pins on the Bing Maps control in WP7 - the final part took longer than expected!

In the first part I showed what happens to memory usage and UI performance when you have to many pins to show and how virtualizing the pins can reduce and improve both of these. In the second part I showed how you could optimise the HTTP calls to the back end services and how scrolling around the map control can be used to start and stop the requesting of more data.

In this part what I want to show is how you can group & cluster pins and effectively remove the idea of using a pins completely but still convey the geo-location data to the user. I'll be using techniques described in the polygons posts I wrote previously to help with the grouping & clustering of pins.

For this post like the previous posts I'm going to be using the UK Police API for street level crime, see here. This API gives a lot of data when used in an urban area like London and I'll using a location based in London to show how grouping and clustering can improve the UI experience.

At the end of part 2 we still had the same UI as part 1 but it was optimised for HTTP communication to the back end services - the first screen shot shows the map with no push pins and second shows the UI at the end of the second post:

As you can see the second screenshot indicates there was 313 crimes in the visible bounding rectangle - what you can't gain from interpreting the data with pins is there are multiple crimes for the same location. Plus when there are a lot crimes we start to loose site of the map control it's self and this defeats the point of using the map control in the first place. I've also highlighted the memory usage and at the end of part 2 the memory usage was around 48 Mb which to be honest is rather high for such a simple task.

What I did to get round these issues was to use a square polygon to represent a defined area of the visible map - very similar to the way I did this in the 'tessellating polygons' posts. I then calculated if a crime occurred within this defined area and if it did the crime was added to class representing the defined area ( class called 'CrimeShape'). The first screen shot below shows the same location zoomed out with no tessellation, the second shows the squares at this resolution. As you can see we can now show more crime data, well over 1000, but at this resolution it's still hard to gain a meaningful understanding. The third screen shot is the same place at a higher resolution:

So now we've a reduced number of pins and an increased amount of crime data. What's interesting about the third screen shot is it appears there is a crime hot spot centred around the traffic junction (intersection) - 269 crimes. The memory usage is also much better, even on the second screen shot we're now peaking memory at half the previous implementation peak value.

Drilling down further into the data by increasing the resolution of the map control (via the Zoom property) and gradually reducing the square area size I get the following set of screen shots:

What you see from the fifth screen shot above is the actually crimes are not occurring at the traffic junction (intersection) they are occurring just above to the left. Determining this kind of detail wouldn't have been possible if I'd just shown pins or used a low map resolution and a course grained area granularity.

Now I think this is a great way to use the polygons on top of the map control but the use of squares doesn't quite look or feel right - they are too regular. What is required is a more irregular pattern - how about hexagons or triangles!

I really like the hexagons, it reminds me of honeycomb...

Before I get into the code and how it is structured I want to show how this data can be interpreted to generate heat map instead of using pins all together:

I get a similar affect using hexagon shapes:

Looking at the code to generate the heat map first this was achieved by binding the crime counts for an area to the Fill property of the MapPolygon class. This is more difficult than it appears and the reason being the Fill property is not a dependency property so you can't bind to it. To get round this I derived from the MapPolygon class and made Fill a dependency property:

public sealed class MapPolygonExtended : MapPolygon
{
    public static readonly DependencyProperty FillProperty = DependencyProperty.RegisterAttached("Fill",
                                                                                                 typeof(Brush), 
                                                                                                 typeof(MapPolygonExtended), 
                                                                                                 new PropertyMetadata(new PropertyChangedCallback(FillChangedCallback)));

    public Brush Fill
    {
        get { return base.Fill; }
        set { base.Fill = value; }
    }

    private static void FillChangedCallback(DependencyObject d, DependencyPropertyChangedEventArgs e)
    {
        var dlb = (MapPolygonExtended)d;
        dlb.Fill = (Brush)e.NewValue;
    }
}

Then using this class I'm able to bind a property from the ViewModel to the Fill property:

As you can see from the XAML above I'm using a converter to convert the CrimeCount property from the CrimeShape Model to a solid brush colour. This is where the thresholds are defined for the polygon fill colour:

public sealed class CrimeCountConverter : IValueConverter
{
    public object Convert(object value, Type targetType, object parameter, CultureInfo culture)
    {
        var count = (int)value;

        if (count < 3)
        {
            return new SolidColorBrush(Colors.Green);
        }

        if (count < 10)
        {
            return new SolidColorBrush(Colors.Orange);
        }

        return new SolidColorBrush(Colors.Red);
    }

    public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
}

The CrimeShape Model aggregates the Polygon Model and is bound via the MapViewModel class. These are standard bindable Model & ViewModel classes. I'm not going to show the complete code for these classes, what is shown below is how the top level service is used to generate & group the crime data for rendering onto the map control. Whether the crime data is shown using a heat map or aggregated push pin is not defined in the ViewModel this is defined as shown above in the XAML.

private void BuildCrimeMap()
{
    if (ukCrimeMapSubscriber != null)
    {
        log.Write("MapViewModel: Shutting down existing crime map subscriber...");
        ukCrimeMapSubscriber.Dispose();
        ukCrimeMapSubscriber = null;
    }

    log.Write("MapViewModel: Building crime map...");

    if (shapeSelected)
    {
        crimeShapes.Clear();
    }
    else
    {
        var nonVisible = crimeShapes.Where(cs => !boundingRectangle.Intersects(cs.TileBoundingRectangle));
        nonVisible.ForEach(cs => crimeShapes.Remove(cs));
    }

    Busy = true;
    shapeSelected = false;

    Func<LocationRect, double, IObservable<CrimeShape>> func = (r, s) => Observable.Empty<CrimeShape>();
    if (selectedShape.Name.ToLower().Contains("square"))
    {
        func = (r, s) => ukCrimeMapService.TessellateSquares(boundingRectangle, selectedShape.Size);
    }
    else if (selectedShape.Name.ToLower().Contains("hexagon"))
    {
        func = (r, s) => ukCrimeMapService.TessellateHexagons(boundingRectangle, selectedShape.Size);
    }
    else if (selectedShape.Name.ToLower().Contains("triangle"))
    {
        func = (r, s) => ukCrimeMapService.TessellateTriangles(boundingRectangle, selectedShape.Size);
    }

    ukCrimeMapSubscriber = func(boundingRectangle, selectedShape.Size)
            .ObserveOnDispatcher()
            .Subscribe(crimeShape =>
            {
                if (crimeShapes.Any(cs => cs.Polygon == crimeShape.Polygon))
                {
                    return;
                }

                crimeShapes.Add(crimeShape);
            },
            exception => { },
            () =>
            {
                Busy = false;
                log.Write("MapViewModel: Crime shapes count = " + crimeShapes.Count);
            });
}

As you can see I'm using Rx (Reactive Extensions) again to deal with asynchronous nature of the tessellating function, not only is the method asynchronous it will return a stream of CrimeShape class instances, the number of theses is determined from the input parameters to the tessellating method. I really like the compact nature of the call to the Rx method - from the ViewModel perspective it is only 10 lines of code!

The service definition is shown below, as you can see I've tried to keep this simple and very clean:

public interface IUkCrimeMapService
{
    IObservable<CrimeShape> TessellateSquares(LocationRect boundingRectangle, double size);
    IObservable<CrimeShape> TessellateTriangles(LocationRect boundingRectangle, double size);
    IObservable<CrimeShape> TessellateHexagons(LocationRect boundingRectangle, double size);
}

This service interface is implemented by the UkCrimeMapService class. The responiblity of this class is two-fold:

Firstly the orchestration of calls to two other services that actually do the work of generating (tessellating) the polygons - ICreatePolygons, and the work to retrieve the crime data from the UK Police back end services - IUKCrimeService.

Secondly the assignment of polygons and crime data to correct CrimeShape class instance.

public sealed class UkCrimeMapService : IUkCrimeMapService
{
    private readonly ICreatePolygons polygonService;
    private readonly IUkCrimeService crimeService;
    private readonly ICacheProvider cacheProvider;
    private readonly ILog log;
    private readonly TimeSpan cacheTimeout;

    public UkCrimeMapService(ICreatePolygons polygonService, IUkCrimeService crimeService, ICacheProvider cacheProvider, ISettings settings, ILog log)
    {
        this.polygonService = polygonService;
        this.crimeService = crimeService;
        this.cacheProvider = cacheProvider;
        this.log = log;

        cacheTimeout = TimeSpan.FromMilliseconds(settings.CacheTimeout);
    }
}

The polygon generating service interface, ICreatePolygons, is defined as follows, I've removed several other mehtods to show only the relevant methods for this post. As you can see this has a similiar structure to the previous service interface:

public interface ICreatePolygons
{
    IObservable<Polygon> TessellateVisibleSquares(LocationRect visibleRectangle, double size);
    IObservable<Polygon> TessellateVisibleHexagons(LocationRect visibleRectangle, double size);
    IObservable<Polygon> TessellateVisibleTriangles(LocationRect visibleRectangle, double size);
}

The crime service also has a simply definition, the criterion takes a geo-location for the area you want retrieve crime data for, the data is returned in a one mile radius of the location:

public interface IUkCrimeService
{
    IObservable<StreetLevelCrimeResult> SearchStreetLevelCrime(StreetLevelCrimeCriterion criterion);
}

The way the call to the UkCrimeMapService orchestrates the calls to these services is as follows:

1. The polygons service is called to tessellate polygons for the required bounding rectangle asynchronously,
2. As each polygon is received a CrimeShape class instance is created and published, 
3. The number of calls required to retrieve all crimes for the polygon area is calculated,
4. This list and polygon are then pushed onto a queue to be processed by a background worker,
5. The background worker starts processing the queue and retrieve the crime data from the UK crime service,
6. Once all the data is returned the Rx observer is signalled as being complete and the background worker shut down.

We use caching where applicable in the services to avoid repetitively creating the same polygons or requesting the same crime data from the UK Police API.

Steps 1, 2, 3 & 4 are represented by the following two methods:

private IObservable<CrimeShape> TessellatingImpl(LocationRect boundingRectangle, double size, Func<LocationRect, double, IObservable<Polygon>> tessellatingFunc, string polygonName)
{
    var crimeWorker = new CrimeWorker();
    var localWorker = crimeWorker;

    return Observable.Create<CrimeShape>(obs =>
    {
        localWorker.SetObserver(obs);
        localWorker.Worker.DoWork += DoCrimeWork;
        localWorker.Worker.WorkerSupportsCancellation = true;
        localWorker.Worker.RunWorkerAsync(localWorker);

        Scheduler.ThreadPool.Schedule(mapThrottle, o =>
        {
            localWorker.TessellatingDisposable = tessellatingFunc(boundingRectangle, size)
                .SubscribeOn(Scheduler.ThreadPool)
                .ObserveOn(Scheduler.ThreadPool)
                .Subscribe(polygon => ProcessResponse(polygon, polygonName, localWorker),
                            FailedTessellatingPolygons,
                            () => CompletedTessellatingPolygons(localWorker));

            mapThrottle = TimeSpan.FromMilliseconds(MapSubsequentThrottle);
        });

        return localWorker.Disposable;
    }).Finally(() =>
    {
        log.Write("UkCrimeMapService: Shutting down background worker...");
        crimeWorker.Dispose();
        log.Write("UkCrimeMapService: Background worker shutdown...");
    });
}
      
private void ProcessResponse(Polygon polygon, string polygonName, CrimeWorker crimeWorker)
{
    var cacheKey = new CrimePolygonTuple(polygon);
    var crimeShape = cacheProvider.Get<CrimePolygonTuple, CrimeShape>(cacheKey);
    var criteria = Enumerable.Empty<StreetLevelCrimeCriterion>();
    if (crimeShape == null)
    {
        crimeShape = new CrimeShape(polygon, polygonName, polygon.Size);
        cacheProvider.Add(cacheKey, crimeShape, cacheTimeout);

        criteria = CalculateCrimeCriteria(crimeShape.TileBoundingRectangle);
    }
    else if (!crimeShape.IsComplete)
    {
        criteria = CalculateCrimeCriteria(crimeShape.TileBoundingRectangle);
    }

    if (crimeWorker.IsDisposed)
    {
        return;
    }

    criteria.ForEach(c => crimeWorker.PushQueue(new CrimeCriterionTuple { CrimeShape = crimeShape, Criterion = c }));

    var observer = crimeWorker.Observer;
    if (observer != null)
    {
        crimeWorker.Observer.OnNext(crimeShape);
    }
}

Could this code be used in a real world WP7 app?


The simple answer is NO!

The reason for this is not the quality of the code per-se but the fact it's using services that aren't well designed for this use. The code has all the required exception handlers, it also avoid doing work on the UI thread (Dispatcher) as much as possible and it manages the life time of the background worker correctly. What I mean by 'services that aren't well designed for this use' can be best demonstrated by the following three screen shots. The first shows the application running through the WP7 emulator and as we all know the emulator is a really bad place to measure app performance:

As you can see from the highlighted output window in visual studio the total time to create the polygons, retrieve the data from the UK police API backend services and render the heat map is less than 8 seconds!

You start thinking this is looking really promising and then you try it on a device. I tried this on my new Nokia Lumia 800:

The elapsed time has risen to 14 seconds, now you're probably thinking this isn't to bad either but what you have to remember is the device is tethered to a machine so the network type is ethernet and importantly I'm only request crime data for a small area.

When you start to look at a larger area it will increase the elapsed time greatly:

The screen shot above represents an area approximate to 3x2 miles and the time taken is over 6 minutes!

The majority of the time is consumed in retrieving the crime data, deserializing to JSON and mapping into model classes ready for use. If the UK Crime API was more mature then maybe there would be a better and more simpler way to retrieve this data - I'm going to talk about back end service design in a future post.

I've made the code available for download via SkyDrive, if you want to run the demo you'll need to register for an account with the UK Police API here.

The code makes extensive use of the WP7Contrib for help with accessing the backend HTTP services, caching of data in memory and the binding of Model classes to the UI.