[OSM-talk] turn restriction relations: via

[Nic Roets]

Let me first give a bit of an introduction to the algorithms for other
readers on the list. At first glance Dijkstra finds the shortest route to
any node n from a given node a, but exactly how (from the North, South etc)
node n was reached is not specified. So turning restrictions cannot be
handled.

One solution is to look at http://en.wikipedia.org/wiki/Line_graph but it
does not really handle complicated restrictions like this one:
A single carriage way S crosses a double carriage way consisting of ways A
and B at nodes D and E. Traveling down A you are not allowed to use S to
make a u-turn into B.

A simple solution to this problem is not to think of Dijkstra vertices as
OSM nodes, but to think of them as state-machine states, for example "I'm at
D traveling backwards along S". And the above mentioned restriction would
require having than 2 times as many possible states as there are segments.
That's all the ussual states ("I'm at ... traveling forwards / backwards
along ... without having triggered any restrictions") as well as states like
"I'm at D traveling backwards along S after triggering restriction R". This
last state will mean that :
S is in R's via
If W1, W2,...,Wk,S is the list of ways that I traveled along then there
exists a i such that Wi=R.from and Wi+1,...,Wk are all in R.via.

I guess there are even a few real world examples where we will need states
where more than one restriction was triggered. Like a small service way
leaving the abovementioned junction from E that you may not enter coming
from A. It means the code will not be very fast, but given how rare these
things are, speed's not an issue.

Based on this description I can't see why we should require that via ways
like S should be split into optimal ways, i.e. at D and E. The program will
run faster, but the mapper is ultimately responsible from spotting
ambigueties and splitting ways so that they don't occur.

Regards,
Nic
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk/attachments/20090329/c10be63f/attachment.html>