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 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    /// An internal sew or link failed
49    #[error("an internal operation failed - {0}")]
50    OpFailed(#[from] SewError),
51}
52
53#[allow(clippy::missing_errors_doc)]
54/// Checks if a face meets the requirements for triangulation.
55///
56/// This function performs several checks on a face before it can be triangulated:
57/// 1. Ensures the face has at least 3 vertices.
58/// 2. Verifies that the face is not already triangulated.
59/// 3. Confirms that the correct number of darts have been allocated for triangulation.
60///
61/// # Arguments
62///
63/// * `n_darts_face` - The number of darts in the face to be triangulated.
64/// * `n_darts_allocated` - The number of darts allocated for the triangulation process.
65/// * `face_id` - The identifier of the face being checked.
66///
67/// # Return / Errors
68///
69/// This function can return:
70/// - `Ok(())` if all checks pass and the face is ready for triangulation.
71/// - `Err(TriangulateError)` if any check fails, with a specific error describing the issue.
72///
73/// A failed check can result in the following errors:
74/// - `TriangulateError::UndefinedFace` - If the face has fewer than 3 vertices.
75/// - `TriangulateError::AlreadyTriangulated` - If the face already has exactly 3 vertices.
76/// - `TriangulateError::NotEnoughDarts` - If there aren't enough darts allocated for triangulation.
77/// - `TriangulateError::TooManyDarts` - If there are too many darts allocated for triangulation.
78#[allow(
79    clippy::cast_possible_wrap,
80    clippy::cast_sign_loss,
81    clippy::cast_abs_to_unsigned
82)]
83pub fn check_requirements(
84    n_darts_face: usize,
85    n_darts_allocated: usize,
86) -> Result<(), TriangulateError> {
87    match n_darts_face {
88        1 | 2 => {
89            return Err(TriangulateError::UndefinedFace("less than 3 vertices"));
90        }
91        3 => {
92            return Err(TriangulateError::AlreadyTriangulated);
93        }
94        _ => {}
95    }
96
97    // check the value of n_allocated - n_expected
98    match n_darts_allocated as isize - (n_darts_face as isize - 3) * 2 {
99        diff @ ..0 => {
100            return Err(TriangulateError::NotEnoughDarts(diff.abs() as usize));
101        }
102        0 => {}
103        diff @ 1.. => {
104            return Err(TriangulateError::TooManyDarts(diff as usize));
105        }
106    }
107
108    Ok(())
109}
110
111/// Compute the cross product: `v1v2 x v2v3`.
112fn crossp_from_verts<T: CoordsFloat>(v1: &Vertex2<T>, v2: &Vertex2<T>, v3: &Vertex2<T>) -> T {
113    (v2.x() - v1.x()) * (v3.y() - v2.y()) - (v2.y() - v1.y()) * (v3.x() - v2.x())
114}
115
116#[cfg(test)]
117mod tests;
honeycomb_kernels/triangulation/mod.rs

honeycomb_kernels/triangulation/
mod.rs
