[GraphHopper] Potential problem with contractions in turn cost

[Renaud De Landtsheer]

(I've sent this mail to 
reply+i-24834155-b934533b0af3ded2f59a77048d6073f5c7a2c5b1-1106958 at reply.github.com
but it is not showing up on the mailing list, so I send it again, 
directly to the graphHopper mailing list)


Hi there,

I was reading the code regarding turn cost found at:

https://github.com/graphhopper/graphhopper/pull/135/files

I feel that there is something wrong with the criterion for inserting a 
shortcut during the PrepareContraction

Let be the following graph portion:

w           x
  \         /
   a - c - b
  /         \
y           z

we want to find shortcuts for contracting c.

The criterion currently used is:
is the path from a to b passing through c the strictly cheapest one?
if yes, a shortcut is needed.
This criterion includes the cost of manoeuvring from the segment a-c to 
the segment c-b

I might be wrong, but I believe that there is a problem with this 
criterion.

When computing a path, you actually arrive from an incoming edge, say 
from w in the picture above, and you leave b through an outgoing edge, 
say through z.
There are also cost of manoeuvring from w-a to a-c, and from c-b to b-z.
These "boundary costs" might be different when passing through c, or 
when avoiding c, since you will enter another segment than a-c, and 
leave through another segment than c-b.

I therefore believe that the criterion for adding a shortcut a-b when 
contracting c should be the following

if
for any incoming edges to a called I (eg: w-a, and y-a)
     for any outgoing edge from b called O (eg: b-x, and b-z)
         the path I-a-c-b-O is the strictly cheapest one binding I to O then
             then a shortcut must be added

This criterion is more expensive to compute, and I believe that it is 
also a bit more demanding, that is: more shortcuts might be added.

-- 
*Renaud De Landtsheer, Ir, Phd*
Sr R&D Engineer
CETIC
Rue des Frères Wright, 29/3
B-6041 Charleroi
Phone: +32 71 490 754


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140110/4d62619a/attachment.html>