Routing website using Gosmore routing engine

I’ve put together a website showing off the combined routing capabilities of Gosmore, the Namefinder indexer, the Route altitude profiles generator and OpenLayers slippy map framework. It’s purpose is the combine the current off-the-shelf 3rd party software that is developed for OpenStreetMap into a usable route planning website.

This project so far has proven itself as an efficient OpenStreetMap data validator and a booster in routing software development.

More info is on the project page. Please add comments, feature requests and questions to this forum topic.

The routeplanner works worldwide, since the summer 2008.

But it’s sad that all these cool features are usually just done for the area where the implementor lives in the beginning, and then later on expanded to the world. You can never try out new features on your own data.

Yes, I know what you mean.

But first please note it is only a demo. Once it has grown-up features works well it could be published in the OSM SVN code repository so anyone could deploy a service.
Second, the application runs on a sponsored server for the Netherlands. Special arrangements with the sponsor should be made before it could cover the world (processor usage, SAN disk space, etc.).

We’ll get there in the near future, even to Sweden :slight_smile:

It’s not working for me at work (IE6). I just get a blank box where the map should be and “errors on page” in the status bar. OSM itself normally works. Is this a known issue with OpenLayers / javascript / something else?

Oliver

No, it’s just that I don’t test much using IE because it’s much more difficult to debug using IE (FF has firebug). Also IE complains about code that works fine with FF. Anyway, I think I fixed the bugs so it should now work for you :slight_smile:

Great - it works now. The user interface acts strangely sometimes, but I managed to plot a couple of routes. The clear button doesn’t always work.

A couple of suggestions to add to your todo list: 1. could the map zoom out to show the whole route, once it’s calculated? 2. could you provide some textual info about the route (length of route or even driving directions)?

To me this should form part of the main openstreetmap website, when it’s sufficiently developed, because wider use of routing tools will help find bugs in the main database.

Regards

Oliver

Thanks for your feedback, I will take this into account in next releases. Please let me explain though, this is the result of about a week long work during the evenings: about 24 hours. It is not even close to become a serious production system showing off all of OSM’s capabilities, but it would be great to have a routing application on the main website (be it mine or someone else’).

Edit: An approximate length is already calculated, but unfortunately very inaccurate. Accurately calculating a route distance is very complicated (I’m talking about multiple pages with formulas here). It is on my todo list but does not have very high priority.

Driving directions is very cool, but I don’t have easy access to the required data (gosmore does not return it atm). If I (or someone) can come up with a method of getting the driving directions then I certainly will implement it.

I’m confused about this. To plot the route on the map, you must have a series of segments. Can’t you just add the length of every segment to give a total route length? Is this something complicated to do with projections and distances between two GPS coordinates? I would have thought with routing, where there will be so many segments, a first-order / straight line approximation would do.

Oliver

Exactly.

There are sometimes a lot of segments (I’ve seen routes so far that have more then 500 segments) and although the error might be small on each segment, adding those small errors for each segment still results in a large error.

Have a look at this document if you have the time for it. It describes the theory pretty well and shows that calculating distances isn’t easy.

And we don’t have good elevation maps so it’s even harder… :frowning:

Since you are only in Netherlands you should be able to convert your OSM nodes to your local orto-grid and just use simple geometry…

Found this to calculate distances in PHP If you want to copy and paste. I haven’t tested this, and there are notes saying that the original algorithm didn’t converge for all cases, and the PDF you linked seems to be the original 1975 paper.

So again untested code:

function distInvVincenty($lat1, $lon1, $lat2, $lon2) {
/* WGS84 stuff */
$a = 6378137;
$b = 6356752.3142;
$f = 1/298.257223563;
/* end of WGS84 stuff */
$L = deg2rad($lon2-$lon1);
$U1 = atan((1-$f) * tan(deg2rad($lat1)));
$U2 = atan((1-$f) * tan(deg2rad($lat2)));
$sinU1 = sin($U1);
$cosU1 = cos($U1);
$sinU2 = sin($U2);
$cosU2 = cos($U2);

$lambda = $L;
$lambdaP = 2*pi();
$iterLimit = 20;
while ((abs($lambda-$lambdaP) > pow(10, -12)) && ($iterLimit-- > 0)) {
$sinLambda = sin($lambda);
$cosLambda = cos($lambda);
$sinSigma = sqrt(($cosU2*$sinLambda) * ($cosU2*$sinLambda) + ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda) * ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda));
if ($sinSigma==0) {return 0;}
$cosSigma = $sinU1*$sinU2 + $cosU1*$cosU2*$cosLambda;
$sigma = atan2($sinSigma, $cosSigma);
$sinAlpha = $cosU1 * $cosU2 * $sinLambda / $sinSigma;
$cosSqAlpha = 1 - $sinAlpha*$sinAlpha;
$cos2SigmaM = $cosSigma - 2*$sinU1*$sinU2/$cosSqAlpha;
if (is_nan($cos2SigmaM)) {$cos2SigmaM = 0;}
$C = $f/16*$cosSqAlpha*(4+$f*(4-3*$cosSqAlpha));
$lambdaP = $lambda;
$lambda = $L + (1-$C) * $f * $sinAlpha *($sigma + $C*$sinSigma*($cos2SigmaM+$C*$cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)));
}
if ($iterLimit==0) {return NaN;} // formula failed to converge

