Crate axiolid_triangulate

Constrained Delaunay triangulation with bounded quality refinement.

Why this exists

The mesh boolean’s retriangulation path was ear clipping. Ear clipping terminates and it is fast, but it offers no angle guarantee: it fans from whichever ear is convex, so a narrow opening near a far boundary corner produces slivers whose aspect ratio is bounded only by the input’s own geometry. A sliver is not a cosmetic problem downstream – normals of a near-degenerate triangle are numerically meaningless, and every consumer that shades, offsets, or measures from those normals inherits the error.

This crate replaces “some valid triangulation” with a triangulation whose quality is stated and checked:

• every constraint edge survives as a union of output edges,
• the result is Delaunay away from the constraints (empty-circumcircle, decided by the certified incircle predicate rather than by a floating-point circumcircle test),
• with Quality refinement, interior angles meet a caller-chosen minimum, or the call reports that it could not get there.

The guarantee is conditional, and says so

Ruppert refinement does not terminate for every input. Two boundary segments meeting at a small angle cannot be fixed by inserting interior points: splitting one segment to fix the angle creates a shorter segment that is itself too close to its neighbour, and the process diverges. This implementation therefore carries an explicit Steiner budget and reports RefineOutcome::Capped when it stops early. The triangulation is still valid and still constrained-Delaunay when capped – only the angle bound is unmet. Silently returning a worse mesh than requested would make the quality parameter a lie.

Structs

Constraint

A constraint edge, as indices into the input point slice.

Quality

A quality target for refinement.

Triangulation

A planar triangulation over a point set, honouring constraint edges.

Enums

RefineOutcome

What refinement actually achieved.

TriangulationError

Why a triangulation could not be produced.

Functions

refine

Refine an existing triangulation in place.

triangulate

Build a constrained Delaunay triangulation of points.

triangulate_refined

Build a constrained Delaunay triangulation and refine it toward quality.