axiolid_triangulate/mesh.rs
1// SPDX-License-Identifier: MPL-2.0
2
3//! The triangulation structure and the constrained Delaunay build.
4//!
5//! # Representation
6//!
7//! Triangles are stored in a flat array with a parallel neighbour array, the
8//! standard "triangle + halfedge" layout: halfedge `3t + i` belongs to
9//! triangle `t`, runs from vertex `i` to vertex `i + 1 mod 3`, and its twin
10//! is `halfedge[3t + i]`. A half-edge structure with explicit records would
11//! carry a pointer per edge and buy nothing here: compactness and cache
12//! locality win. Insertion and flips keep the twin array current locally;
13//! the `adjacency` module holds the rules and the debug check against a
14//! full recomputation.
15//!
16//! Vertices 0..n are the caller's points. During the build one more
17//! vertex, at infinity and without coordinates, closes the convex hull
18//! (see the `build` module); it is removed at the end, together with
19//! every triangle that touches it, and the rest covers the convex hull.
20
21use axiolid_core::Point2;
22
23use crate::domain::Ring;
24use crate::Constraint;
25
26/// Sentinel for "no neighbour across this halfedge".
27pub(crate) const NO_HALFEDGE: u32 = u32::MAX;
28
29/// Why a triangulation could not be produced.
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
31#[non_exhaustive]
32pub enum TriangulationError {
33 /// Fewer than three points were supplied, so no triangle exists.
34 TooFewPoints,
35 /// Every input point is collinear, so the triangulation has zero area.
36 ///
37 /// Reported rather than returning an empty triangulation: a caller that
38 /// asked to triangulate a degenerate polygon has a bug upstream, and an
39 /// empty result would hide it.
40 AllPointsCollinear,
41 /// A vertex could not be placed in any triangle during insertion.
42 ///
43 /// Indicates a corrupted adjacency rather than bad input. Reported so a
44 /// missing vertex surfaces as an error instead of as a silent hole in an
45 /// otherwise valid-looking mesh.
46 VertexUnplaceable {
47 /// Index of the vertex that could not be placed.
48 index: u32,
49 },
50 /// A constraint referenced a vertex index that does not exist.
51 ConstraintOutOfRange {
52 /// The offending index.
53 index: u32,
54 },
55 /// Two constraint pieces cross; a constraint is split at the vertices
56 /// on it first.
57 ///
58 /// Only reachable when two constraints cross at a point that is no
59 /// input vertex: an edge cannot survive if another required edge passes
60 /// through it. The crossing point would have to be inserted as a
61 /// vertex, which changes the caller's input, so this is reported
62 /// instead of silently repaired. A constraint that runs through input
63 /// vertices, or ends on another constraint, is not a crossing.
64 CrossingConstraints {
65 /// First endpoint of the piece that could not be recovered.
66 a: u32,
67 /// Second endpoint.
68 b: u32,
69 },
70 /// A constraint joins two input points at exactly the same position.
71 ///
72 /// Coincident points are merged into one vertex, so the constraint
73 /// would be an edge from that vertex to itself. Reported rather than
74 /// dropped: a caller who asked for an edge between two distinct
75 /// indices has two points where they meant one, or one where they
76 /// meant two.
77 CoincidentConstraint {
78 /// First endpoint, as an input index.
79 a: u32,
80 /// Second endpoint, as an input index.
81 b: u32,
82 },
83 /// A ring referenced a vertex index that does not exist.
84 RingOutOfRange {
85 /// Position of the ring in the ring list.
86 ring: u32,
87 /// The offending index.
88 index: u32,
89 },
90 /// A ring has fewer than three vertices, so it encloses nothing.
91 TooFewRingVertices {
92 /// Position of the ring in the ring list.
93 ring: u32,
94 },
95 /// A ring visits the same vertex twice.
96 ///
97 /// Two indices at one position count as one vertex, and so does
98 /// repeating the first index at the end to close the ring: a ring is
99 /// closed implicitly.
100 RepeatedRingVertex {
101 /// Position of the ring in the ring list.
102 ring: u32,
103 /// The later of the two occurrences, as an input index.
104 index: u32,
105 },
106 /// A ring doubles back on itself at a vertex.
107 ///
108 /// Both neighbours of the vertex lie on one side of it on a common
109 /// line, so the ring has a zero-width spike (or no area at all) there.
110 FoldedRing {
111 /// Position of the ring in the ring list.
112 ring: u32,
113 /// The vertex where the ring folds, as an input index.
114 index: u32,
115 },
116 /// The rings nest in a way that is neither inside nor outside: a region
117 /// has a winding other than 0 or 1.
118 ///
119 /// A hole outside every outer ring, a hole inside a hole, a hole listed
120 /// twice and an outer ring inside another all end here. Rings (or a
121 /// ring and itself) that cross between vertices are refused earlier, as
122 /// [`CrossingConstraints`](Self::CrossingConstraints).
123 MisnestedRing {
124 /// The lowest-numbered ring that carries the boundary crossed into
125 /// the region.
126 ring: u32,
127 /// The winding of that region.
128 winding: i32,
129 },
130 /// The rings enclose no triangle, so the domain is empty.
131 EmptyDomain,
132 /// An input point has a non-finite coordinate (NaN or infinite).
133 ///
134 /// The orientation and incircle predicates are exact only for finite
135 /// doubles; a non-finite one would read as exactly collinear and place
136 /// a made-up edge, so the input is refused.
137 NonFinitePoint {
138 /// Index of the first such point.
139 index: u32,
140 },
141}
142
143impl core::fmt::Display for TriangulationError {
144 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
145 match self {
146 Self::TooFewPoints => write!(f, "a triangulation needs at least three points"),
147 Self::NonFinitePoint { index } => {
148 write!(f, "point {index} has a non-finite coordinate")
149 }
150 Self::AllPointsCollinear => write!(f, "every input point is collinear"),
151 Self::VertexUnplaceable { index } => {
152 write!(f, "vertex {index} could not be placed in any triangle")
153 }
154 Self::ConstraintOutOfRange { index } => {
155 write!(f, "constraint references out-of-range vertex {index}")
156 }
157 Self::CrossingConstraints { a, b } => {
158 write!(f, "constraint ({a}, {b}) crosses another constraint")
159 }
160 Self::CoincidentConstraint { a, b } => {
161 write!(f, "constraint ({a}, {b}) joins two coincident points")
162 }
163 Self::RingOutOfRange { ring, index } => {
164 write!(f, "ring {ring} references out-of-range vertex {index}")
165 }
166 Self::TooFewRingVertices { ring } => {
167 write!(f, "ring {ring} has fewer than three vertices")
168 }
169 Self::RepeatedRingVertex { ring, index } => {
170 write!(f, "ring {ring} visits vertex {index} twice")
171 }
172 Self::FoldedRing { ring, index } => {
173 write!(f, "ring {ring} doubles back on itself at vertex {index}")
174 }
175 Self::MisnestedRing { ring, winding } => {
176 write!(
177 f,
178 "ring {ring} borders a region of winding {winding}, not 0 or 1"
179 )
180 }
181 Self::EmptyDomain => write!(f, "the rings enclose no triangle"),
182 }
183 }
184}
185
186impl core::error::Error for TriangulationError {}
187
188/// An input point merged into an exactly coincident one.
189///
190/// Two input points at the same position are one vertex of the
191/// triangulation: the lowest input index at that position is kept, and the
192/// others are reported here. No triangle uses a merged index.
193#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
194#[non_exhaustive]
195pub struct MergedPoint {
196 /// The input index that was merged.
197 pub input: u32,
198 /// The input index that stands for it in the triangles: the lowest
199 /// index at the same position.
200 pub kept: u32,
201}
202
203/// A planar triangulation over a point set, honouring constraint edges.
204#[derive(Debug, Clone)]
205pub struct Triangulation {
206 pub(crate) points: Vec<Point2>,
207 /// Three vertex indices per triangle, counter-clockwise.
208 pub(crate) triangles: Vec<u32>,
209 /// Twin halfedge per halfedge, or [`NO_HALFEDGE`].
210 pub(crate) halfedges: Vec<u32>,
211 /// Constraint edges, sorted, as vertex index pairs.
212 pub(crate) constraints: Vec<Constraint>,
213 /// Coincident input points merged into a kept one, by input index.
214 pub(crate) merged: Vec<MergedPoint>,
215 /// Kept vertices that no triangle uses, ascending; set by the domain
216 /// filter.
217 pub(crate) outside: Vec<u32>,
218 /// The rings the triangles were filtered by, so refinement can filter
219 /// again; `None` for a hull triangulation.
220 pub(crate) domain: Option<Vec<Ring>>,
221}
222
223impl Triangulation {
224 /// The triangle list, three counter-clockwise vertex indices each.
225 ///
226 /// Indices are into [`points`](Self::points); an input point merged
227 /// into a coincident one (see [`merged_points`](Self::merged_points))
228 /// appears under the kept index.
229 #[must_use]
230 pub fn triangles(&self) -> &[u32] {
231 &self.triangles
232 }
233
234 /// The vertex positions, including any Steiner points appended by
235 /// refinement.
236 #[must_use]
237 pub fn points(&self) -> &[Point2] {
238 &self.points
239 }
240
241 /// Number of triangles.
242 #[must_use]
243 pub fn triangle_count(&self) -> usize {
244 self.triangles.len() / 3
245 }
246
247 /// The constraint edges this triangulation was built to honour, between
248 /// kept vertices: an endpoint that was merged into a coincident point
249 /// is replaced by the kept index. A constraint through input vertices
250 /// is listed as the pieces between them, each an edge of the output.
251 /// For a domain triangulation, pieces outside the domain are dropped.
252 #[must_use]
253 pub fn constraints(&self) -> &[Constraint] {
254 &self.constraints
255 }
256
257 /// The input points merged into an exactly coincident point, in
258 /// ascending input order; empty when every input point is distinct.
259 ///
260 /// Every input index not listed is its own vertex. With this list the
261 /// merge is lossless: a caller can map each of its indices to the
262 /// vertex that carries it.
263 #[must_use]
264 pub fn merged_points(&self) -> &[MergedPoint] {
265 &self.merged
266 }
267
268 /// The kept vertices that no triangle uses, ascending: the points of a
269 /// domain triangulation that lie outside the domain (or inside a hole)
270 /// and were dropped, and ring vertices that bound no domain triangle
271 /// (an outline corner covered by a hole). Empty for a hull triangulation, where every kept
272 /// point is a corner. A merged point is not listed; see
273 /// [`merged_points`](Self::merged_points).
274 #[must_use]
275 pub fn outside_points(&self) -> &[u32] {
276 &self.outside
277 }
278
279 /// Whether `edge` is a constraint.
280 pub(crate) fn is_constrained(&self, a: u32, b: u32) -> bool {
281 self.constraints
282 .binary_search(&Constraint::new(a, b))
283 .is_ok()
284 }
285}