Fix snapping target locations to ways used in turn restrictions

mjjbell · mjjbell · commit 3771e99f74d6 · 2021-02-23T23:30:51.000Z
Currently there is an edge-case in the turn restriction implementation,
such that routes can not be found if the target input location snaps
to a way used in a (multi) via restriction.

With the addition of snapping input locations to multiple ways, we
can now also snap to the "duplicate" edges created for the restriction graph,
thereby fixing the problem.
This is achieved by adding the duplicate restriction edges to the
geospatial search RTree.

This does open up the possibility of multiple paths representing exactly
the same route - one using the original edge as a source, the other
using the duplicate restriction graph edge as source. This is fine,
as both edges are represented by the same geometry, so will generate
the same result.
diff --git a/features/car/multi_via_restrictions.feature b/features/car/multi_via_restrictions.feature
@@ -1031,3 +1031,61 @@ Feature: Car - Multiple Via Turn restrictions
             | from | to | route             | locations   |
 	    | a    | f  | ab,bc,cd,de,ef,ef | a,b,c,d,e,f |
 
+
+    @restriction-way
+    Scenario: Snap source/target to via restriction way
+        Given the node map
+            """
+            a-1-b-2-c-3-d
+            """
+
+        And the ways
+            | nodes |
+            | ab    |
+            | bc    |
+            | cd    |
+
+        And the relations
+            | type        | way:from | way:via | way:to  | restriction    |
+            | restriction | ab       | bc      | cd      | no_straight_on |
+
+        When I route I should get
+            | from | to | route    |
+            | 1    | 2  | ab,bc,bc |
+            | 2    | 3  | bc,cd,cd |
+
+
+    @restriction-way
+    Scenario: Car - Snap source/target to multi-via restriction way
+    # Example: https://www.openstreetmap.org/relation/11787041
+        Given the node map
+            """
+            |--g---f---e
+            a      |   1
+            |--b---c---d
+
+            """
+
+       And the nodes
+            | node | highway         |
+            | b    | traffic_signals |
+
+        And the ways
+            | nodes | oneway | name  |
+            | ab    | yes    | enter |
+            | bc    | yes    | enter |
+            | cd    | yes    | right |
+            | de    | yes    | up    |
+            | ef    | yes    | left  |
+            | fc    | yes    | down  |
+            | fg    | yes    | exit  |
+            | ga    | yes    | exit  |
+
+        And the relations
+            | type        | way:from | way:via    | way:to | restriction  |
+            | restriction | bc       | cd,de,ef   | fg     | no_u_turn    |
+
+        When I route I should get
+            | from | to | route              | locations           |
+            | a    | 1  | enter,right,up,up  | a,c,d,_             |
+            | 1    | a  | up,left,exit,exit  | _,e,f,a             |
diff --git a/src/extractor/edge_based_graph_factory.cpp b/src/extractor/edge_based_graph_factory.cpp
@@ -412,6 +412,44 @@ EdgeBasedGraphFactory::GenerateEdgeExpandedNodes(const WayRestrictionMap &way_re
             m_edge_based_node_distances.push_back(
                 m_edge_based_node_distances[nbe_to_ebn_mapping[eid]]);
 
+            const auto &forward_geometry = m_compressed_edge_container.GetBucketReference(eid);
+            const auto segment_count = forward_geometry.size();
+
+            NodeID current_edge_source_coordinate_id = node_u;
+            const EdgeData &forward_data = m_node_based_graph.GetEdgeData(eid);
+
+            const auto edge_id_to_segment_id = [](const NodeID edge_based_node_id) {
+              if (edge_based_node_id == SPECIAL_NODEID)
+              {
+                  return SegmentID{SPECIAL_SEGMENTID, false};
+              }
+
+              return SegmentID{edge_based_node_id, true};
+            };
+
+            // Add segments of edge-based nodes
+            for (const auto i : util::irange(std::size_t{0}, segment_count))
+            {
+                const NodeID current_edge_target_coordinate_id = forward_geometry[i].node_id;
+
+                // don't add node-segments for penalties
+                if (current_edge_target_coordinate_id == current_edge_source_coordinate_id)
+                    continue;
+
+                BOOST_ASSERT(current_edge_target_coordinate_id != current_edge_source_coordinate_id);
+
+                // build edges
+                m_edge_based_node_segments.emplace_back(
+                    edge_id_to_segment_id(edge_based_node_id),
+                    SegmentID{SPECIAL_SEGMENTID, false},
+                    current_edge_source_coordinate_id,
+                    current_edge_target_coordinate_id,
+                    i,
+                    forward_data.flags.startpoint);
+
+                current_edge_source_coordinate_id = current_edge_target_coordinate_id;
+            }
+
             edge_based_node_id++;
             progress.PrintStatus(progress_counter++);
         }
