Snapping to intersections incurs random turn penalty costs

[danpat]

Given a scenario like this:

the "nearest" point is the end of one of those three lines. The distances are all equal, so the line we snap to depends on the search order in the RTree - it's essentially random from the user's perspective.

When we calculate the outgoing edge weights from our phantom nodes, we subtract the sum of the edge segments leading up to the snapped point from the total edge weight. The problem is that this will leave the turn penalty value as a remainder, even if we snap to the end of the line.

We should special-case this behaviour - if you snap to the end of a line (i.e. an intersection), we should set the outgoing edge weights to 0 to all directly connected outgoing edges.

The problematic code is here:

https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/geospatial_query.hpp#L458-L464

We calculate the % snapped along the line here:

https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/geospatial_query.hpp#L479

If that value is 1.0, then the forward_weight should be 100% of the edge weight, not just the sum of the proceeding segment weights.

I think it's OK logic that if you snap at 99.99% (e.g 1m back from the intersection), then you pay the full turn cost.

[danpat]

Heads up to anyone that tackles this: this will change a lot of our test cases - be prepared to verify/modify many many tests that currently depend on RTree snapping order.

[danpat]

A related problem to this: adding waypoints to existing routes at intersections.

If you have a route, and you add a waypoint exactly at an intersection, we will randomly snap to one of the approach roads to the intersection. The snapped road may not be on the original route, and this will force a potentially large re-routing. In reality, the waypoint doesn't require any detour, as it's basically exactly on the original route.

[MoKob]

@danpat is this related/the same as #2287? At first glance, I would say it to be the same problem

[mjjbell]

This is now fixed by #5953