honeycomb_kernels/triangulation/ear_clipping.rs
1use honeycomb_core::cmap::{CMap2, DartIdType, FaceIdType, Orbit2, OrbitPolicy};
2use honeycomb_core::geometry::CoordsFloat;
3
4use crate::triangulation::{
5 check_requirements, crossp_from_verts, fetch_face_vertices, TriangulateError,
6};
7
8#[allow(clippy::missing_panics_doc)]
9/// Triangulates a face using the ear clipping method.
10///
11/// This function triangulates a cell (face) of a 2D combinatorial map by iteratively
12/// clipping ears (triangles) from the polygon until only a single triangle remains.
13///
14/// Note that:
15/// - the function assumes that the polygon is simple (no self-intersections or holes) and that the
16/// interior is lcoated on the LEFT SIDE of the cross-product.
17/// - the implementation might need adjustments for parallel operations or when working with
18/// identifiers not greater than existing ones.
19///
20/// # Arguments
21///
22/// - `cmap: &mut CMap2` - A mutable reference to the modified `CMap2`.
23/// - `face_id: FaceIdentifier` - Identifier of the face to triangulate within the map.
24/// - `new_darts: &[DartIdentifier]` - Identifiers of pre-allocated darts for the new edges;
25/// the slice length should match the expected number of edges created by the triangulation. For
26/// an `n`-sided polygon, the number of created edge is `n-3`, so the number of dart is `(n-3)*2`.
27///
28/// # Behavior
29///
30/// - The function begins by checking if the face has 3 or fewer vertices, in which case
31/// it's already triangulated or cannot be further processed.
32/// - It ensures that the number of new darts provided matches the triangulation requirement.
33/// - Iteratively finds an 'ear' of the polygon, where an ear is defined by three consecutive
34/// vertices where the triangle formed by these vertices is inside the original polygon.
35/// - Clips this ear by updating the combinatorial map's structure, effectively removing one
36/// vertex from the polygon per iteration.
37/// - Updates the list of darts and vertices accordingly after each ear clip.
38/// - Continues until the polygon is reduced to a triangle.
39///
40/// # Errors
41///
42/// This function will return an error if the face wasn't triangulated. There can be multiple
43/// reason for this:
44/// - The face is incompatible with the operation (made of 1, 2 or 3 vertices)
45/// - The number of pre-allocated darts did not match the expected number (see [#arguments])
46/// - The face contains one or more undefined vertices
47/// - The face does not contain an ear
48///
49/// Note that in all cases except the last, the face will remain the same as it was before the
50/// function call.
51///
52/// Because the ear clipping algorithm works iteratively, the face may be modified a few times
53/// before reaching a state where no ear can be found. Note, however, that this cannot occur if
54/// the face satisfies requirements mentionned above because of the [Two ears theorem][TET].
55///
56/// [TET]: https://en.wikipedia.org/wiki/Two_ears_theorem
57pub fn process_cell<T: CoordsFloat>(
58 cmap: &mut CMap2<T>,
59 face_id: FaceIdType,
60 new_darts: &[DartIdType],
61) -> Result<(), TriangulateError> {
62 // fetch darts using a custom orbit so that they're ordered
63 let mut darts: Vec<_> =
64 Orbit2::new(cmap, OrbitPolicy::Custom(&[1]), face_id as DartIdType).collect();
65 let mut n = darts.len();
66
67 // early checks - check # of darts & face size
68 check_requirements(n, new_darts.len())?;
69
70 // get associated vertices - check for undefined vertices
71 let mut vertices = fetch_face_vertices(cmap, &darts)?;
72
73 let mut ndart_id = new_darts[0];
74 while n > 3 {
75 let Some(ear) = (0..n).find(|idx| {
76 // we're checking whether ABC is an ear or not
77 let v1 = &vertices[*idx]; // A
78 let v2 = &vertices[(*idx + 1) % n]; // B
79 let v3 = &vertices[(*idx + 2) % n]; // C
80
81 // we assume the interior of the polygon is on the left side
82 let is_inside = {
83 let tmp = crossp_from_verts(v1, v2, v3);
84 tmp > T::epsilon()
85 };
86
87 let no_overlap = vertices
88 .iter()
89 .filter(|v| (**v != *v1) && (**v != *v2) && (**v != *v3))
90 .all(|v| {
91 let sig12v = crossp_from_verts(v1, v2, v);
92 let sig23v = crossp_from_verts(v2, v3, v);
93 let sig31v = crossp_from_verts(v3, v1, v);
94
95 let has_pos =
96 (sig12v > T::zero()) || (sig23v > T::zero()) || (sig31v > T::zero());
97 let has_neg =
98 (sig12v < T::zero()) || (sig23v < T::zero()) || (sig31v < T::zero());
99
100 has_pos && has_neg
101 });
102 is_inside && no_overlap
103 }) else {
104 // println!("W: could not find ear to triangulate cell - skipping face {face_id}");
105 return Err(TriangulateError::NoEar);
106 };
107
108 // edit cell; we use the nd1/nd2 edge to create a triangle from the ear
109 // nd1 is on the side of the tri, nd2 on the side of the rest of the cell
110 let d_ear1 = darts[ear];
111 let d_ear2 = darts[(ear + 1) % n];
112 let b0_d_ear1 = cmap.beta::<0>(d_ear1);
113 let b1_d_ear2 = cmap.beta::<1>(d_ear2);
114 let nd1 = ndart_id;
115 let nd2 = ndart_id + 1;
116 ndart_id += 2;
117 // FIXME: using link methods only works if new identifiers are greater than all existing
118 // FIXME: using sew methods in parallel could crash bc of the panic when no vertex defined
119 cmap.force_unlink::<1>(b0_d_ear1).unwrap();
120 cmap.force_unlink::<1>(d_ear2).unwrap();
121 cmap.force_link::<1>(d_ear2, nd1).unwrap();
122 cmap.force_link::<1>(nd1, d_ear1).unwrap();
123 cmap.force_link::<1>(b0_d_ear1, nd2).unwrap();
124 cmap.force_link::<1>(nd2, b1_d_ear2).unwrap();
125 cmap.force_link::<2>(nd1, nd2).unwrap();
126
127 // edit existing vectors
128 darts.remove((ear + 1) % n);
129 darts.push(nd2);
130 darts.swap_remove(ear);
131 vertices.remove((ear + 1) % n);
132
133 // update n
134 n = Orbit2::new(cmap, OrbitPolicy::Custom(&[1]), nd2).count();
135 }
136
137 Ok(())
138}