Open area routing: known defects and deferred review points
Open area routing lands in stages. This tracks what is knowingly left undone, so that none of it has to be rediscovered from the diff.
Nothing here blocks #7161. The first group are defects in the snapping work that follows it; the second are review points from #7161 that were answered with "later" rather than with code.
Known defects
1. A table cell is wrong when only one of its two coordinates is on a plaza
Snapping a coordinate that lies inside an area charges the walk to the vertex against the phantom's weight offset. The search seeds a source with the negation of that offset and a target with the value itself, so the sign depends on which end of the journey the coordinate is, and the snapping code is told which by its position in the coordinate list.
That holds for a route. In a table every coordinate is both. Coordinate 0 is the source
of row 0 and the destination of column 0, so one of the two is charged the wrong way round.
With m on a plaza and e off it:
| m → e | e → m | |
|---|---|---|
/route duration |
115.8 s | 79.8 s |
/table duration |
115.8 s | 51.2 s |
/route distance |
161.7 m | 161.7 m |
/table distance |
50 m | 250 m |
The distances are wrong both ways, because a table's distances are graph distances between snapped points and never included the walk at all.
Cells with both ends on one plaza are correct, because those are computed from the polygon rather than taken from the search, and they are the only ones the cucumber scenarios assert.
The fix is to stop the approach cost being role-dependent: carry it on the phantom instead
of folding it into an offset. That grows PhantomNode from 80 to 84 bytes and
SegmentHint from 84 to 88, so ENCODED_SEGMENT_HINT_SIZE goes from 112 to 120 and the
hint string gets longer. Hints are already marked deprecated in include/engine/hint.hpp
and are invalidated by a data change in any case.
2. A trip whose coordinates all snap to the same vertex reports 0 m
On a plaza with nothing in it, several coordinates can share a cheapest way out, so they
all snap to the same corner. ShortestPathSearch over identical candidate sets returns a
result with no legs and is_valid() false, and /trip reports a tour of 0 m.
The geodesic pass cannot repair it: it rewrites legs, and there are none. A leg between two coordinates on one plaza may have no graph path behind it at all, so this wants the route to be built rather than corrected. The same coordinates on a plaza with an obstacle, which makes them snap to different vertices, give a correct tour.
3. annotations=nodes is not stable at the ends of a route
The first and last entries of a leg's node list are read from the segment its phantom sits on, not from anything the route travelled along. Two candidates can share a location and differ in segment id, since a coordinate snapping to a junction projects onto every way meeting there. Which one is reported then depends on the order the search settled nodes in, and CH and MLD do not always agree. The geometry, distance and duration are identical; only the node ids differ.
The mechanism is general and predates this work. Area snapping makes it common, because it offers a candidate per direction leaving a vertex on purpose, and for a leg that the engine writes itself those terminal ids name a way the route never uses.
Consumers who need to know where a route began should read the waypoint. Fixing it properly means either having a leg carry its own terminal node ids or leaving them out of the annotation for such legs, which changes the array's length.
4. /match does not use the geodesic
/route, /table and /trip now agree about a journey with both ends on one plaza.
/match was not considered.
Deferred from review of #7161
process_areain the profile API (review comment). The current flow registers areas fromprocess_wayandprocess_relation, which reads oddly. A dedicatedprocess_areawould be cleaner and is a profile API change, so it wants its own discussion.index_priority_queueversusquery_heap(review comment). The area code carries its own priority queue. Either it should say in the header whyquery_heapdoes not fit, or it should use it.- Haversine in the mesher.
AreaMesher::run_dijkstraweights edges withboost::geometry::distance, which on these coordinates yields an angle rather than a length. Only the ratios matter to Dijkstra so the routes are right, but replacing it withcoordinate_calculation's haversine interacts withDijkstra::distance_epsilon, which is absolute. Seedocs/areas.md. - More kinds of entry point (review comment). Bridges, tunnels and stairways that start in the middle of an area, and possibly named POIs, are not entry points today.
- Two conventions for
a:nodes. #7161 changes the route step to render node names instead of raw ids, because meshing creates virtual nodes whose ids move whenever the mesh changes.features/step_definitions/matching.jsresolves the same column by its own path and was not changed, so four cells infeatures/testbot/matching.featurestill assert numeric ids. Either finish the conversion or record why match assertions keep ids.
Source: Project-OSRM/osrm-backend