Anthony wrote:
On Wed, Jul 21, 2010 at 1:38 PM, Stephen Woodbridge
<[email protected] <mailto:[email protected]>> 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
[email protected]
http://lists.openstreetmap.org/listinfo/routing
_______________________________________________
Routing mailing list
[email protected]
http://lists.openstreetmap.org/listinfo/routing
