honeycomb_kernels/triangulation/
ear_clipping.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
use crate::triangulation::{
    check_requirements, crossp_from_verts, fetch_face_vertices, TriangulateError,
};
use honeycomb_core::cmap::{CMap2, DartIdType, FaceIdType, Orbit2, OrbitPolicy};
use honeycomb_core::geometry::CoordsFloat;

#[allow(clippy::missing_panics_doc)]
/// Triangulates a face using the ear clipping method.
///
/// This function triangulates a cell (face) of a 2D combinatorial map by iteratively
/// clipping ears (triangles) from the polygon until only a single triangle remains.
///
/// Note that:
/// - the function assumes that the polygon is simple (no self-intersections or holes) and that the
///   interior is lcoated on the LEFT SIDE of the cross-product.
/// - the implementation might need adjustments for parallel operations or when working with
///   identifiers not greater than existing ones.
///
/// # Arguments
///
/// - `cmap: &mut CMap2` - A mutable reference to the modified `CMap2`.
/// - `face_id: FaceIdentifier` - Identifier of the face to triangulate within the map.
/// - `new_darts: &[DartIdentifier]` - Identifiers of pre-allocated darts for the new edges;
///   the slice length should match the expected number of edges created by the triangulation. For
///   an `n`-sided polygon, the number of created edge is `n-3`, so the number of dart is `(n-3)*2`.
///
/// # Behavior
///
/// - The function begins by checking if the face has 3 or fewer vertices, in which case
///   it's already triangulated or cannot be further processed.
/// - It ensures that the number of new darts provided matches the triangulation requirement.
/// - Iteratively finds an 'ear' of the polygon, where an ear is defined by three consecutive
///   vertices where the triangle formed by these vertices is inside the original polygon.
/// - Clips this ear by updating the combinatorial map's structure, effectively removing one
///   vertex from the polygon per iteration.
/// - Updates the list of darts and vertices accordingly after each ear clip.
/// - Continues until the polygon is reduced to a triangle.
///
/// # Errors
///
/// This function will return an error if the face wasn't triangulated. There can be multiple
/// reason for this:
/// - The face is incompatible with the operation (made of 1, 2 or 3 vertices)
/// - The number of pre-allocated darts did not match the expected number (see [#arguments])
/// - The face contains one or more undefined vertices
/// - The face does not contain an ear
///
/// Note that in all cases except the last, the face will remain the same as it was before the
/// function call.
///
/// Because the ear clipping algorithm works iteratively, the face may be modified a few times
/// before reaching a state where no ear can be found. Note, however, that this cannot occur if
/// the face satisfies requirements mentionned above because of the [Two ears theorem][TET].
///
/// [TET]: https://en.wikipedia.org/wiki/Two_ears_theorem
pub fn process_cell<T: CoordsFloat>(
    cmap: &mut CMap2<T>,
    face_id: FaceIdType,
    new_darts: &[DartIdType],
) -> Result<(), TriangulateError> {
    // fetch darts using a custom orbit so that they're ordered
    let mut darts: Vec<_> =
        Orbit2::new(cmap, OrbitPolicy::Custom(&[1]), face_id as DartIdType).collect();
    let mut n = darts.len();

    // early checks - check # of darts & face size
    check_requirements(n, new_darts.len())?;

    // get associated vertices - check for undefined vertices
    let mut vertices = fetch_face_vertices(cmap, &darts)?;

    let mut ndart_id = new_darts[0];
    while n > 3 {
        let Some(ear) = (0..n).find(|idx| {
            // we're checking whether ABC is an ear or not
            let v1 = &vertices[*idx]; // A
            let v2 = &vertices[(*idx + 1) % n]; // B
            let v3 = &vertices[(*idx + 2) % n]; // C

            // we assume the interior of the polygon is on the left side
            let is_inside = {
                let tmp = crossp_from_verts(v1, v2, v3);
                tmp > T::epsilon()
            };

            let no_overlap = vertices
                .iter()
                .filter(|v| (**v != *v1) && (**v != *v2) && (**v != *v3))
                .all(|v| {
                    let sig12v = crossp_from_verts(v1, v2, v);
                    let sig23v = crossp_from_verts(v2, v3, v);
                    let sig31v = crossp_from_verts(v3, v1, v);

                    let has_pos =
                        (sig12v > T::zero()) || (sig23v > T::zero()) || (sig31v > T::zero());
                    let has_neg =
                        (sig12v < T::zero()) || (sig23v < T::zero()) || (sig31v < T::zero());

                    has_pos && has_neg
                });
            is_inside && no_overlap
        }) else {
            // println!("W: could not find ear to triangulate cell - skipping face {face_id}");
            return Err(TriangulateError::NoEar);
        };

        // edit cell; we use the nd1/nd2 edge to create a triangle from the ear
        // nd1 is on the side of the tri, nd2 on the side of the rest of the cell
        let d_ear1 = darts[ear];
        let d_ear2 = darts[(ear + 1) % n];
        let b0_d_ear1 = cmap.beta::<0>(d_ear1);
        let b1_d_ear2 = cmap.beta::<1>(d_ear2);
        let nd1 = ndart_id;
        let nd2 = ndart_id + 1;
        ndart_id += 2;
        // FIXME: using link methods only works if new identifiers are greater than all existing
        // FIXME: using sew methods in parallel could crash bc of the panic when no vertex defined
        cmap.force_one_unlink(b0_d_ear1);
        cmap.force_one_unlink(d_ear2);
        cmap.force_one_link(d_ear2, nd1);
        cmap.force_one_link(nd1, d_ear1);
        cmap.force_one_link(b0_d_ear1, nd2);
        cmap.force_one_link(nd2, b1_d_ear2);
        cmap.force_two_link(nd1, nd2);

        // edit existing vectors
        darts.remove((ear + 1) % n);
        darts.push(nd2);
        darts.swap_remove(ear);
        vertices.remove((ear + 1) % n);

        // update n
        n = Orbit2::new(cmap, OrbitPolicy::Custom(&[1]), nd2).count();
    }

    Ok(())
}