Module mesh_hausdorff 

Certified Hausdorff distance between two triangle meshes (#148, D15).

What is certified

one_sided_hausdorff returns an interval [lower, upper] certain to contain h(A, B) = max over a in A of min over b in B of |a - b|, the one-sided Hausdorff distance between the surfaces of two meshes, and hausdorff_distance the two-sided max(h(A, B), h(B, A)) together with both one-sided intervals. Both ends are guarantees:

• lower is d(y, B) for a sampled point y of A, bounded below. d(y, B) is the minimum over the triangles T of B of d(y, T), and each d(y, T) is bounded below through the support function of the convex T: for every direction u with |u| <= 1, d(y, T) >= min over corners c of T of u . (y - c). The direction is taken towards the computed nearest point, where the bound is tight, and triangles the search never opens are bounded by their boxes.
• upper bounds every point of A. A’s triangles are subdivided, and over one piece t, max over x in t of d(x, B) <= min over T of max over corners v of t of d(v, T): d(., T) is convex, so its maximum over a triangle is at a corner. Each d(v, T) is bounded above by the distance to a point of T itself.

The witnesses are point_from, the sample realising lower, and point_to, its nearest point found on the other mesh.

Rounding accounted for

The input coordinates are taken as exact. Every bound is computed in binary64 and widened by an explicit margin in the standard model (fl(a op b) = (a op b)(1 + d), |d| <= eps / 2, eps = 2^-52), with no underflow assumed:

• A point of T is a + s (b - a) + t (c - a) with s, t >= 0 and s + t <= 1 up to three units in the last place. Its rounded evaluation, the parameter overshoot and the rounded length |v - p| together stay below 8.5 eps S, with S = |v| + |a| + |b| + |c|; the upper bound adds 16 eps S.
• The support bound normalises u and shrinks it by 4 eps so |u| <= 1 survives rounding; each u . (v - c) is off by at most 2.5 eps (|v| + |c|), and the lower bound subtracts 4 eps (|v| + max |c|).
• A box gap is shrunk by 4 eps of itself: coordinate differences keep their sign and the rounded Euclidean length is within 2 eps.
• Subdivision points are rounded midpoints, so a piece is only close to the exact piece of A it stands for. Each corner carries its drift, the parent’s plus eps |m| per midpoint; the distance is 1-Lipschitz, so a piece’s upper bound adds its largest drift and a sample’s lower bound subtracts its own. point_from is therefore within that drift (a few units in the last place of its coordinates) of A, not on it.
• A flat patch of B (below) carries a certified excess, rounded up.

No other rounding enters: branch decisions (which Voronoi region, which edge to split, which triangles to try) only choose a point, a direction or a candidate, and any choice keeps the bounds sound; they affect how fast the interval closes, not whether it contains the distance.

Method

Branch and bound over A’s triangles. Pieces are kept in a queue by upper bound; the largest is split at the midpoint of its longest edge, the midpoint is measured to raise lower, and pieces whose bound falls to lower are dropped. Nearest queries walk a bounding-volume hierarchy over B with a node bound of max over corners of the box gap, which is a certified lower bound of what any triangle below the node can offer, seeded with the triangles found nearest to the piece’s corners.

One triangle at a time, a piece over the seam between two triangles of a flat face stays loose until it is split below the accuracy, along every seam. So flat convex patches of B – two triangles forming a convex quadrilateral, the fan around an interior vertex with a convex link – bound a piece as one convex set, up to a certified excess (see patches).

The hierarchy is private rather than axiolid-spatial’s: that one ranks candidates by box-to-box gap and returns the nearest box, where this search needs a best-first walk under a caller’s bound over several points at once, and keeps axiolid-measure free of a dependency for it.

Convergence

A piece nearest to a single triangle or flat patch of B is bounded exactly up to rounding, so only pieces across the medial surfaces of B need splitting. Two things end the refinement early, and the interval is sound either way, only wider than asked: the split budget, and a request for an accuracy below the rounding margins, where pieces stop splitting once their edges are within rounding of their coordinates.

Scope

This is the distance between SURFACES, like crate::mesh_distance: a mesh wholly inside a closed mesh is as far from it as from its boundary. Degenerate triangles are measured as their edges. Open, non-manifold and self-intersecting meshes are all fine; the Hausdorff distance is defined for any point sets.

Structs

HausdorffBounds

An interval certain to contain a Hausdorff distance, with its witness.

MeshHausdorff

The two-sided Hausdorff distance and both one-sided ones.

Enums

HausdorffError

Why a Hausdorff query could not be answered.

Functions

hausdorff_distance

Two-sided Hausdorff distance between a and b, to within accuracy.

one_sided_hausdorff

One-sided Hausdorff distance h(from, to), to within accuracy.