I am Duncan Parkes,  a developer for mySociety, a non-profit full of web geeks. One of the things we try to do well here is to take complicated data and turn it into really usable tools – tools which are attractive to people who aren’t web (or data) geeks.

For some considerable time I’ve been working on Mapumental – a project that is about turning public transport timetable data into pretty, interactive maps featuring isochrones, shapes that show people where they can live if they want to have a commute of a particular time. You can play with the new version we just launched here. That particular map shows the commuting options to where the Queen lives. Slide the slider for full effect.

There are a couple of hard problems that need solving if you want to build a service with an interactive journey times overlay like this. You need to be able to calculate a *huge* number of journeys extremely quickly, and you need to be able to make custom map layers so that it all looks nice. But what I think might be most interesting for you is the way in which the contours get rendered on top of the maps.

It all started about three years ago, when the first version of the app – co-developed with the geniuses at Stamen – used Flash/Flex to draw contours on the maps, and to let people play with them. You can still play with a couple of versions of that technology from way back in 2007, that is, unless you’re using an iPad or iPhone, which of course don’t do Flash.

Colour Cycling

What was going on inside this Flash app was as follows. We needed to show the user any one of hundreds of different combinations of journey times (5 minutes, 12 minutes, 56 minutes, etc) depending on where they set the slider. Sending each one from the server as a tiled map overlay would be dead slow. Even Google – who have chosen to send new tiles each time – end up with a service which is surprisingly slow (try choosing a different time on this map).

With some help from Stamen, we decided that the way of making it possible to show many different contours very quickly was send the client just one set of tiles, where each tile contained all the data for a variety of journey times. What does that mean? Simple: each colour in the tile represented a different number of minutes travelling on the map. So a batch of pixels that are colour X, all show places that are 15 minutes from the centre of the map.

So, in this old Flash system, when you slide the slider along, the Flash app makes some of the coloured pixels opaque, and the others transparent. It was, in short, a form of colour cycling, familiar to lovers of 8 and 16 bit computer games.

However, from about 2010 onwards, the march of iOS spelt the end of Flash. And that meant that we couldn’t launch a shiny new site based on this technology, as lovely as it was. We had to work out some approach that would use modern web standards instead.

The Death of Flash Makes Life Difficult – for a while

How do we replicate the experience of dragging a slider and seeing the map change like in the original Mapumental demo, but without Flash? One of the things that made the original Mapumental nice to use was how smooth the image changes were when you dragged the slider. Speed really matters to create that sort of organic effect that makes the demo so mesmerising.

So as we started to tackle the question “How do we make this work in a post-Flash world?”. And the first thought was “Let’s do away with those map tiles, filled with all that journey time data!”. After all – why send any tiles to a modern browser, if it can just render nice shapes on the fly?

So we had a go. Several goes. At first we tried rendering SVG circles around each public transport stop – but that was too slow, particularly when zoomed out. Then we tried rendering circles in Canvas, and whilst that was OK in sparsely populated places it sucked in the cities, where people would actually want to use it.

Eventually, we decided that as wonderful and powerful as modern web rendering techniques are, if you exclude WebGL (on the grounds that so few people have it still), all the current techniques result in pages that just hammer your browser, whilst producing an experience which isn’t up to our previous Flash-based standards. To see this in action, see the wonderful Mapnificent site, developed by the super talented Stefan Wehrmeyer. He’s a great guy and a friend of mySociety, but the Javascript circle rendering just grinds, and that’s with far, far fewer data points than we have in our system. (Sorry for potentially crashing your browser there. This is in the interest of Science.)

Back to Colour Cycling – Using Web Standards

So, we thought, why not look again at colour cycling the pixels within pre-rendered map tiles? After all, there are some examples out there, like this waterfall, all in Javascript.

So, I had a bit of a look at the waterfall. It seems to work by holding in memory a structure which has all the pixels which change and all the colours they should change to and when. This works beautifully for the waterfall picture, but only a limited number of the pixels in that image actually change colour, and the image is quite small. For a full screen web browser with a big map in, this didn’t seem promising, although I’d love to see someone try.

