Bing Maps Geodesics

This month’s MSDN magazine has an article describing how to create curved lines on the Bing Maps AJAX control. While I don’t want to criticise the author at all, there are two comments I would make on the article:

  • Firstly, it’s written using v6.3 of the AJAX control – v7.0 has been available for well over 6 months now and (despite some teething problems) this latest version is recommended for all new development.
  • Secondly, the article describes how to draw arbitrary Bezier curves on the projected plane of the map. Whilst this is an interesting exercise (and the author goes on to describe important concepts such as how to test the routine), it’s not actually that useful. More often, when we see curved lines on a map, we expect them to represent geodesics – the shortest path between two points on the surface of the earth. Although this was never the intention of the article, Bing Maps evangelist Chris Pendleton mistakenly drew this conclusion and tweeted a link to the article stating that it demonstrated geodesics, when in fact it does not.

Therefore, I thought that responding to this article would provide a good prompt for me to dust off and update my own v6.x geodesic curve script from several years ago (originally published here).

What’s a Geodesic, anyway?

A geodesic is a “locally-length minimising curve” (Mathworld) – it’s the shortest path between any two points on a given surface. On a flat plane, like a piece of paper, a geodesic is a straight line. On a sphere, a geodesic is a great circle. When dealing with geospatial data, a geodesic is the shortest distance between two points on the surface of the earth.

Generally speaking, Bing Maps has no regard for geodesic shapes relative to the earth’s surface – instead it draws shapes directly onto the projected map image. Drawing a straight line between two points on a map represents the shortest path between those points in the projected plane of the map, but it generally does not represent the shortest path between those same two points on the surface of the earth.

For example, consider a polyline drawn between Munich and Seattle, both of which lie at a latitude of approximately 48 degrees. You can define a polyline connecting these two points as follows:

Microsoft.Maps.Polyline([
  new Microsoft.Maps.Location(48, 11.5),
  new Microsoft.Maps.Location(48, -122)]);

When displayed on the map, this polyline will follow a constant latitude between the two points, like this:image

However, this is certainly not the shortest route between Munich and Seattle. If you are unsure why, consider how this same line would appear when viewed on a 3-dimensional model of the earth. In the screenshot below, the line that follows a constant latitude of 48 degrees, as shown above, is plotted in red, while the geodesic line that represents the true shortest line connecting the destinations is shown in blue:

image

Notice how, rather than being parallel to the equator, the geodesic route goes much further north over the top of the UK, then over Iceland, Greenland, and much of Canada before turning south again into Seattle. You can try this yourself on a globe – the geodesic route is the path that a piece of string follows when held tight between two locations. (For those readers familiar with SQL Server, the red line above is equivalent to a route calculated using the geometry datatype, while the blue line is equivalent to using the geography datatype)

As shown above, the shortest “straight line” route on a map is not the shortest direct path between two points on a globe. Likewise, the shortest geodesic route between two locations on the globe does not generally correspond to a straight line on a map. This is why, when airline companies show maps illustrating the flightpaths to various destinations, the lines appear curved – because they’re representing the geodesic path on the surface of the earth, which, when projected onto a map, will generally not be straight lines:

image

Drawing Geodesic curves in Bing Maps

Geodesics are clearly very useful if you want to visualise the path of shortest distance between two points. So how do you go about drawing geodesic curves in Bing Maps? Well, Bing Maps does not support curved geometries directly, so instead we must approximate the shape of a geodesic curve by creating a polyline containing several small segments. Using a larger number of segments will make the polyline appear more smooth and more closely resemble the shape of the smooth curve, but will also increase its complexity. I find that using 32 segments is more than sufficient accuracy for most maps. We’ll call this value n.

var n = 32;

Then, we need to determine the overall extent of the route, which we’ll call d. The shortest distance between any two points on a sphere is the great circle distance. Assuming that the coordinates of the start and end points are (lat1, lon1) and (lat2, lon2) respectively, measured in Radians, then we can work out the great circle distance between them using the Haversine formula, as follows:

var d = 2 * asin(sqrt(pow((sin((lat1 - lat2) / 2)), 2) + cos(lat1) * cos(lat2) * pow((sin((lon1 - lon2) / 2)), 2)));

We then determine the coordinates of the endpoints of each segment along the geodesic path. If f is a value from 0 to 1, which represents the percentage of the route travelled from the start point (lat1,lon1) to the end point (lat2,lon2), then the latitude and longitude coordinates of the point that lies at f proportion of the route can be calculated as follows:

var A = sin((1 - f) * d) / sin(d);
var B = sin(f * d) / sin(d);

// Calculate 3D Cartesian coordinates of the point
var x = A * cos(lat1) * cos(lon1) + B * cos(lat2) * cos(lon2);
var y = A * cos(lat1) * sin(lon1) + B * cos(lat2) * sin(lon2);
var z = A * sin(lat1) + B * sin(lat2);

// Convert these to latitude/longitude
var lat = atan2(z, sqrt(pow(x, 2) + pow(y, 2)));
var lon = atan2(y, x);

By repeating the above with different values of f, (the number of repetitions set according to the number of segments in the line), we can construct an array of latitude and longitude coordinates at set intervals along the geodesic curve from which a polyline can be constructed.

The following code listing wraps this all together in a reusable function, ToGeodesic, that returns an array of points that approximate the geodesic path between the supplied polyline or polygon locations.

To demonstrate the use of the function, I’ve added two entity collections to the map. The simple layer acts a regular shape layer, containing polylines and polygons displayed in red. Whenever an entity is added to this collection, the entityAdded event handler fires, which converts the added entity into the equivalent geodesic shape and adds it to the geodesicShapeLayer, displayed in blue. By maintaining two layers you can continue to deal with shapes as per normal in the layer collection – the additional points needed to simulate the geodesic display of each shape only get added in the copy of the shape added to the geodesicShapeLayer. You may then, for example, choose not to display the non-geodesic layer and only use it as a method to manage shapes, while the geodesic layer is used to actually display them on the map.

  
  

