Routing Sans Frontières

I noticed a question on StackOverflow recently, concerning the ability of various web-mapping services (Google Maps, Bing Map et al.) to plan routes across national borders. I have to say that it’s a question I’ve never really considered before – all the trans-national routes I’ve ever tried to calculate have worked as expected, just the same as those contained within a single country. However, having given it some thought, it certainly is an interesting issue.

Even across contiguous land masses such as mainland Europe, most mapping services manage their datasets on a country-by-country basis. This makes sense, because the providers of that data are often governments or other national agencies, and the quality, completeness, and timeliness of data available will therefore vary between countries.

Bing and Google both offer similar country coverage for their mapping services:

• Google publishes this spreadsheet detailing the features it offers in different countries.
• Microsoft does the same for Bing Maps, on this MSDN page.

So far, so good, but what about situations where you plan a route that passes through more than one country? Even though the dataset may internally be partitioned into separate countries, you’d still expect those national datasets to be “connected” where appropriate, at the points where a road crosses the boundary between two countries. However, it seems that, as a by-product of managing datasets at a national level, some mapping providers don’t consider certain routes to be valid because they don’t regard roads as contiguous when they cross a national boundary.

For example, Google will plot a route between Ipiales and Pasto, in Colombia, or between Tulcan and Quito, in Ecuador, say, but it cannot calculate a route between Tulcan, Ecuador and Ipiales, Colombia… despite the fact that they lie only a few miles from each other, connected by the Pan-American Highway:

Bing Maps, however, does calculate this route:

There are other examples; Google Maps, for example, doesn’t appear to calculate any route that crosses into or out of China:

Which, again, Bing Maps does without complaint via the international border crossing between Zamyn-Üüd and Erenhot:

Of course, there are some other routes where it perhaps makes sense to be slightly cautious of crossing national borders. Bing Maps suggests that travelling from Cairo to Damascus is a “simple” 10 hour drive into Israel, Jordan, and then into Syria…:

Whether it makes sense to even attempt to complete this journey, Google Maps opts to send you the long way round via the Turkey/Syria border instead:

In practice, I’m certain I probably wouldn’t attempt to drive either of these routes…

Automatic Road Detection using Bing Maps Imagery

Microsoft are often accused of imitating rather than innovating. For example, claims have surfaced this week that Bing copies Google’s search results. And, in the world of mapping, Bing Map’s “Streetside” looks, and sounds,  really quite a lot like Google Maps’ “Streetview”, doesn’t it?

Google StreetSide?

Microsoft Streetview?

While, in some areas, Microsoft appears to be playing catch-up, I was interested to see an announcement earlier today publicising Microsoft’s Road Detect Web Site at http://magicshop.cloudapp.net/. This really does seem to be an example of Microsoft trying an innovative application of technology and, while the image pattern recognition algorithms behind this service are certainly not new, I’m not aware of anyone else who has used them for this purpose before (there are examples of raster to vector conversion of existing maps, but not any I could find direct from aerial imagery). And what an interesting purpose it is…

Essentially, given the latitude and longitude coordinates of a bounding box, and two points that lie somewhere on a road in that area, the service attempts to use Bing Maps’ aerial imagery dataset to automatically identify the set of points following the route of that road (and, optionally, other roads that connect to it). This service is an interesting complement to the recent decision to license Bing Maps imagery for use in Open Street Maps – allowing OSM users to manually trace the location of features on aerial tiles into the OSM database. With a combination of automatic, approximate feature identification, and manual correction and correlation against Bing Maps aerial imagery, we could very quickly see a large amount of routing data being made available in countries that at the moment have no road network information.

I had a quick test of the service, based on features in the following tile (quadkey 1202002233123001):

Aerial View

Road View

Note that the bounding box you supply to the service doesn’t have to line up with a particular Bing Maps quadkey – I just decided to do this as it would be easy to calculate the bounding box coordinates and check the results.

The coordinates of the bounding box of this tile are as follows:

North: 52.6163902330454
West: 1.2799072265625
South: 52.6130549393468
East: 1.285400390625

And the points I chose to mark out my road were placed at either end of Ipswich Road, which is the main road running SW – NE across the centre of the map.

Point 1: 52.61315265664219,  1.2821844220161344
Point 2: 52.61620621223255, 1.2840968370437653

Detect Service

To start with, I decided to test the basic Detect Service, called as follows:

http://magicshop.cloudapp.net/DetectRoad.svc/detect/?pt1=52.61315265664219,1.2821844220161344&pt2=52.61620621223255,1.2840968370437653&bbox=52.6163902330454,1.2799072265625,52.6130549393468,1.285400390625

Which returns the following result:

