Tessellating shapes on top of Bing Maps in a WP7 app - part 2

In my previous post I showed how to tessellate polygons over Bing Maps control. This was a demonstration of how to achieving tessellation over the map control for a WP7 app. The problem is this is a sub-optimal solution from a UI perspective. This post shows how I've changed to code to use an asynchronous pattern for creating the polygons. The code is available for download.

The primary problem with the solution is not the actual calculation but 'where' the calculation was being performed. All the work was done on the main UI (Dispatcher) thread. Simply this means the app would freeze whilst calculating the required the polygons for the currently visible map area.

The secondary problem was overloading the UI thread with rendering requests. Obviously all the visible polygons need rendering to the screen, but if you chuck a lot of work at the UI thread nothing else in your app is going to be able to do any UI work until all those requests have been processed. This means at best you'll get a jerk response or at worst you'll app will freeze.

And finally there isn't any caching for already calculated polygons for a geo-location, why would we want to repeat the same work over and over again.

The first approach to address these issues is the introduction of a service interface exposing the polygon methods asynchronously:

public interface ICreatePolygons
{
    ISettings Settings { get; }

    Polygon Polygon(GeoCoordinate location, int sides, double diameter, double offset, double offsetBearing, double startAngle);

    IObservable<Polygon> Square(GeoCoordinate centre, double size);
    IObservable<Polygon> AdjacentSquares(Polygon polygon);
    IObservable<Polygon> TessellateVisibleSquares(LocationRect visibleRectangle, IList<Polygon> existingPolygons, double size);

    IObservable<Polygon> Hexagon(GeoCoordinate centre, double size);
    IObservable<Polygon> AdjacentHexagons(Polygon polygon);
    IObservable<Polygon> TessellateVisibleHexagons(LocationRect visibleRectangle, IList<Polygon> visiblePolygons, double size);

    IObservable<Polygon> Triangle(GeoCoordinate centre, double size);
    IObservable<Polygon> AdjacentTriangles(Polygon polygon);
    IObservable<Polygon> TessellateVisibleTriangles(LocationRect visibleRectangle, IList<Polygon> visiblePolygons, double size);
}

As you can see all the methods apart from the Polygon method all return the polygons using the Rx (Reactive extensions) approach. This allows the actual work of calculating the polygons to be done on a background worker thread and solve the primary problem with the previous solution - freezing of the UI.

Shown below is the Hexagon method, what you can see is how I schedule the work onto the thread pool using Rx:

public IObservable<Polygon> Hexagon(GeoCoordinate centre, double size)
{
    try
    {
        this.ValidateDatum();

        return Observable.Create<Polygon>(obs =>
        {
            var disposable = new BooleanDisposable();
            Scheduler.ThreadPool.Schedule(o =>
            {
                var polygon = CreateHexagonImpl(centre, size);

                if (disposable.IsDisposed)
                {
                    return;
                }

                obs.OnNext(polygon);
                obs.OnCompleted();
            });

            return disposable;
        });
    }
    catch (Exception exn)
    {
        this.log.Write(FailedHexagon, exn);
        throw new ServiceException(FailedHexagon, exn);
    }
}

The secondary problem is solved easily with the primary change in place. The addition of a pause to the thread calculating the adjacent  polygons when tessellating the polygons for the map control.

Shown below is the recursive method used to calculate the visible adjacent polygons, what you'll see is the 'Thread.SpinWait' added every time an adjacent polygon is found and notified to any subscribers of the observer. This allows the background thread to cease work for a fixed amount of time (default is 66 ms) without causing a context switch. I found using a delay of 66 ms was enough to allow other threads\controls enough time to do their stuff, in my case this was allow the map control to render & download tiles and allow the use interact with the UI.

private void AddVisibleAdjacentPolygons(LocationRect visibleRectangle,
                                        Polygon polygon, ICollection<Polygon> newPolygons,
                                        Func<Polygon, IList<Polygon>> adjacentPolygonFunc,
                                        IObserver<Polygon> observer,
                                        BooleanDisposable disposable)
{
    foreach (var adjacentPolygon in adjacentPolygonFunc(polygon))
    {
        if (disposable.IsDisposed)
        {
            return;
        }

        if (!visibleRectangle.Intersects(adjacentPolygon.TileBoundingRectangle))
        {
            continue;
        }

        if (newPolygons.Contains(adjacentPolygon))
        {
            continue;
        }

        newPolygons.Add(adjacentPolygon);
        observer.OnNext(adjacentPolygon);

        Thread.SpinWait(this.settings.Throttle);

        this.AddVisibleAdjacentPolygons(visibleRectangle, adjacentPolygon, newPolygons, adjacentPolygonFunc, observer, disposable);
    }
}

The final problem is address by a standard pattern - caching. For this I'm using the WP7Contrib caching assembly. Before I show how I use the cache provider lets look at the generation times for different polygon tessellations.

Shown below is with no caching for the initial tessellation generation for 1 mile squares (on a device not in the emulator). As you can see the duration is 8247 ms:

When I move the map around in the local vicinity you can see the durations are about half of the start-up time when caching is not enabled:

When caching for adjacent polygons is enabled we get similar result for the initial start-up:

But when you compare the subsequent requests for the local vicinity you can see the time for generating the adjacent polygons has been reduced:

This demo makes use of the WP7Contrib in memory cache provider. The code for this demo app is available on SkyDrive.