axiolid_triangulate/
lib.rs

1// SPDX-License-Identifier: MPL-2.0
2#![forbid(unsafe_code)]
3#![warn(missing_docs)]
4
5//! Constrained Delaunay triangulation with bounded quality refinement.
6//!
7//! # Why this exists
8//!
9//! The mesh boolean's retriangulation path was ear clipping. Ear clipping
10//! terminates and it is fast, but it offers no angle guarantee: it fans from
11//! whichever ear is convex, so a narrow opening near a far boundary corner
12//! produces slivers whose aspect ratio is bounded only by the input's own
13//! geometry. A sliver is not a cosmetic problem downstream -- normals of a
14//! near-degenerate triangle are numerically meaningless, and every consumer
15//! that shades, offsets, or measures from those normals inherits the error.
16//!
17//! This crate replaces "some valid triangulation" with a triangulation whose
18//! quality is *stated and checked*:
19//!
20//! - every constraint edge survives as a union of output edges,
21//! - the result is Delaunay away from the constraints (empty-circumcircle,
22//!   decided by the certified `incircle` predicate rather than by a
23//!   floating-point circumcircle test),
24//! - with [`Quality`] refinement, interior angles meet a caller-chosen
25//!   minimum, or the call reports that it could not get there.
26//!
27//! # The guarantee is conditional, and says so
28//!
29//! Ruppert refinement does not terminate for every input. Two boundary
30//! segments meeting at a small angle cannot be fixed by inserting interior
31//! points: splitting one segment to fix the angle creates a shorter segment
32//! that is itself too close to its neighbour, and the process diverges. This
33//! implementation therefore carries an explicit Steiner budget and reports
34//! [`RefineOutcome::Capped`] when it stops early. The triangulation is still
35//! valid and still constrained-Delaunay when capped -- only the angle bound
36//! is unmet. Silently returning a worse mesh than requested would make the
37//! quality parameter a lie.
38
39use axiolid_core::Point2;
40use axiolid_guarantees::{Certified, Sign};
41use axiolid_predicates::{incircle, orient2d};
42
43mod build;
44mod mesh;
45mod recover;
46mod refine;
47
48pub use build::triangulate;
49pub use mesh::{Triangulation, TriangulationError};
50pub use refine::{refine, triangulate_refined, Quality, RefineOutcome};
51
52/// A constraint edge, as indices into the input point slice.
53///
54/// Held as a pair rather than as two points so the caller's vertex identity
55/// survives the triangulation: a consumer that knows "edge 3 was my window
56/// head" can still find it in the output.
57#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
58pub struct Constraint {
59    /// Index of the first endpoint.
60    pub a: u32,
61    /// Index of the second endpoint.
62    pub b: u32,
63}
64
65impl Constraint {
66    /// Construct a constraint between two vertex indices.
67    ///
68    /// Endpoints are stored in ascending order so that `(a, b)` and `(b, a)`
69    /// are the same constraint. An undirected edge compared directionally is
70    /// a classic source of "constraint lost" bugs that only appear when the
71    /// caller happens to list an edge the other way round.
72    #[must_use]
73    pub fn new(a: u32, b: u32) -> Self {
74        if a <= b {
75            Self { a, b }
76        } else {
77            Self { a: b, b: a }
78        }
79    }
80}
81
82/// The proven sign of a predicate, or `Sign::Zero` when the configuration is
83/// exactly degenerate.
84///
85/// The certified predicates escalate to exact arithmetic internally, so
86/// `Uncertain` cannot survive a top-level call. Treating it as `Zero` rather
87/// than unwrapping keeps this total: a degenerate answer is a real geometric
88/// outcome here (three collinear points, four cocircular ones), and the
89/// callers below all branch on strict positivity.
90pub(crate) fn decided(certified: Certified) -> Sign {
91    match certified {
92        Certified::Certain { sign, .. } => sign,
93        // `Certified` is `#[non_exhaustive]`, so a wildcard is required. Any
94        // future variant means "not proven", which is the same conservative
95        // answer as `Uncertain`.
96        _ => Sign::Zero,
97    }
98}
99
100/// Orientation of three points, decided exactly.
101///
102/// Wraps the certified predicate so the sign convention is stated once here
103/// rather than re-derived at each call site.
104pub(crate) fn turns_left(a: Point2, b: Point2, c: Point2) -> bool {
105    decided(orient2d(a, b, c)) == Sign::Positive
106}
107
108/// Whether `a`, `b`, `c` are exactly collinear.
109pub(crate) fn collinear(a: Point2, b: Point2, c: Point2) -> bool {
110    decided(orient2d(a, b, c)) == Sign::Zero
111}
112
113/// Whether `d` lies strictly inside the circumcircle of `a`, `b`, `c`.
114///
115/// `a`, `b`, `c` must be counter-clockwise; the caller guarantees that by
116/// construction. Decided by the certified `incircle` predicate: a
117/// floating-point circumcircle test flips sign on nearly-cocircular input,
118/// and a flip decision made on a wrong sign can cycle forever.
119pub(crate) fn in_circumcircle(a: Point2, b: Point2, c: Point2, d: Point2) -> bool {
120    decided(incircle(a, b, c, d)) == Sign::Positive
121}
axiolid_triangulate/lib.rs

axiolid_triangulate/
lib.rs
