[Routing] Bad routing: U turns for highway links?

[Stephen Woodbridge]

Anthony wrote:
> On Wed, Jul 21, 2010 at 1:38 PM, Stephen Woodbridge 
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
> 
>     So what rules are you proposing the router should implement again?
> 
> 
> I'm not proposing anything.  It's not my place to do so.  If I were 
> writing the router, I'd have a checkbox for "avoid U-turns".
>  
> 
>     There is nothing in your above explanation that would lead me to
>     believe that this should be in the router.
> 
> 
> Fine, don't put it in.  I was mainly just explaining why it shouldn't be 
> in the data.

Anthony,

I don't work on this router, but I have worked on quite a few others and 
  for the most part they are all very similar in concept and 
implementations. I also just realized that you and I have a different 
concept for what is the "router" which may ad to the confusion.

I believe when you use the word router you are speaking of the whole 
routing application, IE: user input -> some process -> routing output. 
While I think of it as only one part of the "some process" box. Here is 
a crude box break down of the pieces:

1. preprocess data into graph file
(data) -> [graph builder] -> (graph file)

2. compute a route
(use input) + (graph file) -> [router process] -> (intermediate result)

3. post process route to human readable instructions
(intermediate result) + (data) -> [explicator] -> (driving instruction) 
+ (route path data)

This is what happens in the "routing application".

The graph file is basically a connectivity list with costs to transition 
over edges and turn restriction information. There is no geometry here. 
The only information is A is connected to B and if cost X to get from A 
to B and additional information about restrictions at any given node.

So the internal routing process knows nothing about angles (read on for 
more about angles).

The intermediate results as a list of nodes and edges to get from start 
to end and the cost associated with each edge and/or node.

The explicator process the takes the list of nodes and edges and looks 
these up in the data file to get their names and get the polylines the 
represent the edges in the route. From the polylines it is possible to 
then compute the turn angles the are explicated. What is important to 
note here is that you only have to compute the angles for the say 100 
edges in your results and not the 45 million edges in your graph file.

So when I say the route know nothing about angles, I referring to the 
pieces that is extracting the route from the graph and not the 
explicator both of which are inside you black box called the "router".

I hope this sheds some light on how things work and hopefully will make 
my responses more meaningful.

>     I the data model does not support encoding all these information
>     then that should be fixed.
> 
> 
> What information?  It's a really sharp turn.  That's already encoded in 
> the data.  In fact, Cloudmade's router even *says* "make a sharp left".  
> So the router already knows it's a really sharp turn.
> 
> What more information do you need?
>  
> 
>     Things like turn restrictions should be implemented in the data.
> 
> 
> Agreed.  But there is no turn restriction at 
> http://www.openstreetmap.org/?lat=28.077361&lon=-82.570335&zoom=18&layers=B000FTF 
> <http://www.openstreetmap.org/?lat=28.077361&lon=-82.570335&zoom=18&layers=B000FTF>
> 
> There's no sign saying "no left turn".  There's no barrier.  There's no 
> painted median.  There's nothing to map.

And as far as supporting user preferences, these all have to be 
converted into modifications of the cost structures or the restrictions. 
It might be possible for someone to encode angle information into the 
graph file so the router could use that also, but it is not a common 
practice except in GPS devices.

I have not looked at the Navteq data for the link you posted, but I 
would expect that traveling west to south allong Gunn HWY that there is 
a turn restriction that would prevent the router from turning hard left 
up onto Walsh Ln. This would force all routes from the west to make a 
right turn from the E-W hwy onto Walsh Ln.

-Steve

> ------------------------------------------------------------------------
> 
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing