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::{earclip_cell_countercw, earclip_cell_cw};
18pub use fan::process_cell as fan_cell;
19pub use fan::process_convex_cell as fan_convex_cell;
20
21use honeycomb_core::cmap::SewError;
22use thiserror::Error;
23
24/// Error-modeling enum for triangulation routines.
25#[derive(Error, Debug, PartialEq, Eq)]
26pub enum TriangulateError {
27    /// The face to triangulate is already a triangle.
28    #[error("face is already a triangle")]
29    AlreadyTriangulated,
30    /// The face has no ear to use for triangulation using the ear clipping method.
31    #[error("no ear found in the polygon to triangulate")]
32    NoEar,
33    /// The face is not fannable, i.e. there is no "star" vertex.
34    #[error("no star in the polygon to triangulate")]
35    NonFannable,
36    /// The number of darts passed to create the new segments is too low. The `usize` value
37    /// is the number of missing darts.
38    #[error("not enough darts were passed to the triangulation function - missing `{0}`")]
39    NotEnoughDarts(usize),
40    /// The number of darts passed to create the new segments is too high. The `usize` value
41    /// is the number of excess darts.
42    #[error("too many darts were passed to the triangulation function - missing `{0}`")]
43    TooManyDarts(usize),
44    /// The face is not fit for triangulation. The `String` contains information about the reason.
45    #[error("face isn't defined correctly - {0}")]
46    UndefinedFace(&'static str),
47    /// An internal sew or link failed
48    #[error("an internal operation failed - {0}")]
49    OpFailed(#[from] SewError),
50}
51
52#[allow(clippy::missing_errors_doc)]
53/// Checks if a face meets the requirements for triangulation.
54///
55/// This function performs several checks on a face before it can be triangulated:
56/// 1. Ensures the face has at least 3 vertices.
57/// 2. Verifies that the face is not already triangulated.
58/// 3. Confirms that the correct number of darts have been allocated for triangulation.
59///
60/// # Arguments
61///
62/// * `n_darts_face` - The number of darts in the face to be triangulated.
63/// * `n_darts_allocated` - The number of darts allocated for the triangulation process.
64/// * `face_id` - The identifier of the face being checked.
65///
66/// # Return / Errors
67///
68/// This function can return:
69/// - `Ok(())` if all checks pass and the face is ready for triangulation.
70/// - `Err(TriangulateError)` if any check fails, with a specific error describing the issue.
71///
72/// A failed check can result in the following errors:
73/// - `TriangulateError::UndefinedFace` - If the face has fewer than 3 vertices.
74/// - `TriangulateError::AlreadyTriangulated` - If the face already has exactly 3 vertices.
75/// - `TriangulateError::NotEnoughDarts` - If there aren't enough darts allocated for triangulation.
76/// - `TriangulateError::TooManyDarts` - If there are too many darts allocated for triangulation.
77#[allow(
78    clippy::cast_possible_wrap,
79    clippy::cast_sign_loss,
80    clippy::cast_abs_to_unsigned
81)]
82pub fn check_requirements(
83    n_darts_face: usize,
84    n_darts_allocated: usize,
85) -> Result<(), TriangulateError> {
86    match n_darts_face {
87        1 | 2 => {
88            return Err(TriangulateError::UndefinedFace("less than 3 vertices"));
89        }
90        3 => {
91            return Err(TriangulateError::AlreadyTriangulated);
92        }
93        _ => {}
94    }
95
96    // check the value of n_allocated - n_expected
97    match n_darts_allocated as isize - (n_darts_face as isize - 3) * 2 {
98        diff @ ..0 => {
99            return Err(TriangulateError::NotEnoughDarts(diff.abs() as usize));
100        }
101        0 => {}
102        diff @ 1.. => {
103            return Err(TriangulateError::TooManyDarts(diff as usize));
104        }
105    }
106
107    Ok(())
108}
109
110#[cfg(test)]
111mod tests;
honeycomb_kernels/triangulation/mod.rs

honeycomb_kernels/triangulation/
mod.rs
