honeycomb_kernels/triangulation/
mod.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//! Polygon triangulation functions
//!
//! This module contains implementations of simple polygon triangulation methods. These are not
//! meshing functions; our goal with these is to cut existing cells of an irregular mesh into
//! triangular cells.
//!
//! With consideration to the above, we implement two polygon triangulation methods:
//! - fanning -- two versions of this are implemented:
//!     - a defensive one where the function actively search for a valid vertex to fan from
//!     - a specific one which assume the cell is convex; it fans the polygon from its first vertex
//! - ear clipping -- this method isn't algorithmically efficient, but (a) we operate on small
//!   cells, and (b) it covers our needs (non-fannable polygons without holes)

// ------ MODULE DECLARATIONS

mod ear_clipping;
mod fan;

// ------ PUBLIC RE-EXPORTS

pub use ear_clipping::process_cell as earclip_cell;
pub use fan::process_cell as fan_cell;
pub use fan::process_convex_cell as fan_convex_cell;

// ------ CONTENT

use honeycomb_core::cmap::{CMap2, DartIdType};
use honeycomb_core::geometry::{CoordsFloat, Vertex2};
use thiserror::Error;

/// Error-modeling enum for triangulation routines.
#[derive(Error, Debug, PartialEq, Eq)]
pub enum TriangulateError {
    /// The face to triangulate is already a triangle.
    #[error("face is already a triangle")]
    AlreadyTriangulated,
    /// The face has no ear to use for triangulation using the ear clipping method.
    #[error("no ear found in the polygon to triangulate")]
    NoEar,
    /// The face is not fannable, i.e. there is no "star" vertex.
    #[error("no star in the polygon to triangulate")]
    NonFannable,
    /// The number of darts passed to create the new segments is too low. The `usize` value
    /// is the number of missing darts.
    #[error("not enough darts were passed to the triangulation function - missing `{0}`")]
    NotEnoughDarts(usize),
    /// The number of darts passed to create the new segments is too high. The `usize` value
    /// is the number of excess darts.
    #[error("too many darts were passed to the triangulation function - missing `{0}`")]
    TooManyDarts(usize),
    /// The face is not fit for triangulation. The `String` contains information about the reason.
    #[error("face isn't defined correctly - {0}")]
    UndefinedFace(&'static str),
}

#[allow(clippy::missing_errors_doc)]
/// Checks if a face meets the requirements for triangulation.
///
/// This function performs several checks on a face before it can be triangulated:
/// 1. Ensures the face has at least 3 vertices.
/// 2. Verifies that the face is not already triangulated.
/// 3. Confirms that the correct number of darts have been allocated for triangulation.
///
/// # Arguments
///
/// * `n_darts_face` - The number of darts in the face to be triangulated.
/// * `n_darts_allocated` - The number of darts allocated for the triangulation process.
/// * `face_id` - The identifier of the face being checked.
///
/// # Return / Errors
///
/// This function can return:
/// - `Ok(())` if all checks pass and the face is ready for triangulation.
/// - `Err(TriangulateError)` if any check fails, with a specific error describing the issue.
///
/// A failed check can result in the following errors:
/// - `TriangulateError::UndefinedFace` - If the face has fewer than 3 vertices.
/// - `TriangulateError::AlreadyTriangulated` - If the face already has exactly 3 vertices.
/// - `TriangulateError::NotEnoughDarts` - If there aren't enough darts allocated for triangulation.
/// - `TriangulateError::TooManyDarts` - If there are too many darts allocated for triangulation.
#[allow(
    clippy::cast_possible_wrap,
    clippy::cast_sign_loss,
    clippy::cast_abs_to_unsigned
)]
pub fn check_requirements(
    n_darts_face: usize,
    n_darts_allocated: usize,
) -> Result<(), TriangulateError> {
    match n_darts_face {
        1 | 2 => {
            return Err(TriangulateError::UndefinedFace("less than 3 vertices"));
        }
        3 => {
            return Err(TriangulateError::AlreadyTriangulated);
        }
        _ => {}
    }

    // check the value of n_allocated - n_expected
    match n_darts_allocated as isize - (n_darts_face as isize - 3) * 2 {
        diff @ ..0 => {
            return Err(TriangulateError::NotEnoughDarts(diff.abs() as usize));
        }
        0 => {}
        diff @ 1.. => {
            return Err(TriangulateError::TooManyDarts(diff as usize));
        }
    }

    Ok(())
}

fn fetch_face_vertices<T: CoordsFloat>(
    cmap: &CMap2<T>,
    darts: &[DartIdType],
) -> Result<Vec<Vertex2<T>>, TriangulateError> {
    let tmp = darts
        .iter()
        .map(|dart_id| cmap.force_read_vertex(cmap.vertex_id(*dart_id)));
    if tmp.clone().any(|v| v.is_none()) {
        Err(TriangulateError::UndefinedFace(
            "one or more undefined vertices",
        ))
    } else {
        Ok(tmp.map(Option::unwrap).collect()) // safe unwrap due to if
    }
}

/// Compute the cross product: `v1v2 x v2v3`.
fn crossp_from_verts<T: CoordsFloat>(v1: &Vertex2<T>, v2: &Vertex2<T>, v3: &Vertex2<T>) -> T {
    (v2.x() - v1.x()) * (v3.y() - v2.y()) - (v2.y() - v1.y()) * (v3.x() - v2.x())
}

// ------ TESTS

#[cfg(test)]
mod tests;