<osm version="0.6" generator="CGImap 0.0.2">
 <bounds minlat="52.613152" minlon="1.282187" maxlat="52.616207" maxlon="1.284097"/>
 <node id="-230" lat="52.6162071" lon="1.2840968" visible="true"/>
 <node id="-231" lat="52.6156883" lon="1.2837696" visible="true"/>
 <node id="-232" lat="52.6154289" lon="1.2836355" visible="true"/>
 <node id="-233" lat="52.6151848" lon="1.2834316" visible="true"/>
 <node id="-234" lat="52.6140175" lon="1.2827128" visible="true"/>
 <node id="-235" lat="52.6136475" lon="1.2824017" visible="true"/>
 <node id="-236" lat="52.6133995" lon="1.2823212" visible="true"/>
 <node id="-237" lat="52.6131516" lon="1.2821871" visible="true"/>
 <way id="-24" user="" uid="1946651915" visible="flase" version="5">
 <nd ref="-230"/>
 <nd ref="-231"/>
 <nd ref="-232"/>
 <nd ref="-233"/>
 <nd ref="-234"/>
 <nd ref="-235"/>
 <nd ref="-236"/>
 <nd ref="-237"/>
 <tag k="highway" v=""/>
 </way>
</osm>

(Notice how the schema of the returned xml follows the OSM schema?)

The next step was to shred this xml data into a SQL Server table, where each node was represented by a geography point:

DECLARE @x xml;

SET @x = '<osm version="0.6" generator="CGImap 0.0.2">
 <bounds minlat="52.613152" minlon="1.282187" maxlat="52.616207" maxlon="1.284097"/>
 <node id="-230" lat="52.6162071" lon="1.2840968" visible="true"/>
 <node id="-231" lat="52.6156883" lon="1.2837696" visible="true"/>
 <node id="-232" lat="52.6154289" lon="1.2836355" visible="true"/>
 <node id="-233" lat="52.6151848" lon="1.2834316" visible="true"/>
 <node id="-234" lat="52.6140175" lon="1.2827128" visible="true"/>
 <node id="-235" lat="52.6136475" lon="1.2824017" visible="true"/>
 <node id="-236" lat="52.6133995" lon="1.2823212" visible="true"/>
 <node id="-237" lat="52.6131516" lon="1.2821871" visible="true"/>
 <way id="-24" user="" uid="1946651915" visible="flase" version="5">
 <nd ref="-230"/>
 <nd ref="-231"/>
 <nd ref="-232"/>
 <nd ref="-233"/>
 <nd ref="-234"/>
 <nd ref="-235"/>
 <nd ref="-236"/>
 <nd ref="-237"/>
 <tag k="highway" v=""/>
 </way>
</osm>';

SELECT
 OSMnode.value('@id', 'int') AS nodeid,
 geography::Point(OSMnode.value('@lat', 'float'), OSMnode.value('@lon', 'float'), 4326) AS geog4326,
FROM
 @x.nodes('/osm/node') AS OSM(OSMnode)
END
GO

This gave me a table of results as follows:

nodeid    geog4326
-230    POINT (1.2840968 52.6162071)
-231    POINT (1.2837696 52.6156883)
-232    POINT (1.2836355 52.6154289)
-233    POINT (1.2834316 52.6151848)
-234    POINT (1.2827128 52.6140175)
-235    POINT (1.2824017 52.6136475)
-236    POINT (1.2823212 52.6133995)
-237    POINT (1.2821871 52.6131516)

Which, when plotted back on my original Bing Maps tile, gives the following:

Not a bad correlation for a first attempt…

Explore Service

The explore service basically works in exactly the same way as the detect service, except that instead of returning only nodes that lie along the selected way, it also returns nodes that lie on any intersecting ways within the bounding box. I called it with the same set of parameters as used previously for the Detect service:

http://magicshop.cloudapp.net/DetectRoad.svc/explore/?pt1=52.61315265664219,1.2821844220161344&pt2=52.61620621223255,1.2840968370437653&bbox=52.6163902330454,1.2799072265625,52.6130549393468,1.285400390625

This time, the results do not contain a single set of nodes, but rather a set of ways and nodes, with each way containing a set of <nd> elements linking it back to the nodes contained in that way. Plotting all the nodes gives the following results:

The data obviously needs a bit of cleaning up – it’s failed to detect certain roads, and also seems to have produced false positives where no roads exist, but it’s not a bad start. As it happens, my example here was rather trivial because Bing’s road network in Norwich is already pretty good An interesting follow-up experiment, and one that has more practical application, would be to see how the results differ if used on a remote area rather than built-up urban environment, where roads and other features are much more sparsely distributed, and the image recognition algorithm may work more effectively.

Drivetime Polygons with MapPoint and Bing Maps

There was a time, a few years ago, when the MapPoint CD could regularly be found in my computer’s CD drive… back then, it was the best tool for examining maps, plotting routes, and creating your own sets of pushpin data.

Nowadays, Bing maps, Google maps, and other online web-mapping providers provide much of the functionality that could previously only be found in desktop applications such as MapPoint, for free, with continuously updated road and aerial imagery data. The terabytes of global data that sit behind web applications such as Bing Maps could never easily be packaged up and distributed in a desktop application any more. And since these webservices are readily available from any web browser, (including almost all new mobile phones), there are less obvious reasons why you’d still want to use the MapPoint desktop application on your computer.

