Module exact_hausdorff 

Certified Hausdorff distance between the boundaries of two exact B-reps (#224).

What is certified

one_sided_boundary_hausdorff returns an interval [lower, upper] certain to contain h(A, B) = max over p in dA of d(p, dB), how far the boundary of A strays from the boundary of B, and boundary_hausdorff_distance the two-sided max(h(A, B), h(B, A)) with both one-sided intervals: the contract of crate::hausdorff_distance for meshes, on the exact boundaries instead of a tessellation of them. Both ends are guarantees:

• lower is d(p, dB) bounded below for a point p certainly on dA (an edge point, or a surface point at parameters its face’s domain is certified to contain), less p’s evaluation rounding (#439), by the same branch and bound as crate::boundary_distance with one side shrunk to the point.
• upper bounds d(p, dB) for every point of dA. The faces of A are covered by patches of their parameter domains (a patch is dropped only when certified outside its face), and each patch’s bound is the better of two:
  • a matched bound: when a face of B has the same surface family (for a cone the same radius and angle, for a B-spline the same knots, degrees and weights) and the very same trimming pcurves with the same intervals, both faces are one domain D mapped by S_A and S_B, so every S_A(u, v) of the patch has the boundary point S_B(u, v) of B within |S_A - S_B|. Written over the family’s basis, S_A - S_B = (o_A - o_B) + sum phi_k (a_k^A - a_k^B), bounded over the patch by its value at the centre plus each basis function’s oscillation times its coefficient difference. A rigid move of a solid changes only frames, so for a pure translation the bound is the translation itself on every patch at once, and for an identical copy zero up to rounding. For a rotation it is the displacement of the rotation, which may exceed the distance: it then only caps what the Lipschitz bound must refine;
  • the same bound for a face of B that is a translate of A’s but trimmed in another chart (#227), as a builder that trims in world coordinates makes it: same family, axes and shape, and trims equal after the parameter shift the translation induces, to within a measured residue. S_B re-charted by the shift is again one domain with S_A, the residue is folded in, and the bound is |t|. A turned or resized face is never matched this way (the derivation and the gate are in the private exact_hausdorff/translate.rs);
  • a Lipschitz bound: d(., dB) is 1-Lipschitz, so over a patch inside a sphere of radius r about c it is at most d(c, dB) + r, with d(c, dB) bounded above by a point found on dB plus that point’s evaluation rounding (#439). A B-spline patch’s sphere is about the control net’s box midpoint, not its witness, so the bound about the witness adds their distance (#459).

The witnesses are point_from, the point realising lower, and point_to, the nearest point found to it on the other boundary.

Method

Branch and bound over A‘s face patches, largest upper bound first: the patch is split across its longer side, and each half is bounded and, if its centre is certainly on the face, measured to raise lower. Edge spans of A are split alongside, only to place witnesses (the faces’ closures already hold every edge point), so a farthest point on an edge is approached along the edge. Point queries walk a tree of B’s elements that is refined once and shared by every query.

Before any split, each translation t a matched face carries seeds the lower bound with A’s support point against t on its edges: for a translate that point is exactly |t| from B’s boundary, whatever the shape, so a farthest point isolated at a corner is not left to edge bisection. For a body of several items (crate::exact_bodies) each item’s own support point is seeded: an item moved alone has its farthest point there, wherever the union’s support point lies.

Convergence and refusal

Copies offset by a translation (and identical copies) close in a few dozen splits whatever the accuracy, and usually in none: the matched bound holds every patch at |t| at once, and the support point is |t| from the other boundary when the solid’s support against t is on an edge (faces on planes, cylinders and cones). Elsewhere the Lipschitz bound closes at first order: an accuracy e needs patches of radius about e wherever the distance comes within e of the farthest, so the work grows with that area over e^2. Refinement stops at a fixed budget, or at the caller’s (one_sided_boundary_hausdorff_with_budget); the interval returned is then still sound, only wider than asked – a caller decides by its width, never by a guess. A face whose domain cannot be bounded is refused as by crate::boundary_distance.

Scope

This is the distance between BOUNDARIES. A solid wholly inside another is as far from it as its boundary is from the other’s boundary, not zero; containment is a separate classification.

Structs

BoundaryHausdorff

The two-sided Hausdorff distance between two exact boundaries and both one-sided ones.

Functions

boundary_hausdorff_distance

Two-sided Hausdorff distance between the boundaries of a and b, to within accuracy (#224).

one_sided_boundary_hausdorff

One-sided Hausdorff distance h(from, to) between two exact boundaries, to within accuracy (#224).

one_sided_boundary_hausdorff_with_budget

one_sided_boundary_hausdorff with the caller’s refinement budget: at most max_splits splits of from’s face patches and edge spans (#227).