Add support for fold testing in router QA tools

[mraross]

A fold is a portion of a best route that doubles back on itself. A fold usually indicates an unnecessary loop in the best route. In the case of a single-line road, the route doubles back on the same line. In the case of a divided road, the route doubles back on the line in the opposite direction of the same road.

In fold testing, pick a pair of start/end point at from within a user-specified area, find the best route, and check for a fold. Any number of things can cause a fold: bad turn restrictions, bad road impactors, bad road topology, bad distortion field settings, etc.

[gleeming]

Folds on double lines (or any one way) can be completely valid when the origin is on one of the divided segments (or any one-way for that matter). If the destination is in the opposite direction, then the initial flow is forced away to the earliest place a turnaround can be performed. Sometimes this can be a very long distance. Fortunately I have found those cases to be equally valuable for QA as they help uncover bad turnaround locations (e.g. missed uturn or hookback restrictions on turning lanes).

On a related note, an enhancement for the router could be to permit non-truck vehicles to use a segment tagged with a cul-de-sac impactor as a reversal point. While this would also create a fold, in one-way starting cases it could provide a closer reversal location. Rules in the router restricting re-use of a segment on a path may need to be relaxed to accommodate this.

[mraross]

Thanks for defining the cases where folds are needed. I see folds as a QA metric, not a routing heuristic.

Your cul-de-sac as reversal point is an interesting routing heuristic.

[gleeming]

Here's a cul-de-sac test case that currently fails: 49.213475,-122.861915 to 49.15790,-122.76919 A u-turn is not permitted at the end of the divided strata roads just before the destination,. However if the route were instead allowed to continue to the cul-de-sac immediately west in the same complex and turn around there, there would be no violations. One segment would have to be traversed in both directions.

[cmhodgson]

Usually the dead-end logic handles cases like the one described by Graeme above, however it doesn't take into account turn restrictions or the complicated situations that can arise from them. There is no issue with traversing a segment in both directions, that was fixed long ago now. However I do question the validity of the turn restrictions on that segment as there are home on that segment and the reasonable way to reach them is by taking the restricted U-turn. I wonder if we really need those kind of U-turn restrictions at neighborhood entrances, as they really don't prevent any shortcutting that isn't totally reasonable.