Module bounding

Bounding volumes of 3D point sets (#118): the minimum enclosing sphere and a containing oriented box.

Minimum enclosing sphere: exact choice, enclosed output

Welzl’s algorithm, iterative, over a fixed pseudo-random visiting order. Whether a point lies in the sphere spanned by one to four support points is decided exactly (intervals, then dyadics):

• one support point: equality;
• two: the sign of (p - a) . (p - b);
• three, the least sphere through them (centred in their plane): with u = b - a, v = c - a, w = u x v and N = |u|^2 (v x w) + |v|^2 (w x u) (so the centre is a + N / 2|w|^2), the sign of |p - a|^2 |w|^2 - (p - a) . N;
• four, their circumsphere: with D = 2 u . (v x w) and M = |u|^2 (v x w) + |v|^2 (w x u) + |w|^2 (u x v), the sign of |p - a|^2 D - 2 (p - a) . M against the sign of D.

So the support set is the exact minimum sphere’s. The centre is enclosed from the same exact numerators and denominators, and the radius is rounded up, so the returned sphere contains the exact one and every input point. SphereEvidence::error bounds the centre’s distance from the exact centre and the radius’s excess over the exact radius.

Oriented box: certified containment, not certified optimality

oriented_bounding_box tries these orientations and keeps the least volume:

• the axis-aligned box;
• the principal axes of the points’ covariance;
• for each of the world axes, the principal axes, every face normal of the exact convex hull (crate::hull::convex_hull) and, for flat input, the plane’s normal: that normal as one axis and the exact minimum-area rectangle (axiolid_overlay::minimum_area_rectangle) of the points projected across it for the other two.

What is certified is containment: for every input point p and every axis, |(p - centre) . axes[i]| <= half_extents[i] holds exactly for the returned f64 values – the extents are measured in outward-rounded intervals. The volume is no more than the axis-aligned box’s. What is not claimed is the global minimum volume: an optimal box need not have a face flush with a hull face (O’Rourke’s exact algorithm, cubic in the hull size, is not implemented), so the result is a good box, not the best one.

Structs

BoxEvidence

How the box was chosen and how far its axes are from orthonormal.

EnclosingSphere

A sphere by its centre and radius.

MinimumSphere

The sphere and its evidence.

OrientedBoundingBox

The box and its evidence.

OrientedBox

A box by its centre, three unit axes and the half extents along them.

SphereEvidence

Which points determine the sphere and how exact the output is.

Enums

BoundingError

Why no bounding volume was built.

Functions

minimum_enclosing_sphere

The minimum sphere enclosing points.

oriented_bounding_box

A box holding every point, of volume no more than the axis-aligned box.