OpenStreetMap Forum

The Free Wiki World Map

You are not logged in.

Announcement

A fix has been applied to the login system for the forums - if you have trouble logging in please contact support@openstreetmap.org with both your forum username and your OpenStreetMap username so we can make sure your accounts are properly linked.

#1 2008-05-28 15:53:46

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

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.

Last edited by Lambertus (2008-09-06 14:06:22)


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#2 2008-05-28 16:07:53

emj
Member
From: .se (59.3N17.99E) 0735969076
Registered: 2006-06-18
Posts: 949

Re: Routing website using Gosmore routing engine

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.

Last edited by emj (2008-09-22 19:18:51)

Offline

#3 2008-05-28 16:13:35

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

emj wrote:

Cool, but sad that all these cool features are only done for the area where the implementor lives. Or just for England/London. :-)

I wonder what it would take to make them bigger.

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 smile


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#4 2008-06-02 13:24:57

OliverLondon
Member
Registered: 2008-04-04
Posts: 43

Re: Routing website using Gosmore routing engine

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

Offline

#5 2008-06-02 15:22:20

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

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 smile


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#6 2008-06-02 16:17:05

OliverLondon
Member
Registered: 2008-04-04
Posts: 43

Re: Routing website using Gosmore routing engine

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

Offline

#7 2008-06-02 21:31:03

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

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.


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#8 2008-06-03 12:42:09

OliverLondon
Member
Registered: 2008-04-04
Posts: 43

Re: Routing website using Gosmore routing engine

Lambertus wrote:

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).

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

Offline

#9 2008-06-03 13:02:31

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

OliverLondon wrote:

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?

Exactly.

I would have thought with routing, where there will be so many segments, a first-order / straight line approximation would do.

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.


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#10 2008-06-04 17:23:35

emj
Member
From: .se (59.3N17.99E) 0735969076
Registered: 2006-06-18
Posts: 949

Re: Routing website using Gosmore routing engine

And we don't have good elevation maps so it's even harder... :-(

Offline

#11 2008-06-04 17:32:37

emj
Member
From: .se (59.3N17.99E) 0735969076
Registered: 2006-06-18
Posts: 949

Re: Routing website using Gosmore routing engine

Lambertus wrote:
OliverLondon wrote:

Is this something complicated to do with projections and distances between two GPS coordinates?

Exactly.

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;
}

Last edited by emj (2008-06-04 17:50:12)

Offline

#12 2008-06-05 00:39:05

Nic Roets
Member
Registered: 2007-11-12
Posts: 3

Re: Routing website using Gosmore routing engine

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.

Offline

#13 2008-06-05 08:37:18

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

Nic Roets wrote:

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.

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'?

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...

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.

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.

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


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#14 2008-06-05 13:08:48

emj
Member
From: .se (59.3N17.99E) 0735969076
Registered: 2006-06-18
Posts: 949

Re: Routing website using Gosmore routing engine

Nic Roets wrote:

I would be disappointed if we implement Netherlands-specific code.

people want travel time...

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



Nic Roets wrote:

travel distance with OSM will always be inaccurate, because:

* Because we don't have height data (as mentioned)
* OSM is out of date and the users don't always connect the ways.

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



Nic Roets wrote:

people want travel time...

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?

Offline

#15 2008-06-05 14:47:28

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

emj, perhaps it's nice to know that our server is currently crunching away on the planet file to allow worldwide routing 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 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 smile


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#16 2008-06-06 13:54:56

emj
Member
From: .se (59.3N17.99E) 0735969076
Registered: 2006-06-18
Posts: 949

Re: Routing website using Gosmore routing engine

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

Offline

#17 2008-06-06 15:27:04

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

emj wrote:

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

Hey don't bite the hand that feeds you!


tongue


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#18 2008-06-06 15:45:56

Hobby Navigator
Member
From: Aßlar, Germany
Registered: 2007-11-11
Posts: 1,616

Re: Routing website using Gosmore routing engine

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


"Ich denke, dass es einen Weltmarkt für vielleicht fünf Computer gibt."
Thomas Watson, Vorsitzender von IBM, 1943

Offline

#19 2008-06-06 17:26:52

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

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?


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#20 2008-06-06 18:23:51

Hobby Navigator
Member
From: Aßlar, Germany
Registered: 2007-11-11
Posts: 1,616

Re: Routing website using Gosmore routing engine

The namefinder service works with "ß" no Problem 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.:)

Georg


"Ich denke, dass es einen Weltmarkt für vielleicht fünf Computer gibt."
Thomas Watson, Vorsitzender von IBM, 1943

Offline

#21 2008-06-06 20:37:25

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

The routing site uses the namefinder service lookups to translate street/city names to coordinates through a proxy. This is what namefinder responds:

<searchresults 
  find='Friedenstra�e, A�lar' 
  sourcedate='2008-06-06' 
  date='2008-06-06 20:28:13' 
  distancesearch='no' 
  findname='Friedenstra�e' 
  findplace='A�lar' 
  error='place not found'
>

Probably has something to do with URL encoding. It's on the todo list now.


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#22 2008-08-11 14:33:37

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

Lambertus wrote:

The routing site uses the namefinder service lookups to translate street/city names to coordinates through a proxy. This is what namefinder responds:

<searchresults 
  find='Friedenstra�e, A�lar' 
  sourcedate='2008-06-06' 
  date='2008-06-06 20:28:13' 
  distancesearch='no' 
  findname='Friedenstra�e' 
  findplace='A�lar' 
  error='place not found'
>

Probably has something to do with URL encoding. It's on the todo list now.

Late update: this has been fixed a long time ago.

I added route altitude profile image feature for routes less then 400 nodes. The image is generated using Sjors Provoost' GSOC code/service.

Still looking for a way to be able to add support for North and South America...


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#23 2008-08-12 14:36:14

florianheer
Member
From: Bonn
Registered: 2008-07-28
Posts: 15
Website

Re: Routing website using Gosmore routing engine

Thanks a lot for this service, tested one route on foot and immediately found an error in the data :-)

Regards, Florian.

Offline

#24 2008-08-12 16:03:21

Lambertus
Administrator
From: Apeldoorn (NL)
Registered: 2007-03-17
Posts: 3,269
Website

Re: Routing website using Gosmore routing engine

florianheer wrote:

Thanks a lot for this service, tested one route on foot and immediately found an error in the data :-)

That's great smile


Mapping tools: Garmin GPSmap 60CSx, Giant Terrago 2002

Offline

#25 2008-08-12 17:47:02

OliverLondon
Member
Registered: 2008-04-04
Posts: 43

Re: Routing website using Gosmore routing engine

The routing works well but I find that when I try to zoom in on part of the route, the blue line showing the route disappears.  Maybe this is another IE bug? 

Oliver

Offline

Board footer

Powered by FluxBB