Then I thought: browsers have always been very good at displaying images quickly – that’s sort of vital. Perhaps we could get our tile generating server to output PNG images where, as before, the colours represent travel times, but using a palette. Then by putting this in a canvas layer in the JavaScript mapping framework Leaflet, and by changing the palette of the images on the canvas as the slider is dragged, we could get our animation.

Unfortunately, there is no way to change the palette of an image that you’ve put on the canvas. In fact, there’s no way to change the palette of an HTML img element: all you can do is assign it a new src attribute.

But this gets back to the original problem – we don’t want to download new mapping for every different position on the time slider. We definitely can’t afford to have the client downloading a new image source for every tile whenever the slider is moved, so we had to find a way to make that src at the client end and get that into the src attribute.

The Breakthrough – Data URIs and Base64 encoding

So we started trying data URIs. For those of you not familiar, these allow you to put a whole object into your HTML or CSS, encoded in Base64. They’re commonly used to prevent pages having to make extra downloads for things like tiny icons.

So I thought, “Here’s a way we can set an image src in JavaScript to something we’ve calculated, rather than something we’ve downloaded.” And this turned out to be the key insight that allows for the relatively smooth, attractive overlays you see in Mapumental today.

My new plan was that the client, having downloaded each palette-based image, would make a Base64 encoded version of it, which it could then use to build a version with the right palette and assign this as a data URI of the tile.

However Base64 encoding all these images in the JavaScript seemed like unnecessary processing to do there, so the final evolution of this technique was to do the Base64 encoding at the tile server end, and while we’re at it, not to bother sending over the parts of the image that we always replace at the client end.

So in summary, what we built does this:

1. The server calculates the journey times and renders them to palette-based tiles.
2. It sends these to the client, encoded in Base64, and with the initial bits up to the palette and transparency chunks removed.
3. At the client end, we have a pre-prepared array of 255 ‘starts’ of PNGs that we combine with the later parts of the ’tiles’ from the tile server to make data URIs.
4. When you drag the slider it combines the appropriate ‘start’ of a PNG with the bulk of the tile that has been downloaded from the server, and assigns that to the src attribute of the tile.

And that’s how the nice overlays on Mapumental work. But as so often in coding, the really interesting devil is in the detail – read on if you’re interested.

Diving into Base64 and the PNG file format – The Gnarly Bits

So – why are there 255 of these ‘starts’ of these PNGs, and what do I mean by a ‘start’ anyway?

PNG files are divided up into an 8 byte signature (the same for every PNG file) and a number of chunks, where each chunk consists of 4 bytes to tell you its length, 4 bytes of its name, some data, and 4 bytes of cyclic redundancy check. In this case, what I call a ‘start’ of a PNG is the 8 byte signature, the 25 byte of the IHDR chunk, and the PLTE (palette) and tRNS (transparency) chunks. The PLTE chunk has 12 bytes of overhead and 3 bytes per colour, and the tRNS chunk has 12 bytes of overhead and 1 byte per colour.

Base64 encoding is a way of representing binary data in text so that it can be used in places where you would normally expect text – like URIs. Without going into too much detail, it turns groups of 3 bytes of binary gumpf into 4 bytes of normal ASCII text without control characters in it, which can then be put into a URI.

Why do we have 255 colours, rather than the maximum 256 which are available in a palette? Because we need the break between the end of the tRNS chunk and the start of the IDAT chunk in the PNG file to align with a break between groups of three bytes in the Base64 encoded image. We need the length of these starts to be a multiple of 3 bytes in the original PNG format, which translates into a multiple of 4 bytes in the Base64 encoded version, so we can cut and shut the images without corruption.

Which just goes to show that even though web GIS technologies may feel like they are approaching a zenith of high level abstraction, there’s still some really gnarly work to be done to get the best out of current browsers.