itinero / routing

The routing core of itinero.
Apache License 2.0
221 stars 69 forks source link

DirectionCalculator sometimes erroneously returns default turn direction of 'Left' #153

Closed jerryfaust closed 6 years ago

jerryfaust commented 6 years ago

The DirectionCalculator.Calculate method is provided with 3 coordinates, which determine an 'angle', and from which it will determine a relative turning direction (e.g. Right, Left, etc).

I have encountered circumstances in which two of the three points are identical, resulting in an calculated angle of NaN, and ultimately returning the default turning direction of Left.

Perhaps I only know enough to make bad judgments, but working my way backward to method RouteExtension.RelativeDirectionAt, I find the collection of 'shape' coordinates that make up the route. I don't know where or how these were generated, I can only see how they are used, so I don't really know if the problem is in the 'shape' collection, that it should not contain 2 consecutive identical coordinates, or if the problem is in the interpretation, of using consecutive coordinates to calculate the turning angle. For now, I have assumed that the problem is in the interpretation, and I have provided a possible solution.

Currently, the RouteExtension.RelativeDirectionAt method contains the following code which, based on the current position 'i', passes in the coordinates immediately before and after.

return DirectionCalculator.Calculate( 
    new Coordinate(route.Shape[i - 1].Latitude, route.Shape[i - 1].Longitude),
    new Coordinate(route.Shape[i].Latitude, route.Shape[i].Longitude),
    new Coordinate(route.Shape[i + 1].Latitude, route.Shape[i + 1].Longitude));

I have modified the code to allow for consecutive identical coordinates by doing the following:

int h = i - 1; // work backward from i to make sure we don't use an identical coordinate
int j = i + 1; // work forward from i to make sure we don't use an identical coordinate
while (h >= 0 && route.Shape[h].Latitude == route.Shape[i].Latitude 
              && route.Shape[h].Longitude == route.Shape[i].Longitude) h--;
while (j <= route.Shape.Length && route.Shape[j].Latitude == route.Shape[i].Latitude 
                               && route.Shape[j].Longitude == route.Shape[i].Longitude) j++;

return DirectionCalculator.Calculate(route, i,
    new Coordinate(route.Shape[h].Latitude, route.Shape[h].Longitude),
    new Coordinate(route.Shape[i].Latitude, route.Shape[i].Longitude),
    new Coordinate(route.Shape[j].Latitude, route.Shape[j].Longitude));

Do you think this is the right approach, or should this case have never occurred in the first place?

Thank you.

xivk commented 6 years ago

I think this is fine, there aren't supposed to be edges of length 0 in the route but this code makes things better and more robust. I'll have a closer look later and include it in the current source if you don't mind signing the contributor agreement, see contributing.md on why:

https://github.com/itinero/routing/blob/develop/CONTRIBUTING.md#how-to-contribute

If you have any idea why this route exists or how to reproduce this let us know here, it possibly points to a bug/issue elsewhere.