Module polyline_hausdorff 

Hausdorff distance between polylines, and a certified Fréchet decision (#147, ledger row H4).

The Hausdorff distance treats both curves as continuous piecewise-linear point sets (not just their vertices). The one-sided distance from a to b is the supremum, over every point of a, of that point’s distance to the nearest point of b; the two-sided distance is the larger of the two one-sided distances. Unlike the Fréchet distance, it has no notion of a monotone walk, so it can be much smaller than the Fréchet distance for curves that pass close to each other out of step, and it is not symmetric in general – see one_sided_polyline_hausdorff_distance.

Algorithm

For one segment of a, parametrised a(t) = p0 + t * d for t in [0, 1], the distance to b is f(t) = min over every feature of b (a vertex, or a segment’s infinite line restricted to where the foot of a(t) falls inside the segment) of dist(a(t), feature). Distance squared to a fixed point, or to an infinite line, is a quadratic function of t (an affine image of a convex distance), so on any sub-interval where a single feature is uniquely the minimum, f is convex there and has no interior local maximum: its maximum on such a sub-interval sits at an endpoint. The candidates for the segment’s supremum are therefore the segment’s own endpoints, t = 0 and t = 1, plus every t where two features of b are simultaneously the minimum – a tie found by solving a (at most) quadratic equation per pair of features, restricted to any line feature’s activity window. At every candidate, the true minimum distance over all of b’s features is evaluated (ordinary clamped point-to-segment distance, minimised over every segment of b), and the largest of these is the segment’s contribution. This is O(m^2) per segment of a against m segments of b, so O(n * m^2) for one direction – worth revisiting if a crate consumer needs it faster, but correctness came first here.

Rounding

Everything is f64. Tie candidates are roots of quadratics solved in floating point, so a genuinely exact tie can be missed, or found a few ULPs from its true parameter; the evaluation step then reads the true minimum at that (slightly off) point, so the reported supremum can be a few ULPs short of the exact answer. Nothing here is certified.

Enums

FrechetDecision

A certified answer to the Fréchet decision problem: whether the continuous Fréchet distance is at most eps.

Functions

frechet_decide_certified

A certified decision for whether the continuous Fréchet distance between a and b is at most eps, unlike frechet_at_most (cheaper, but its module docs say plainly it is not certified).

frechet_decide_certified_2d

frechet_decide_certified in the plane.

one_sided_polyline_hausdorff_distance

The supremum, over every point of polyline a, of that point’s distance to the nearest point of polyline b. Both curves are treated as continuous piecewise-linear point sets, not just their vertices.

one_sided_polyline_hausdorff_distance_2d

one_sided_polyline_hausdorff_distance in the plane.

polyline_hausdorff_distance

The symmetric Hausdorff distance between polylines a and b: the larger of the two one-sided distances (see one_sided_polyline_hausdorff_distance).

polyline_hausdorff_distance_2d

polyline_hausdorff_distance in the plane.