However, there are still some functions that MapPoint provides that are not easily available in Bing Maps or Google Maps (or, as far as I’m aware, any other web-mapping providers). One of these features is the ability to plot drivetime polygons – the area containing all those places that can be reached by road within a certain amount of time starting from a particular location.

Fortunately, MapPoint can be accessed through a COM interface, which means that we can create a drivetime polygon programmatically through code, and then export it as a SQL Server geography polygon or Bing Maps polygon to display using the Bing Maps control.

To do so, you first need to import a reference to the MapPoint Object Library into your application. Create a new Visual Studio project, select Add Reference from the Project menu, select the COM tab, and scroll down to select the Microsoft MapPoint Object Library.

Note that I’m using Microsoft MapPoint Europe 2010, so my library is version 17.0 – if you have a different version installed on your computer then the name of the library will differ accordingly, but you should still be able to use the same code.

Once you’ve imported the COM assembly, you can access the MapPoint map functions via the ApplicationClass of the MapPoint namespace. The following code demonstrates a simple C# console application that initialises the MapPoint application, creates a drivetime polygon that determines all locations that can be reached within 60 minutes drive from “10 Downing Street, London”, and then retrieves the points in those shapes and converts them to Well-Known Text:

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            MapPoint.ApplicationClass app = new MapPoint.ApplicationClass();
            MapPoint.Map map = app.ActiveMap;

            object index = 1;
            MapPoint.Location location =
       (MapPoint.Location)map.FindResults("10 Downing Street, London, England").get_Item(ref index);

            //Add a 60 minute drivetime zone around a location
            MapPoint.Shape shape =
               map.Shapes.AddDrivetimeZone(location,
                          60 * MapPoint.GeoTimeConstants.geoOneMinute);

            string WKT = "POLYGON((";

            //Now get the vertices for this polygon
            object[] vertices = shape.Vertices as object[];
            foreach (object vertex in vertices)
            {
                MapPoint.Location loc = vertex as MapPoint.Location;
                WKT = WKT + loc.Longitude.ToString() + " " + loc.Latitude.ToString() + ", ";
            }
            WKT = WKT.Substring(0, WKT.Length - 2);
            WKT = WKT + "))";
            Console.Write(WKT);
        }
    }
}

Drivetime polygons created using this method can be stored in SQL Server 2008’s geography datatype, and then retrieved and plotted on Bing Maps.

Here’s some drivetime polygons generated using the method described above illustrating those areas reachable within  20 minutes, 40 minutes, and 60 minutes drive starting from my house in Norwich, displayed on Bing Maps v7:

using System;

using System.Collections.Generic;

using System.Text;

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            MapPoint.ApplicationClass app = new MapPoint.ApplicationClass();

            MapPoint.Map map = app.ActiveMap;

            object index = 1;

            MapPoint.Location location =

       (MapPoint.Location)map.FindResults("10 Downing Street, London, England").get_Item(ref index);

            //Add a 60 minute drivetime zone around a location

            MapPoint.Shape shape =

               map.Shapes.AddDrivetimeZone(location,

                          60 * MapPoint.GeoTimeConstants.geoOneMinute);

            string WKT = "POLYGON((";

            //Now get the vertices for this polygon

            object[] vertices = shape.Vertices as object[];

            foreach (object vertex in vertices)

            {

                MapPoint.Location loc = vertex as MapPoint.Location;

                WKT = WKT + loc.Longitude.ToString() + " " + loc.Latitude.ToString() + ", ";

            }

            WKT = WKT.Substring(0, WKT.Length - 2);

            WKT = WKT + "))";

            Console.Write(WKT);

        }

    }

}

Who needs Google Maps? Build your own Mapping, Geocoding, and Routing service with SQL Server

Back in November 2009, I was lucky enough to present a session at the SQLBits V conference, on “Creating High Performance Spatial Databases“. I say “lucky” not because I enjoy presenting at conferences (because I don’t particularly), but because SQL Bits is a fantastic conference, organised by a highly-dedicated, bloody-hardworking, talented, and generally nice bunch of people, and it was an honour to be associated with them and to learn from them.

The next SQL Bits conference, SQL Bits 8, is happening in Brighton between 7th – 9th April 2011, and I’ve just submitted a new session for it, titled (as is this post) “Who needs Google Maps? Build your own Mapping, Geocoding, and Routing service”. If my session gets accepted, I’m planning demonstrating practical uses of the spatial datatypes in SQL Server to perform, well, mapping, geocoding, and routing.

Following feedback from Simon Sabin (a SQL Server MVP with much more presenting experience than me) I got after my last presentation , I’m going to be ditching the Powerpoint slides and the theory and, if my session is selected, I’ll be presenting a lot more eye-candy like this instead:

Routefinding

Mapping Features