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:

• triangulate covers the exact convex hull of the input, collinear hull points included (a symbolic vertex at infinity closes the hull during the build, so no thin hull triangle is lost),
• triangulate_domain keeps exactly the triangles inside the outer rings and outside the holes it is given, and reports the points it dropped (Triangulation::outside_points),
• exactly coincident input points become one vertex, and the merge is reported (Triangulation::merged_points); a constraint between two of them is refused by name,
• every constraint edge survives as a union of output edges (one that runs through input vertices is split at them; triangulate_domain keeps only the pieces inside the domain),
• 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.

MergedPoint

An input point merged into an exactly coincident one.

Quality

A quality target for refinement.

Ring

A closed boundary of the domain, as indices into the input points.

Triangulation

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

Enums

RefineOutcome

What refinement actually achieved.

RingKind

What a ring bounds.

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_domain

Build a constrained Delaunay triangulation of the domain bounded by rings.

triangulate_refined

Build a constrained Delaunay triangulation and refine it toward quality.