<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
(I've sent this mail to <a class="moz-txt-link-abbreviated"
href="mailto:reply+i-24834155-b934533b0af3ded2f59a77048d6073f5c7a2c5b1-1106958@reply.github.com">reply+i-24834155-b934533b0af3ded2f59a77048d6073f5c7a2c5b1-1106958@reply.github.com</a><br>
but it is not showing up on the mailing list, so I send it again,
directly to the graphHopper mailing list)<br>
<br>
<br>
Hi there, <br>
<br>
I was reading the code regarding turn cost found at: <br>
<br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://github.com/graphhopper/graphhopper/pull/135/files">https://github.com/graphhopper/graphhopper/pull/135/files</a><br>
<br>
I feel that there is something wrong with the criterion for
inserting a shortcut during the PrepareContraction<br>
<br>
Let be the following graph portion: <br>
<br>
<tt>w x</tt><tt><br>
</tt><tt> \ /</tt><tt><br>
</tt><tt> a - c - b </tt><tt><br>
</tt><tt> / \</tt><tt><br>
</tt><tt> y z</tt><br>
<br>
we want to find shortcuts for contracting c. <br>
<br>
The criterion currently used is: <br>
is the path from a to b passing through c the strictly cheapest one?<br>
if yes, a shortcut is needed. <br>
This criterion includes the cost of manoeuvring from the segment a-c
to the segment c-b<br>
<br>
I might be wrong, but I believe that there is a problem with this
criterion. <br>
<br>
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. <br>
There are also cost of manoeuvring from w-a to a-c, and from c-b to
b-z. <br>
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. <br>
<br>
I therefore believe that the criterion for adding a shortcut a-b
when contracting c should be the following <br>
<br>
if<br>
for any incoming edges to a called I (eg: w-a, and y-a)<br>
for any outgoing edge from b called O (eg: b-x, and b-z)<br>
the path I-a-c-b-O is the strictly cheapest one binding I to
O then<br>
then a shortcut must be added<br>
<br>
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. <br>
<br>
<div class="moz-signature">-- <br>
<table cellspacing="0" width="400">
<tbody>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-style:
normal; font-variant: normal; font-weight: normal;
font-size: 14px; line-height: normal; font-size-adjust:
none; font-stretch: normal; vertical-align: top;"> <b>Renaud
De Landtsheer, Ir, Phd</b> </td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-style:
italic; font-variant: normal; font-weight: normal;
font-size: 14px; line-height: normal; font-size-adjust:
none; font-stretch: normal; vertical-align: top;">Sr
R&D Engineer</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-style:
normal; font-variant: small-caps; font-weight: normal;
font-size: 14px; line-height: normal; font-size-adjust:
none; font-stretch: normal; vertical-align: top;">
CETIC <br>
Rue des Frères Wright, 29/3 <br>
B-6041 Charleroi <br>
Phone: +32 71 490 754 </td>
</tr>
<tr>
<td colspan="2" style="border-top: 1px solid rgb(0, 102, 0);
background-color: rgb(255, 255, 255); font-style: italic;
font-variant: normal; font-weight: normal; font-size:
12px; line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;" align="top">
<p><br>
</p>
</td>
</tr>
</tbody>
</table>
</div>
</body>
</html>