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:

  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:


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:


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:


The Value of Spatial Data Services (SDS)

The end of life for MapPoint Web Service and Multimap is quickly approaching (November 18, to be exact), so it’s a good time to start considering migrating to Bing Maps. This blog focuses on why the use of the Bing Maps Spatial Data Services (SDS) should be considered as your migration solution.

With MapPoint Web Service there are customer data sources and FindNearby queries. You may have considered spatial features found in SQL Server (or SQL Azure). SQL Spatial provides a robust spatial database and is a great solution for complex queries, like find near a route, find in a polygon, etc. If you are using MapPoint Web Service polygon features, SQL Spatial is a good way to go. For those of you with simple queries, SQL Spatial can certainly be used, but it comes at an additional cost and solution complexity (for example, you need to create an API to query data).

The Bing Maps SDS APIs provide the ability to upload and query your point data, like buildings or stores. Here are some significant reasons to migrate from MapPoint Web Service to Bing Maps SDS.

1)    SDS is a RESTful API. It’s easy to understand and use without WSDLs and SOAP parsing. Like other Bing Maps APIs, the REST APIs support JSONP, thus they can easily be used client side without cross-domain issues.

2)    SDS runs on the Bing Maps Content Delivery Network (CDN) (see figure 1.) When you upload your data using the Data Source Management APIs your data gets automatically replicated to the 19 CDN nodes. When using a client-side query, the request gets routed to the nearest CDN node, which reduces latency and significantly increases performance while adding the reliability that comes with such massive data replication.

Figure 1 – Bing Maps Content Delivery Network nodes

3)    SDS Supports Bounding Boxes. In many applications (store locators, for instance), organizations will often use a FindNearby query (“Give me all the locations within a certain radius”). This is fine for initial queries, but what if the user wants to pan around? FindNearby queries typically don’t work well. Does the user really care about what was nearby their initial query? And does the user really care about all the locations within 20 miles if they have zoomed in to a very specific area? In addition to a FindNearby query, the SDS Query API also supports bounding box queries. This means that as the user pans/zooms the map, you can query based on the user’s new view and load data for the precise area they want to see.

Parsing Free-Text Addresses and a UK Postcode Regular Expression Pattern

We’ll be attempting to replicate the functionality of Google Maps using nothing but freely-available tools and data – SQL Server Express, OS Open Data, and a dash of Silverlight.

One of the features I’ll be demonstrating is a basic geocoding function – i.e. given an address, placename, or landmark, how do you look up and return the coordinates representing the location so that the map can centre on that place? This is not really a spatial question at all – it’s a question of parsing a free-text user input and using that as the basis of a text search of the database.

The simplest way of doing this is to force your users to enter Street Number, Street Name, Town, and Postcode in separate input elements (and these match the fields in your database). In this case, your query becomes straightforward:

SELECT X, Y FROM AddressDatabase WHERE StreetNumber = ‘10’ AND StreetName = ‘Downing Street’ AND Town=’London’

Most databases don’t contain the location of every individual address. If there is no exact matching StreetNumber record, then you typically find the closest matching properties on the same road and interpolate between them (it seems reasonable to assume that Number 10 Downing Street will be somewhere between Number 9 and Number 11).

Forcing users to enter each element of the address separately doesn’t necessarily create the most attractive UI, however. What’s more common is to use a single free-text search box into which users can type whatever they’re searching for – a placename, address, landmark, postcode etc. Nice UI, but horrible to make sense of the input. In these cases, the user might supply:

“10 Downing Street, London”

“Downing Street, St James’, LONDON”

“10, Downing St. SW1A 2AA”

…not to mention “10 Downig Street. London”, and any other many of misspellings or alternative formats.

One approach you might want to take in these cases is to use a RegEx pattern matcher to determine if any part of the string supplied is a postcode. The UK postcode format is defined by British Standard BS7666, and can be described using the following regular expression pattern:

(GIR 0AA|[A-PR-UWYZ]([0-9][0-9A-HJKPS-UW]?|[A-HK-Y][0-9][0-9ABEHMNPRV-Y]?) [0-9][ABD-HJLNP-UW-Z]{2})

Matching the supplied address string against this RegEx doesn’t prove that a valid postcode was supplied, but just that some part of the user input matched the format for a postcode. The matching substring can then be looked up (say, against the CodePoint Open dataset) to confirm that it is real.

Once you’ve identified the postcode, you can then run a query to retrieve a list of roadnames that lie in that postcode, from something like the OSLocator dataset, and scan the remainder of the input to see if it contains any of those names. You can also scan for any numeric characters in the first part of the text input, which might represent a house number. If you find a matching property, with the same road name and valid postcode, you can be pretty sure you’ve found a match.

If you find more than valid match, or possibly several partial matches only, then you can of course present a disambiguation dialogue box – “Is this the 10 Downing Street you meant?”. For example, there are many “10 Downing Street”s in the UK – from Liverpool to Llanelli and Farnham to Fishwick…. without knowing either the town or the postcode, it could have referred to any of the following: