axiolid-triangulate

Constrained Delaunay triangulation with bounded quality refinement.

Latest release	0.3.7 (2026-11-03)
crates.io	axiolid-triangulate
Layer	algorithms (algorithm.planar)
API documentation	rustdoc · docs.rs
Source	crates/algorithms/planar/triangulate/

Overview

Constrained Delaunay triangulation with bounded quality refinement. The output of triangulate covers the exact convex hull of the input; triangulate_domain keeps exactly the triangles inside outer rings and outside holes, and reports the points it dropped. Exactly coincident points are merged into one vertex and the merge is reported, every constraint edge survives as a union of output edges (split at the input vertices on it; for triangulate_domain, only the pieces inside the domain), the result is Delaunay away from the constraints (decided by the certified incircle predicate), and optional Ruppert refinement drives interior angles toward a caller-chosen minimum. Refinement carries an explicit Steiner budget and reports when it was capped, so an unmet angle bound is never returned silently.

Depends on

• axiolid-core
• axiolid-guarantees
• axiolid-predicates

Changes

Latest release, 0.3.7 (2026-11-03):

Added

• The package now ships LICENSE and LICENSE-COMMERCIAL (symlinks to the repository root), so the licence texts travel with the archive (#358).
• TriangulationError::NonFinitePoint { index }: a point with a NaN or infinite coordinate is refused up front (#355).

Fixed

• A point with a non-finite coordinate is refused with NonFinitePoint. Recovery by walking the segment would read its orientation as exactly collinear and could return a made-up split (#355).

Changed

• Constraint recovery no longer scans every triangle per missing constraint. Edges are found through a vertex-to-triangle index that every flip keeps current, and the edges a constraint crosses and the vertices on it are found by walking the segment with the exact orientation predicate. The triangulation is identical, triangle for triangle. On a jittered grid with zigzag breaklines (triangulate_constraints benchmark, release build), 10,000 points with 4,950 segments took 12.1 s and now take 0.065 s; 49,729 points with 12,432 segments took 168 s and now take 0.175 s (best of three, same machine) (#355).

Full history: crates/algorithms/planar/triangulate/CHANGELOG.md