Module frechet

Fréchet distance between polylines (#147).

The Fréchet distance is the least leash length that lets two walkers traverse the two curves from start to end, each moving only forward. The discrete version walks vertex to vertex; the continuous version walks along the segments too, and is never larger.

• discrete_frechet_distance: the Eiter-Mannila dynamic programme, O(nm) time and O(m) memory, iterative.
• frechet_at_most: the Alt-Godau decision, O(nm): can the curves be walked with a leash of length eps?
• frechet_distance: the continuous distance. The answer is always one of the critical values of the free space – a distance between two vertices, from a vertex to a segment, or from a point on a segment to two vertices of the other curve at once – so it is the least critical value the decision accepts, found by binary search over the sorted critical values. When there are more than CANDIDATE_BUDGET of them (there are O(n^2 m + n m^2)), the range is first narrowed by bisection on the decision, so memory stays bounded.

The _2d functions lift the points to z = 0, which changes no distance.

Rounding

Everything is f64. Critical values are computed in floating point, and the decision reads its free-space intervals with the same helpers, so at a vertex-to-vertex or vertex-to-segment critical value the decision sees exactly the distance the candidate was built from. A passage that opens at a point equidistant to two vertices is decided by comparing interval ends, which carry a few units of rounding; there the answer can be the next larger critical value. Nothing here is certified.

Enums

FrechetError

Why a Fréchet query was refused.

Constants

CANDIDATE_BUDGET

Critical values held at once before the range is narrowed by bisection.

Functions

discrete_frechet_distance

Discrete Fréchet distance between the vertex sequences of a and b.

discrete_frechet_distance_2d

discrete_frechet_distance in the plane.

frechet_at_most

Whether the continuous Fréchet distance between a and b is at most eps.

frechet_at_most_2d

frechet_at_most in the plane.

frechet_distance

Continuous Fréchet distance between the polylines a and b.

frechet_distance_2d

frechet_distance in the plane.