osrm-extract assert triggering on guidance intersection handler

[mjjbell]

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.

osrm-backend/src/guidance/turn_handler.cpp

Lines 239 to 243 in 79d4363

	Intersection TurnHandler::handleThreeWayTurn(const EdgeID via_edge, Intersection intersection) const
	{
	BOOST_ASSERT(intersection.size() == 3);
	const auto obvious_index = findObviousTurn(via_edge, intersection);
	BOOST_ASSERT(intersection[0].angle < 0.001);

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.

osrm-backend/src/extractor/intersection/intersection_analysis.cpp

Line 654 in 79d4363

const auto is_uturn_angle = is_uturn(turn_angle);

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.

osrm-backend/src/extractor/intersection/intersection_analysis.cpp

Lines 697 to 705 in 79d4363

	// Check that the perceived angles order is the same as the initial OSM one
	if (next->first.angle < curr->first.angle)
	{ // If the true bearing is out of the initial order (next before current) then
	// adjust the next road angle to keep the order. The adjustment angle is at most
	// 0.5° or a half-angle between the current angle and 360° to prevent overlapping
	const auto angle_adjustment =
	std::min(.5, util::restrictAngleToValidRange(360. - curr->first.angle) / 2.);
	next->first.angle =
	util::restrictAngleToValidRange(curr->first.angle + angle_adjustment);

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.

osrm-backend/include/util/coordinate.hpp

Line 44 in 79d4363

constexpr const double COORDINATE_PRECISION = 1e6;

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.

[mjjbell]

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.

[mjjbell]

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 |

[mjjbell]

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°.

[mjjbell]

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:

1. 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.

2. 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.

3. 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.