geo/algorithm/triangulate_earcut.rs
1use crate::{coord, CoordFloat, CoordsIter, Polygon, Triangle};
2
3/// Triangulate polygons using an [ear-cutting algorithm](https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf).
4///
5/// Requires the `"earcutr"` feature, which is enabled by default.
6pub trait TriangulateEarcut<T: CoordFloat> {
7 /// # Examples
8 ///
9 /// ```
10 /// use geo::{coord, polygon, Triangle, TriangulateEarcut};
11 ///
12 /// let square_polygon = polygon![
13 /// (x: 0., y: 0.), // SW
14 /// (x: 10., y: 0.), // SE
15 /// (x: 10., y: 10.), // NE
16 /// (x: 0., y: 10.), // NW
17 /// (x: 0., y: 0.), // SW
18 /// ];
19 ///
20 /// let triangles = square_polygon.earcut_triangles();
21 ///
22 /// assert_eq!(
23 /// vec![
24 /// Triangle(
25 /// coord! { x: 0., y: 10. }, // NW
26 /// coord! { x: 10., y: 10. }, // NE
27 /// coord! { x: 10., y: 0. }, // SE
28 /// ),
29 /// Triangle(
30 /// coord! { x: 10., y: 0. }, // SE
31 /// coord! { x: 0., y: 0. }, // SW
32 /// coord! { x: 0., y: 10. }, // NW
33 /// ),
34 /// ],
35 /// triangles,
36 /// );
37 /// ```
38 fn earcut_triangles(&self) -> Vec<Triangle<T>> {
39 self.earcut_triangles_iter().collect()
40 }
41
42 /// # Examples
43 ///
44 /// ```
45 /// use geo::{coord, polygon, Triangle, TriangulateEarcut};
46 ///
47 /// let square_polygon = polygon![
48 /// (x: 0., y: 0.), // SW
49 /// (x: 10., y: 0.), // SE
50 /// (x: 10., y: 10.), // NE
51 /// (x: 0., y: 10.), // NW
52 /// (x: 0., y: 0.), // SW
53 /// ];
54 ///
55 /// let mut triangles_iter = square_polygon.earcut_triangles_iter();
56 ///
57 /// assert_eq!(
58 /// Some(Triangle(
59 /// coord! { x: 0., y: 10. }, // NW
60 /// coord! { x: 10., y: 10. }, // NE
61 /// coord! { x: 10., y: 0. }, // SE
62 /// )),
63 /// triangles_iter.next(),
64 /// );
65 ///
66 /// assert_eq!(
67 /// Some(Triangle(
68 /// coord! { x: 10., y: 0. }, // SE
69 /// coord! { x: 0., y: 0. }, // SW
70 /// coord! { x: 0., y: 10. }, // NW
71 /// )),
72 /// triangles_iter.next(),
73 /// );
74 ///
75 /// assert!(triangles_iter.next().is_none());
76 /// ```
77 fn earcut_triangles_iter(&self) -> Iter<T> {
78 Iter(self.earcut_triangles_raw())
79 }
80
81 /// Return the raw result from the `earcutr` library: a one-dimensional vector of polygon
82 /// vertices (in XY order), and the indices of the triangles within the vertices vector. This
83 /// method is less ergonomic than the `earcut_triangles` and `earcut_triangles_iter`
84 /// methods, but can be helpful when working in graphics contexts that expect flat vectors of
85 /// data.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use geo::{coord, polygon, Triangle, TriangulateEarcut};
91 /// use geo::triangulate_earcut::RawTriangulation;
92 ///
93 /// let square_polygon = polygon![
94 /// (x: 0., y: 0.), // SW
95 /// (x: 10., y: 0.), // SE
96 /// (x: 10., y: 10.), // NE
97 /// (x: 0., y: 10.), // NW
98 /// (x: 0., y: 0.), // SW
99 /// ];
100 ///
101 /// let mut triangles_raw = square_polygon.earcut_triangles_raw();
102 ///
103 /// assert_eq!(
104 /// RawTriangulation {
105 /// vertices: vec![
106 /// 0., 0., // SW
107 /// 10., 0., // SE
108 /// 10., 10., // NE
109 /// 0., 10., // NW
110 /// 0., 0., // SW
111 /// ],
112 /// triangle_indices: vec![
113 /// 3, 0, 1, // NW-SW-SE
114 /// 1, 2, 3, // SE-NE-NW
115 /// ],
116 /// },
117 /// triangles_raw,
118 /// );
119 /// ```
120 fn earcut_triangles_raw(&self) -> RawTriangulation<T>;
121}
122
123impl<T: CoordFloat> TriangulateEarcut<T> for Polygon<T> {
124 fn earcut_triangles_raw(&self) -> RawTriangulation<T> {
125 let input = polygon_to_earcutr_input(self);
126 let triangle_indices =
127 earcutr::earcut(&input.vertices, &input.interior_indexes, 2).unwrap();
128 RawTriangulation {
129 vertices: input.vertices,
130 triangle_indices,
131 }
132 }
133}
134
135/// The raw result of triangulating a polygon from `earcutr`.
136#[derive(Debug, PartialEq, Clone)]
137pub struct RawTriangulation<T: CoordFloat> {
138 /// Flattened one-dimensional vector of polygon vertices (in XY order).
139 pub vertices: Vec<T>,
140
141 /// Indices of the triangles within the vertices vector.
142 pub triangle_indices: Vec<usize>,
143}
144
145#[derive(Debug)]
146pub struct Iter<T: CoordFloat>(RawTriangulation<T>);
147
148impl<T: CoordFloat> Iterator for Iter<T> {
149 type Item = Triangle<T>;
150
151 fn next(&mut self) -> Option<Self::Item> {
152 let triangle_index_1 = self.0.triangle_indices.pop()?;
153 let triangle_index_2 = self.0.triangle_indices.pop()?;
154 let triangle_index_3 = self.0.triangle_indices.pop()?;
155 Some(Triangle(
156 self.triangle_index_to_coord(triangle_index_1),
157 self.triangle_index_to_coord(triangle_index_2),
158 self.triangle_index_to_coord(triangle_index_3),
159 ))
160 }
161}
162
163impl<T: CoordFloat> Iter<T> {
164 fn triangle_index_to_coord(&self, triangle_index: usize) -> crate::Coord<T> {
165 coord! {
166 x: self.0.vertices[triangle_index * 2],
167 y: self.0.vertices[triangle_index * 2 + 1],
168 }
169 }
170}
171
172struct EarcutrInput<T: CoordFloat> {
173 pub vertices: Vec<T>,
174 pub interior_indexes: Vec<usize>,
175}
176
177fn polygon_to_earcutr_input<T: CoordFloat>(polygon: &crate::Polygon<T>) -> EarcutrInput<T> {
178 let mut vertices = Vec::with_capacity(polygon.coords_count() * 2);
179 let mut interior_indexes = Vec::with_capacity(polygon.interiors().len());
180 debug_assert!(polygon.exterior().0.len() >= 4);
181
182 flat_line_string_coords_2(polygon.exterior(), &mut vertices);
183
184 for interior in polygon.interiors() {
185 debug_assert!(interior.0.len() >= 4);
186 interior_indexes.push(vertices.len() / 2);
187 flat_line_string_coords_2(interior, &mut vertices);
188 }
189
190 EarcutrInput {
191 vertices,
192 interior_indexes,
193 }
194}
195
196fn flat_line_string_coords_2<T: CoordFloat>(
197 line_string: &crate::LineString<T>,
198 vertices: &mut Vec<T>,
199) {
200 for coord in &line_string.0 {
201 vertices.push(coord.x);
202 vertices.push(coord.y);
203 }
204}
205
206#[cfg(test)]
207mod test {
208 use super::TriangulateEarcut;
209 use crate::{coord, polygon, Triangle};
210
211 #[test]
212 fn test_triangle() {
213 let triangle_polygon = polygon![
214 (x: 0., y: 0.),
215 (x: 10., y: 0.),
216 (x: 10., y: 10.),
217 (x: 0., y: 0.),
218 ];
219
220 let triangles = triangle_polygon.earcut_triangles();
221
222 assert_eq!(
223 &[Triangle(
224 coord! { x: 10.0, y: 0.0 },
225 coord! { x: 0.0, y: 0.0 },
226 coord! { x: 10.0, y: 10.0 },
227 ),][..],
228 triangles,
229 );
230 }
231
232 #[test]
233 fn test_square() {
234 let square_polygon = polygon![
235 (x: 0., y: 0.),
236 (x: 10., y: 0.),
237 (x: 10., y: 10.),
238 (x: 0., y: 10.),
239 (x: 0., y: 0.),
240 ];
241
242 let mut triangles = square_polygon.earcut_triangles();
243 triangles.sort_by(|t1, t2| t1.1.x.partial_cmp(&t2.2.x).unwrap());
244
245 assert_eq!(
246 &[
247 Triangle(
248 coord! { x: 10.0, y: 0.0 },
249 coord! { x: 0.0, y: 0.0 },
250 coord! { x: 0.0, y: 10.0 },
251 ),
252 Triangle(
253 coord! { x: 0.0, y: 10.0 },
254 coord! { x: 10.0, y: 10.0 },
255 coord! { x: 10.0, y: 0.0 },
256 ),
257 ][..],
258 triangles,
259 );
260 }
261}