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//! - [`triangulate`] covers the exact convex hull of the input, collinear
21//! hull points included (a symbolic vertex at infinity closes the hull
22//! during the build, so no thin hull triangle is lost),
23//! - [`triangulate_domain`] keeps exactly the triangles inside the outer
24//! rings and outside the holes it is given, and reports the points it
25//! dropped ([`Triangulation::outside_points`]),
26//! - exactly coincident input points become one vertex, and the merge is
27//! reported ([`Triangulation::merged_points`]); a constraint between two
28//! of them is refused by name,
29//! - every constraint edge survives as a union of output edges (one that
30//! runs through input vertices is split at them; `triangulate_domain`
31//! keeps only the pieces inside the domain),
32//! - the result is Delaunay away from the constraints (empty-circumcircle,
33//! decided by the certified `incircle` predicate rather than by a
34//! floating-point circumcircle test),
35//! - with [`Quality`] refinement, interior angles meet a caller-chosen
36//! minimum, or the call reports that it could not get there.
37//!
38//! # The guarantee is conditional, and says so
39//!
40//! Ruppert refinement does not terminate for every input. Two boundary
41//! segments meeting at a small angle cannot be fixed by inserting interior
42//! points: splitting one segment to fix the angle creates a shorter segment
43//! that is itself too close to its neighbour, and the process diverges. This
44//! implementation therefore carries an explicit Steiner budget and reports
45//! [`RefineOutcome::Capped`] when it stops early. The triangulation is still
46//! valid and still constrained-Delaunay when capped -- only the angle bound
47//! is unmet. Silently returning a worse mesh than requested would make the
48//! quality parameter a lie.
49
50use axiolid_core::Point2;
51use axiolid_guarantees::{Certified, Sign};
52use axiolid_predicates::{incircle, orient2d};
53
54mod adjacency;
55mod build;
56mod domain;
57mod hint;
58mod mesh;
59mod recover;
60mod refine;
61
62pub use build::triangulate;
63pub use domain::{triangulate_domain, Ring, RingKind};
64pub use mesh::{MergedPoint, Triangulation, TriangulationError};
65pub use refine::{refine, triangulate_refined, Quality, RefineOutcome};
66
67/// A constraint edge, as indices into the input point slice.
68///
69/// Held as a pair rather than as two points so the caller's vertex identity
70/// survives the triangulation: a consumer that knows "edge 3 was my window
71/// head" can still find it in the output.
72#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
73pub struct Constraint {
74 /// Index of the first endpoint.
75 pub a: u32,
76 /// Index of the second endpoint.
77 pub b: u32,
78}
79
80impl Constraint {
81 /// Construct a constraint between two vertex indices.
82 ///
83 /// Endpoints are stored in ascending order so that `(a, b)` and `(b, a)`
84 /// are the same constraint. An undirected edge compared directionally is
85 /// a classic source of "constraint lost" bugs that only appear when the
86 /// caller happens to list an edge the other way round.
87 #[must_use]
88 pub fn new(a: u32, b: u32) -> Self {
89 if a <= b {
90 Self { a, b }
91 } else {
92 Self { a: b, b: a }
93 }
94 }
95}
96
97/// The proven sign of a predicate, or `Sign::Zero` when the configuration is
98/// exactly degenerate.
99///
100/// The certified predicates escalate to exact arithmetic internally, so
101/// `Uncertain` cannot survive a top-level call. Treating it as `Zero` rather
102/// than unwrapping keeps this total: a degenerate answer is a real geometric
103/// outcome here (three collinear points, four cocircular ones), and the
104/// callers below all branch on strict positivity.
105pub(crate) fn decided(certified: Certified) -> Sign {
106 match certified {
107 Certified::Certain { sign, .. } => sign,
108 // `Certified` is `#[non_exhaustive]`, so a wildcard is required. Any
109 // future variant means "not proven", which is the same conservative
110 // answer as `Uncertain`.
111 _ => Sign::Zero,
112 }
113}
114
115/// Orientation of three points, decided exactly.
116///
117/// Wraps the certified predicate so the sign convention is stated once here
118/// rather than re-derived at each call site.
119pub(crate) fn turns_left(a: Point2, b: Point2, c: Point2) -> bool {
120 decided(orient2d(a, b, c)) == Sign::Positive
121}
122
123/// Whether `a`, `b`, `c` are exactly collinear.
124pub(crate) fn collinear(a: Point2, b: Point2, c: Point2) -> bool {
125 decided(orient2d(a, b, c)) == Sign::Zero
126}
127
128/// Whether `d` lies strictly inside the circumcircle of `a`, `b`, `c`.
129///
130/// `a`, `b`, `c` must be counter-clockwise; the caller guarantees that by
131/// construction. Decided by the certified `incircle` predicate: a
132/// floating-point circumcircle test flips sign on nearly-cocircular input,
133/// and a flip decision made on a wrong sign can cycle forever.
134pub(crate) fn in_circumcircle(a: Point2, b: Point2, c: Point2, d: Point2) -> bool {
135 decided(incircle(a, b, c, d)) == Sign::Positive
136}