Routing miscalculates the ShortestPath when one border has zero length

[amastrobera]

Dear FZI,

I have cases where a lanelet is a junction lane. Say we are turning right at a junction. Right border is just one point (or a line with two equal points), while left border is a curve. In those cases the lanelet2.routing.RoutingGraph.shortestPath() does not take that lane into account, and calculates the path passing by other roads.

This case is very frequent (for junctions or corner roads). Can this be fixed ?

[autonomobil]

I think you can workaround this problem by adjusting the border to a very small line:

[amastrobera]

yea that's what I have done. I just ask them if it should be an issue or not

[poggenhans]

Hm, that looks like a bug. I'll try to find the time to look into it this week. Thanks for reporting!

[mitsudome-r]

This is probably due to miscalculation of the orientation of boundaries. You cannot calculate signed distance against a point(linestring with length 0). Since the lane boundary is treated as wrong direction in some cases, lane graph would be corrupted and thus routing fails.

https://github.com/fzi-forschungszentrum-informatik/Lanelet2/blob/46fd46ca2bbb755bf1f2e8ea21994fdae89c93d7/lanelet2_core/include/lanelet2_core/geometry/impl/LineString.h#L747

[poggenhans]

That shouldn't be the reason. This function checks which of the two linestrings of the lanelet has nonzero length and uses that for the signed distance calculation to the other boundary. There is even a unittest that covers this case. This kind of problem should also be visible in the debug routing graph.

But you are right in that it is most probably related to the problem that it is hard to determine neighborhood relationships for linestrings with zero length. Its not impossible, but hard to get right.

[mitsudome-r]

@poggenhans

This function checks which of the two linestrings of the lanelet has nonzero length and uses that for the signed distance calculation to the other boundary.

Are you referring to this line?

  if (!rightOfLeft && left.size() > 1) {
    left = left.invert();
  }

What it is checking is the size of the linestring, not the length. I believe if the boundary has multiple points with the same location, then this error could still happen.

[poggenhans]

I see. Linestrings that have duplicated points are not allowed in general. There are too many algorithms (also in boost::geometry) that rely on this. We should update or docs to reflect that. Linestings that have one single point are allowed however.

[poggenhans]

@amastrobera can you confirm that this problem is solved by using a single-point-linestring?

I tried to reproduce your issue and with my test cases everything worked fine with them.

[amastrobera]

@poggenhans yes I tried it just now. LineString3d of 1 point for border makes the path planning work.

[poggenhans]

Ok, thanks for checking. We have updated the doc and added a new validator to lanelet2_validation for this case.

[autonomobil]

How do you generate a "single-node"-way in josm?

[poggenhans]

Afaik, its not possible directly within JOSM. If you remove the second-last node from a way, the way will be deleted as well. But at least JOSM will not remove existing single node ways from loaded OSM files.

To create one, you would have to create it directly within lanelet2 or modify the osm file by hand.