Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Routing miscalculates the ShortestPath when one border has zero length #58

Closed
amastrobera opened this issue Nov 15, 2019 · 12 comments
Closed

Comments

@amastrobera
Copy link

amastrobera commented Nov 15, 2019

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.

image

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

@autonomobil
Copy link

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

image

@amastrobera
Copy link
Author

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

@poggenhans
Copy link
Contributor

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

@mitsudome-r
Copy link
Contributor

mitsudome-r commented Nov 19, 2019

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.

std::pair<LineString1T, LineString2T> align(LineString1T left, LineString2T right) {

@poggenhans
Copy link
Contributor

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
Copy link
Contributor

mitsudome-r commented Nov 19, 2019

@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
Copy link
Contributor

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
Copy link
Contributor

@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
Copy link
Author

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

@poggenhans
Copy link
Contributor

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

@autonomobil
Copy link

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

@poggenhans
Copy link
Contributor

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants