Struct Cdt 

pub struct Cdt { /* private fields */ }

Half-edge based Constrained Delaunay Triangulation.

Implementations

impl Cdt

pub fn new(bounds: (Point2, Point2)) -> Self

Create a new CDT with a super-triangle that contains the given bounds.

The bounds (min, max) define an axis-aligned rectangle. The super-triangle is constructed large enough to enclose this rectangle with margin.

pub fn with_capacity(bounds: (Point2, Point2), n: usize) -> Self

Create a new CDT with pre-allocated capacity for n points.

Pre-allocates vertex and triangle storage to avoid reallocations during bulk insertion. Each point insertion creates ~2 triangles, so 2*n + 1 triangle slots are allocated.

pub fn insert_point(&mut self, p: Point2) -> Result<usize, MathError>

Insert a point into the triangulation.

Returns the vertex index of the inserted point. If the point is a duplicate of an existing vertex (within tolerance), the existing vertex index is returned.

Errors

Returns MathError::ConvergenceFailure if the point cannot be located in any triangle (should not happen for valid inputs).

pub fn insert_points_hilbert( &mut self, points: &[Point2], ) -> Result<Vec<usize>, MathError>

Bulk-insert points sorted by Hilbert curve for O(1) amortized locate.

Returns a Vec where result[original_index] is the CDT vertex index. Points near the Hilbert curve walk path are inserted together, so each locate_point call starts close to the target triangle.

Errors

Returns MathError::ConvergenceFailure if any point cannot be located.

pub fn insert_constraint( &mut self, v0: usize, v1: usize, ) -> Result<(), MathError>

Insert a constraint edge between two existing vertices.

The edge is recovered by flipping intersecting unconstrained edges until the constraint edge appears in the triangulation.

Errors

Returns MathError::ConvergenceFailure if the constraint cannot be recovered after the maximum number of iterations.

pub fn triangles(&self) -> Vec<(usize, usize, usize)>

Get the triangles as index triples (vertex indices).

Only returns non-removed triangles that do not reference super-triangle vertices.

pub fn vertices(&self) -> &[Point2]

Get the vertices.

pub fn remove_exterior(&mut self, boundary: &[(usize, usize)])

Remove triangles outside the boundary defined by constraint edges.

Flood-fills from super-triangle-adjacent triangles, stopping at constraint edges. Also removes any triangle that references a super-triangle vertex.

pub fn flood_remove_from_point( &mut self, seed: Point2, constraints: &DetHashSet<(usize, usize)>, ) -> bool

Remove all non-removed triangles reachable from the triangle containing seed, stopping at constraint edges.

This is the standard CDT hole-removal approach: given a point known to be inside a hole, find its containing triangle and flood-fill remove.

Returns true if the seed triangle was found and removal occurred, false if no triangle contains the seed point (e.g. concave hole centroid falling outside the polygon).

pub fn extract_regions(&self, separators: &[(usize, usize)]) -> Vec<Vec<Point2>>

Partition remaining (non-removed) interior triangles into connected regions separated by the given separator edges.

After calling Cdt::remove_exterior, this method groups interior triangles into connected components. Two adjacent triangles belong to the same region unless the shared edge is in separators.

Returns a list of polygonal boundaries, one per connected region, ordered as closed loops in parameter space. Each polygon is the boundary of the union of triangles in that region.

Arguments

• separators — edges that act as region boundaries (typically the pcurve constraint edges inserted during NURBS boolean splitting). Stored as sorted (min, max) pairs.

pub fn constraint_edges(&self) -> &DetHashSet<(usize, usize)>

Get the set of constraint edges (sorted pairs).

Useful for distinguishing boundary constraints from interior (separator) constraints in callers like NURBS boolean splitting.