$uSq = $cosSqAlpha * ($a*$a - $b*$b) / ($b*$b);
$A = 1 + $uSq/16384*(4096+$uSq*(-768+$uSq*(320-175*$uSq)));
$B = $uSq/1024 * (256+$uSq*(-128+$uSq*(74-47*$uSq)));
$deltaSigma = $B*$sinSigma*($cos2SigmaM+$B/4*($cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)- $B/6*$cos2SigmaM*(-3+4*$sinSigma*$sinSigma)*(-3+4*$cos2SigmaM*$cos2SigmaM)));

$s = $b*$A*($sigma-$deltaSigma);
return "Distance: ".$s;
}

I would be disappointed if we implement Netherlands-specific code. gosmore is ready to be used on the whole planet file : It takes 3 hours to import it on a dual core 64 bit machine with 2 GB RAM and generates a 6.5 GB file.

Predicting the travel distance with OSM will always be inaccurate, because we don’t have height data (as mentioned), DGPS wasn’t used, people don’t drive, cycle or walk down the middle of the road, OSM is out of date and the users don’t always connect the ways. And people want travel time…

I can make gosmore output the names of the ways (1 per segment). So then it will be helpful if we know weather each turn is left or right (e.g. by calculating bearing), because then we can generate simple driving instructions.

I tried that yesterday but Gosmore choked on our sponsored 32 bit machine while processing a planet file from April 16th. The person that maintains the system claims that 32 bit in theory doesn’t mean that it won’t be able to process the planet. I assume Gosmore uses architecture specific variable types like ‘int’?

Yeah ppl always want more but, before we venture into the advanced routing areas, I want to get basic routing functional and available. Let’s worry about exact traveltimes determined by combining the measured speeds of mobile phones, wifi networks and historic gpx logs later.

That would be my next request for Gosmore. It would be great if you could implement that :slight_smile: I promise to put it to good use on the website :smiley:

If you convert to your local NL grid, or .se grid, or like OS grid in uk, the code will still be the same for all countries. Since one unit equals one meter. This has several benefits, but is most probably too hard to do since there are too little information on how you use these grids. And there is no server available that can use multiple grids

Yes incomplete data in OSM is a problem, but if you can you should try to find these inconsistencies. This is something that should be easier todo when we can see what happens with routes, this would make it easier to fix topology.

Are you sure these will add much to the time?

  • DGPS wasn’t used
  • People don’t drive, cycle or walk down the middle of the road

Then how do we add it? I’m guessing you can’t do that with current OSM data. At least it must be very hard to do for cars.

We need:

  • crossing=lights/uncontrolled
  • speed
  • traffic_jammy

Anything else?

emj, perhaps it’s nice to know that our server is currently crunching away on the planet file to allow worldwide routing :slight_smile:

I’ve tried to accomplish that using a single Gosmore .pak file for the whole world, but that won’t work since our server is 32bit currently. So instead I’ve split the routing backend into two (America and Eurasia) in an attempt to limit the .pak file size.

The only backside of this approach is that you won’t be able to get the routing engine to produce a route that would require you to swim from Boston to London across the Atlantic ocean :stuck_out_tongue:

This worldwide service will be available as long as our sponsor allows us to and as long as it doesn’t interfere with it’s main function: serve slippy maps for the Netherlands. I think it will be able to process about 10-20 route requests per second (about 0.03 seconds per request) under optimal circumstances (estimate, the service isn’t up and running yet). Under worst conditions it will be able to only produce about 8 requests per minute as Gosmore sometimes seems to choke on the data causing it tor run for minutes on end, but limited with ulimit).

Update: Gosmore choked on the Tiger data in North America, so routing only works for Europe, Asia, Africa and Polynesia: http://tile.openstreetmap.nl/~lambertus/routing-world.

Nic Roets, you might find it interesting that a first attempt to route from Camps Bay Cape Town to Graaff Reinet (which I drove once) was calculated in about 41 seconds and returned almost 2000 nodes :slight_smile:

Works nicely, as you say a little on the slow side.

Hey don’t bite the hand that feeds you!

:stuck_out_tongue:

Hi Lambertus, it works nice. In Germany too!
Ok, i know the German Language is a little specialy…
The routing works not with the Caracter like “ß” it meens “ss” but in many Street Names there is a “ß”.
Georg

I think looking up a street, city combination for the ‘to’ and ‘from’ coordinates doesn’t work? If so, can you tell me if the namefinder service works properly with “ß” characters?

The namefinder service works with “ß” no Problem :slight_smile:
But the Routing Demo dosen’t. Test this please “from: Friedenstraße, Aßlar” “to: Bergstraße, Wetzlar”…

It’s not a big Problem, it’s a great work from you! And when the Software will finished it will work very well, i think.:slight_smile:

Georg