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 -- the triangulation is
12//! rebuilt rather than edited, so compactness and cache locality win.
13//!
14//! Vertices 0..n are the caller's points. Three extra vertices form a super
15//! triangle large enough to contain them all; they are removed at the end,
16//! together with every triangle that touches them.
17
18use axiolid_core::Point2;
19
20use crate::Constraint;
21
22/// Sentinel for "no neighbour across this halfedge".
23pub(crate) const NO_HALFEDGE: u32 = u32::MAX;
24
25/// Why a triangulation could not be produced.
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27#[non_exhaustive]
28pub enum TriangulationError {
29    /// Fewer than three points were supplied, so no triangle exists.
30    TooFewPoints,
31    /// Every input point is collinear, so the triangulation has zero area.
32    ///
33    /// Reported rather than returning an empty triangulation: a caller that
34    /// asked to triangulate a degenerate polygon has a bug upstream, and an
35    /// empty result would hide it.
36    AllPointsCollinear,
37    /// A vertex could not be placed in any triangle during insertion.
38    ///
39    /// Indicates a corrupted adjacency rather than bad input. Reported so a
40    /// missing vertex surfaces as an error instead of as a silent hole in an
41    /// otherwise valid-looking mesh.
42    VertexUnplaceable {
43        /// Index of the vertex that could not be placed.
44        index: u32,
45    },
46    /// A constraint referenced a vertex index that does not exist.
47    ConstraintOutOfRange {
48        /// The offending index.
49        index: u32,
50    },
51    /// A constraint could not be recovered after insertion.
52    ///
53    /// Only reachable when two constraints cross: an edge cannot survive if
54    /// another required edge passes through it. The crossing point would have
55    /// to be inserted as a vertex, which changes the caller's input, so this
56    /// is reported instead of silently repaired.
57    CrossingConstraints {
58        /// First endpoint of the constraint that could not be recovered.
59        a: u32,
60        /// Second endpoint.
61        b: u32,
62    },
63}
64
65impl core::fmt::Display for TriangulationError {
66    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
67        match self {
68            Self::TooFewPoints => write!(f, "a triangulation needs at least three points"),
69            Self::AllPointsCollinear => write!(f, "every input point is collinear"),
70            Self::VertexUnplaceable { index } => {
71                write!(f, "vertex {index} could not be placed in any triangle")
72            }
73            Self::ConstraintOutOfRange { index } => {
74                write!(f, "constraint references out-of-range vertex {index}")
75            }
76            Self::CrossingConstraints { a, b } => {
77                write!(f, "constraint ({a}, {b}) crosses another constraint")
78            }
79        }
80    }
81}
82
83impl core::error::Error for TriangulationError {}
84
85/// A planar triangulation over a point set, honouring constraint edges.
86#[derive(Debug, Clone)]
87pub struct Triangulation {
88    pub(crate) points: Vec<Point2>,
89    /// Three vertex indices per triangle, counter-clockwise.
90    pub(crate) triangles: Vec<u32>,
91    /// Twin halfedge per halfedge, or [`NO_HALFEDGE`].
92    pub(crate) halfedges: Vec<u32>,
93    /// Constraint edges, sorted, as vertex index pairs.
94    pub(crate) constraints: Vec<Constraint>,
95}
96
97impl Triangulation {
98    /// The triangle list, three counter-clockwise vertex indices each.
99    #[must_use]
100    pub fn triangles(&self) -> &[u32] {
101        &self.triangles
102    }
103
104    /// The vertex positions, including any Steiner points appended by
105    /// refinement.
106    #[must_use]
107    pub fn points(&self) -> &[Point2] {
108        &self.points
109    }
110
111    /// Number of triangles.
112    #[must_use]
113    pub fn triangle_count(&self) -> usize {
114        self.triangles.len() / 3
115    }
116
117    /// The constraint edges this triangulation was built to honour.
118    #[must_use]
119    pub fn constraints(&self) -> &[Constraint] {
120        &self.constraints
121    }
122
123    /// Whether `edge` is a constraint.
124    pub(crate) fn is_constrained(&self, a: u32, b: u32) -> bool {
125        self.constraints
126            .binary_search(&Constraint::new(a, b))
127            .is_ok()
128    }
129}
axiolid_triangulate/mesh.rs

axiolid_triangulate/
mesh.rs