Here’s the results, showing both the flat (red) and geodesic (blue) layers of a polyline and a polygon:

image

Google Developer Day coming to a city near you in 2011

 

As Vic Gundotra announced previously, Google Developer Day (GDD) will be coming to eight cities in 2011. Please save the date, as we prepare to bring our world tour of GDDs to a city near you.

  • September 16: Sao Paulo, Brazil
  • September 19-20: Buenos Aires, Argentina
  • October 10: Moscow, Russia
  • October 18: Prague, Czech Republic
  • November 1: Tokyo, Japan
  • November 8: Sydney, Australia
  • November 13: Tel-Aviv, Israel
  • November 19: Berlin, Germany

Google Developer Days are a chance to learn about our latest developer products and meet the engineers who work on them. As in years past, we will have an application process when registration opens, so stay tuned, as we will continue to bring you updates.

Dynamic Animated Tile Layers in Bing Maps (AJAX v7) 3

Now that I’ve got a working animated tile class, it’s time to look and see what performance improvements I can make to it. As in my first post in this series, the frames of my animation are going to be built from weather RADAR data collected from the NOAA at regular intervals in time (every 15 minutes), over a 6 hour period. This means that, every time my animation runs through a complete cycle, I will have requested 24 times the number of tiles normally required to construct the background of the map display. The absolute key to making this solution usable was going to be in ensuring those tiles were as small filesize as possible.

Reducing the Bit Depth

My weather data was retrieved and the tile images constructed dynamically using a PHP script. Since I wanted my tiles to retain transparency (so that they could be overlaid on top of other layers), but didn’t want to use GIF format, my only choice was to opt for PNG files which can be created with the PHP imagepng function.

By default, PHP creates true colour (i.e. 32bit) PNG images. However, my NOAA radar imagery was only using a 256 colour palette so, as suggested by a commentator on one of my previous posts (thanks Chris!), I could save some space without affecting image quality by ensuring all my tile images were saved as 8bit PNG rather than 32bit PNG. To compare, here’s the RADAR image for tile quadkey 02311, recorded at 10:15am on 27th May 2011:

02311

32Bit PNG (192kb)

02311

8Bit PNG (9kb)

192kb reduced to 9kb with no change in appearance – that’s a pretty good start!

Compressing the Tiles

My next option was to compress the tiles. The PNG file format uses the Deflate compression algorithm, which has two key features: a.) It’s a lossless algorithm, so (unlike JPG) there is no reduction in image quality in a compressed image file, and b.) it has a static decompression rate. What that means is that, however much you compress a PNG file, it will not take longer to decompress. Unlike some archive formats, there is no trade-off between having a smaller compressed filesize, only for it to take longer to unpack or for it to be lower quality – with PNG, compression is always desirable. You can read a good introductory guide to PNG compression at http://optipng.sourceforge.net/pngtech/optipng.html

There are a number of different PNG compression tools out there. For comparison, I tried both an online service (PunyPNG), and a small downloadable Windows application that provides a front-end for a series of command-line PNG utilities (PNG Monster). Both are free to use, and don’t add any watermarks to your images.

PunyPNG compressed my 8bit PNG, original size 9,212 bytes, down to 7,270 bytes (a 22% reduction). PNG Monster did even better, reducing it to just 5,793 bytes (a 37% reduction).

02311

PunyPNG compressed 8Bit PNG image (8 bytes)

02311

PNG Monster compressed 8Bit PNG image (6 bytes)

What makes PNG Monster even more useful is that you can set it to batch process and compress all the PNG files in a directory, rather than having to upload them one by one to an online webservice. The interface isn’t much to look at (except for the nice icon of the Cookie Monster), but if it gets the job done, who cares?!

I set it to work in a directory that contained 256 tiles representing the tiles for one frame of animation, at zoom levels 5, 6, and 7. This reduced the total size from 1.2Mb down to 566Kb – less than half the original size:

image

The Only Way is… PNG?

(If you’re not au fait with pop singles from the late 1980s, that title was meant to be an homage to Yazz. Oh, never mind…).

I was pretty pleased with the results from PNG monster, but there was just one more option I wanted to explore. My reason for choosing PNG was because it supported transparency, and could therefore be added as a separate tilelayer overlaid on top of other background layers within the AJAX control. For example, you could place the animated weather tilelayers on top of the base aerial imagery tiles, or the road map tiles:

Base map style Transparent PNG Result
+ =
+ =

But what about, rather than creating the RADAR image as a transparent layer, I created an opaque tile that showed the data ready overlaid onto a Bing Maps imagery tile? That way, I could save the tile as a JPG file instead and take advantage of its (potentially) greater compression ratio.

The aerial image tile shown above, http://ecn.t1.tiles.virtualearth.net/tiles/h02311.jpeg?g=685&mkt=en-gb&n=z, is 24,128 bytes. Setting a compression ratio of 65%, I could create a JPG tile of almost exactly the same filesize as the original Bing Maps tile, but incorporated the radar image as well:

While, at first, I thought that embedding the RADAR imagery onto the background tile image might have been a good idea, (and, it would be, if I was only trying to display a single static tile combining weather data and imagery), the end JPG tile ended up being much greater size than my compressed PNG image tiles. In every frame of the animation, I’d be downloading the entire background map image for that tile again, and I’d also lose the flexibility of being to overlay a transparent layer on top of any other layer. Idea aborted – back to PNGs!