honeycomb_kernels/triangulation/
mod.rs

1//! Polygon triangulation functions
2//!
3//! This module contains implementations of simple polygon triangulation methods. These are not
4//! meshing functions; our goal with these is to cut existing cells of an irregular mesh into
5//! triangular cells.
6//!
7//! With consideration to the above, we implement two polygon triangulation methods:
8//! - fanning -- two versions of this are implemented:
9//!     - a defensive one where the function actively search for a valid vertex to fan from
10//!     - a specific one which assume the cell is convex; it fans the polygon from its first vertex
11//! - ear clipping -- this method isn't algorithmically efficient, but (a) we operate on small
12//!   cells, and (b) it covers our needs (non-fannable polygons without holes)
13
14mod ear_clipping;
15mod fan;
16
17pub use ear_clipping::process_cell as earclip_cell;
18pub use fan::process_cell as fan_cell;
19pub use fan::process_convex_cell as fan_convex_cell;
20
21use honeycomb_core::cmap::{CMap2, DartIdType};
22use honeycomb_core::geometry::{CoordsFloat, Vertex2};
23use thiserror::Error;
24
25/// Error-modeling enum for triangulation routines.
26#[derive(Error, Debug, PartialEq, Eq)]
27pub enum TriangulateError {
28    /// The face to triangulate is already a triangle.
29    #[error("face is already a triangle")]
30    AlreadyTriangulated,
31    /// The face has no ear to use for triangulation using the ear clipping method.
32    #[error("no ear found in the polygon to triangulate")]
33    NoEar,
34    /// The face is not fannable, i.e. there is no "star" vertex.
35    #[error("no star in the polygon to triangulate")]
36    NonFannable,
37    /// The number of darts passed to create the new segments is too low. The `usize` value
38    /// is the number of missing darts.
39    #[error("not enough darts were passed to the triangulation function - missing `{0}`")]
40    NotEnoughDarts(usize),
41    /// The number of darts passed to create the new segments is too high. The `usize` value
42    /// is the number of excess darts.
43    #[error("too many darts were passed to the triangulation function - missing `{0}`")]
44    TooManyDarts(usize),
45    /// The face is not fit for triangulation. The `String` contains information about the reason.
46    #[error("face isn't defined correctly - {0}")]
47    UndefinedFace(&'static str),
48}
49
50#[allow(clippy::missing_errors_doc)]
51/// Checks if a face meets the requirements for triangulation.
52///
53/// This function performs several checks on a face before it can be triangulated:
54/// 1. Ensures the face has at least 3 vertices.
55/// 2. Verifies that the face is not already triangulated.
56/// 3. Confirms that the correct number of darts have been allocated for triangulation.
57///
58/// # Arguments
59///
60/// * `n_darts_face` - The number of darts in the face to be triangulated.
61/// * `n_darts_allocated` - The number of darts allocated for the triangulation process.
62/// * `face_id` - The identifier of the face being checked.
63///
64/// # Return / Errors
65///
66/// This function can return:
67/// - `Ok(())` if all checks pass and the face is ready for triangulation.
68/// - `Err(TriangulateError)` if any check fails, with a specific error describing the issue.
69///
70/// A failed check can result in the following errors:
71/// - `TriangulateError::UndefinedFace` - If the face has fewer than 3 vertices.
72/// - `TriangulateError::AlreadyTriangulated` - If the face already has exactly 3 vertices.
73/// - `TriangulateError::NotEnoughDarts` - If there aren't enough darts allocated for triangulation.
74/// - `TriangulateError::TooManyDarts` - If there are too many darts allocated for triangulation.
75#[allow(
76    clippy::cast_possible_wrap,
77    clippy::cast_sign_loss,
78    clippy::cast_abs_to_unsigned
79)]
80pub fn check_requirements(
81    n_darts_face: usize,
82    n_darts_allocated: usize,
83) -> Result<(), TriangulateError> {
84    match n_darts_face {
85        1 | 2 => {
86            return Err(TriangulateError::UndefinedFace("less than 3 vertices"));
87        }
88        3 => {
89            return Err(TriangulateError::AlreadyTriangulated);
90        }
91        _ => {}
92    }
93
94    // check the value of n_allocated - n_expected
95    match n_darts_allocated as isize - (n_darts_face as isize - 3) * 2 {
96        diff @ ..0 => {
97            return Err(TriangulateError::NotEnoughDarts(diff.abs() as usize));
98        }
99        0 => {}
100        diff @ 1.. => {
101            return Err(TriangulateError::TooManyDarts(diff as usize));
102        }
103    }
104
105    Ok(())
106}
107
108fn fetch_face_vertices<T: CoordsFloat>(
109    cmap: &CMap2<T>,
110    darts: &[DartIdType],
111) -> Result<Vec<Vertex2<T>>, TriangulateError> {
112    let tmp = darts
113        .iter()
114        .map(|dart_id| cmap.force_read_vertex(cmap.vertex_id(*dart_id)));
115    if tmp.clone().any(|v| v.is_none()) {
116        Err(TriangulateError::UndefinedFace(
117            "one or more undefined vertices",
118        ))
119    } else {
120        Ok(tmp.map(Option::unwrap).collect()) // safe unwrap due to if
121    }
122}
123
124/// Compute the cross product: `v1v2 x v2v3`.
125fn crossp_from_verts<T: CoordsFloat>(v1: &Vertex2<T>, v2: &Vertex2<T>, v3: &Vertex2<T>) -> T {
126    (v2.x() - v1.x()) * (v3.y() - v2.y()) - (v2.y() - v1.y()) * (v3.x() - v2.x())
127}
128
129#[cfg(test)]
130mod tests;
honeycomb_kernels/triangulation/mod.rs

honeycomb_kernels/triangulation/
mod.rs
