Module nearest 

least_distance: the least distance between two sets of points — a point, curves, surfaces, trimmed faces — and two points attaining it, by branch and bound over pieces of them.

How

A Piece is part of one of the sets: a span of a curve, a patch of a surface. It knows points whose convex hull holds all of it (its control points: every weight is positive, so a rational piece lies in their hull too), a point it attains, and how to cut itself in two. For a pair of pieces the hulls give a lower bound on the distance between them, and the attained points an upper bound on the least distance overall. Pairs are taken least lower bound first; a pair whose lower bound is definitely above the best distance attained holds nothing nearer and is dropped, and any other is cut, its larger piece in two. The search is done once the attained distance is not definitely above the least lower bound left: nothing can then be shown to be nearer.

The lower bound is the separation of the two hulls along the direction between them, or of their boxes, whichever is more. Along the right direction it is off by the square of a piece’s size, not by the size itself, as a box’s is: near a minimum that keeps a handful of pairs alive at each level, rather than a number growing with every level.

What is returned

Two attained points, and the least distance as an enclosure: from the least lower bound of every pair still standing to the distance between the two points. Pieces stop being cut once they are smaller than the caller’s handoff (see “Subdivide to isolate, then Newton to refine” in AGENTS.md), and the search stops at max_nodes pairs; either only leaves the enclosure wider, never wrong. The pairs left at the handoff are returned too, for a caller to refine each with Newton.

A piece is also left as it is once its points spread no further than they are wide ([resolved]). Its hull points are enclosures, and the bound from them is off by their width as well as by the piece’s size: cutting halves the size, never the width. A span of a traced curve, its control points 2e-6 wide, was cut until its domain was two ULPs wide because its box never came under the handoff; the distance it bounds is as wide as its data, and no cut could make it sharper.

Structs

CurveSpan

A span of a 3-D curve: a piece of the curve’s points, At its parameter.

Nearest

The least distance between two sets, as least_distance finds it.

PointPiece

A single point: a set of one piece that cannot be cut.

SurfacePatch

A patch of a surface: a piece of the surface’s points, At its parameters.

Traits

Piece

Part of a set a distance is measured to (see the module docs).

Functions

could_come_within

Whether the set a is pieces of could come within reach of the set b is pieces of: least_distance’s search for a question that needs no least distance. A pair whose lower bound is definitely beyond reach is dropped before anything is asked of it, attaining a point being what costs on a trimmed face, and the first points attained within it end the search. So two parts a hair apart cost a few cuts, and two lying on each other one look. What the search cannot tell apart, at the handoff or at max_nodes pairs, could be within it.

least_distance

The least distance between the set a is pieces of and the set b is pieces of (see the module docs).