Project-OSRM
osrm-extract assert triggering on guidance intersection handler
With the Washington State OSM extract.
Applying the fix #6215 to master.
osrm-extract with the default foot profile triggers an angle assertion when processing intersection guidance.
https://github.com/Project-OSRM/osrm-backend/blob/79d4363d5972ea4d69abd92b26cda80de7941365/src/guidance/turn_handler.cpp#L239-L243
The offending intersection is in a bus station: https://www.openstreetmap.org/node/3750788725
The fact that the assertion is triggered within handleThreeWayTurn on a four-way intersection hints at the problem here.
When processing the turns from one of the incoming edges to the intersection, it incorrectly identifies the straight-ahead turn as a u-turn, and discards the actual u-turn. https://github.com/Project-OSRM/osrm-backend/blob/79d4363d5972ea4d69abd92b26cda80de7941365/src/extractor/intersection/intersection_analysis.cpp#L654
Later in the processing it tries to fix the inconsistency in the angles as it rotates around the turns, effectively removing the u-turn from the list and making two 90 degree turns. This is what triggers the assertion. https://github.com/Project-OSRM/osrm-backend/blob/79d4363d5972ea4d69abd92b26cda80de7941365/src/extractor/intersection/intersection_analysis.cpp#L697-L705
Potential Fix
I'm not familiar with the guidance code, but increasing the coordinate precision to 7 decimal places is sufficient to fix the problem. Which probably means the nodes involved in the angle calculations are too close together to be calculated accurately at the current level of coordinate precision.
https://github.com/Project-OSRM/osrm-backend/blob/79d4363d5972ea4d69abd92b26cda80de7941365/include/util/coordinate.hpp#L44
It's been noted previously (e.g. #3368) that coordinate precision needs increasing to improve consistency, but now we have a case where it's breaking logical assumptions.
6dp is already giving us sub-10cm precision, so it might be the angle calculation code that needs tweaking instead.
Nevertheless, OSM stores coordinates to 7dp, so it would be beneficial to match it within OSRM to ensure any geometric errors aren't due to the precision loss during import.
After further investigation, the issue is indeed in the angle calculation code. The 7dp fix works by accident.
The problem occurs because the intersection in question includes a path that overlaps with the intersection. In this case, the path represents two ways connected to an elevator. OSRM will compress these into the same path.
https://www.openstreetmap.org/way/376473222
https://www.openstreetmap.org/way/376473226
Here is the minimal test case that triggers the assertion
@routing @foot
Feature: Foot - Intersections
Background:
Given the profile "foot"
Given a grid size of 2 meters
Scenario: Foot - Handles non-planar intersections
Given the node map
"""
f
|
a
|
b---c---d
|
e
"""
And the ways
| nodes | highway | foot |
| ac | footway | yes |
| bc | footway | yes |
| cd | footway | yes |
| cef | footway | yes |
When I route I should get
| from | to | route |
| a | d | ac,cd,cd |
This is what OSRM is seeing at the intersection.
Consider the turns for someone travelling south to the intersection (bearing 180°). The initial outgoing bearings for each turn are as expected:
The outgoing bearings are adjusted. The logic is complicated, but for footpaths it will consider the path bearing 10 meters from the intersection. In the case of the elevator path, this is now the other side of the intersection, so the bearing is flipped. Furthermore, it's viewed as a u-turn. Because of this we discard the real u-turn and no longer consider it in our calculations.
The turn angles are then calculated from the perceived bearings. This can be viewed as the angle between the incoming bearing path and the outgoing bearing path, extended from the intersection node.
Angles are then adjusted. Again there is some logic that tries to fix edge-cases. In this case however, the elevator path is adjusted back to 180°, because the initial bearings indicate it's not a u-turn (which is correct).
It then tries to reconcile the angles we have assigned to the turns. Rotating clockwise from the smallest angle, the angles should be increasing. However, the turn angles are 90°->0°->180°, so the middle angle is arbitrarily tweaked to 90.5° to make the angles consistent.
Thus, we reach the state that triggers the assertion.
We require intersection[0].angle < 0.001, but our first angle is 90°.
The 7dp fix works by accident because it calculates the elevator path bearing accurately enough to not view it as a u-turn (angle is greater than epsilon), but in other intersection scenarios we would still encounter the same problem. In any case, I think the upgrading to 7dp coordinates is still a good idea.
I see three possible ways to fix the assertion issue:
-
Update the representative coordinate logic for perceived bearings to work better for the foot profile. I suspect when designing for vehicles, the 10 metre lookahead on low priority roads made sense, but it doesn't work so well on footpaths. We probably only need to look ahead a few metres at most.
-
Simplify the angle correction logic. The edge-case fixing that tries to counteract multiple u-turns detected and non-increasing angles looks like a fragile solution. Instead we should try and handle these situations more gracefully.
-
Planarize the graph. This is the hard option, but potentially the only one that is robust to all the weird path configurations that can appear in OSM. This would ensure that any bearing/angle adjustments can't change to the extent that they are no longer consistent with the other intersection turns.