1use crate::{Arc, Ring};
13
14#[derive(Clone, Copy, Default, Debug)]
15pub struct CleanStats {
16 pub dups: u32,
18 pub spikes: u32,
21 pub collinear: u32,
24 pub rings_dropped: u32,
27 pub polys_dropped: u32,
30 pub arcs_dropped: u32,
33}
34
35enum Kind {
36 Spike,
37 Collinear,
38 Keep,
39}
40
41fn classify(p: (i32, i32), q: (i32, i32), r: (i32, i32)) -> Kind {
44 let (ax, ay) = (i64::from(q.0 - p.0), i64::from(q.1 - p.1));
45 let (bx, by) = (i64::from(r.0 - q.0), i64::from(r.1 - q.1));
46 if ax * by != ay * bx {
47 return Kind::Keep;
48 }
49 if ax * bx + ay * by < 0 {
50 Kind::Spike
51 } else {
52 Kind::Collinear
53 }
54}
55
56pub fn clean_arc(arc: &mut Arc<i32>, closed: bool, stats: &mut CleanStats) {
67 if closed {
68 if arc.len() > 1 && arc.first() == arc.last() {
69 arc.pop();
70 }
71 clean_cyclic(arc, stats);
72 if arc.len() > 1 {
73 let first = arc[0];
74 arc.push(first);
75 }
76 } else {
77 clean_open(arc, stats);
78 }
79}
80
81fn clean_open(arc: &mut Arc<i32>, stats: &mut CleanStats) {
82 let mut i = 1;
83 while i < arc.len() {
84 if arc[i] == arc[i - 1] {
85 arc.remove(i);
86 stats.dups += 1;
87 i = i.saturating_sub(1).max(1);
88 continue;
89 }
90 if i + 1 == arc.len() {
91 break;
92 }
93 if arc[i] == arc[i + 1] {
94 arc.remove(i);
95 stats.dups += 1;
96 i = i.saturating_sub(1).max(1);
97 continue;
98 }
99 match classify(arc[i - 1], arc[i], arc[i + 1]) {
100 Kind::Spike => {
101 arc.remove(i);
102 stats.spikes += 1;
103 i = i.saturating_sub(1).max(1);
104 }
105 Kind::Collinear => {
106 arc.remove(i);
107 stats.collinear += 1;
108 i = i.saturating_sub(1).max(1);
109 }
110 Kind::Keep => i += 1,
111 }
112 }
113}
114
115fn clean_cyclic(arc: &mut Arc<i32>, stats: &mut CleanStats) {
116 loop {
117 let mut changed = false;
118 let mut index = 0;
119 while arc.len() >= 3 && index < arc.len() {
120 let len = arc.len();
121 let (previous, current, next) = (
122 arc[(index + len - 1) % len],
123 arc[index],
124 arc[(index + 1) % len],
125 );
126 if current == previous || current == next {
127 arc.remove(index);
128 stats.dups += 1;
129 changed = true;
130 continue;
131 }
132 match classify(previous, current, next) {
133 Kind::Spike => {
134 arc.remove(index);
135 stats.spikes += 1;
136 changed = true;
137 }
138 Kind::Collinear => {
139 arc.remove(index);
140 stats.collinear += 1;
141 changed = true;
142 }
143 Kind::Keep => index += 1,
144 }
145 }
146 if !changed || arc.len() < 3 {
147 break;
148 }
149 }
150 if arc.len() == 2 && arc[0] == arc[1] {
151 arc.pop();
152 stats.dups += 1;
153 }
154}
155
156#[must_use]
159pub fn ring_coords_q(refs: &[u32], arcs: &[Arc<i32>]) -> Ring<i32> {
160 let mut coords: Ring<i32> = Vec::new();
161 for &arc_ref in refs {
162 let (id, reversed) = ((arc_ref >> 1) as usize, (arc_ref & 1) == 1);
163 let mut arc = arcs[id].clone();
164 if reversed {
165 arc.reverse();
166 }
167 if coords.last() == arc.first() {
168 arc.remove(0);
169 }
170 coords.extend(arc);
171 }
172 if coords.len() > 1 && coords.last() == coords.first() {
173 coords.pop();
174 }
175 coords
176}
177
178#[must_use]
185pub fn ring_degenerate(coords: &[(i32, i32)]) -> bool {
186 if coords.len() < 3 {
187 return true;
188 }
189 let mut doubled_area: i128 = 0;
190 for i in 0..coords.len() {
191 let (p, q) = (coords[i], coords[(i + 1) % coords.len()]);
192 doubled_area += i128::from(p.0) * i128::from(q.1) - i128::from(q.0) * i128::from(p.1);
193 }
194 doubled_area == 0 && !has_proper_cross(coords)
195}
196
197fn has_proper_cross(coords: &[(i32, i32)]) -> bool {
201 let len = coords.len();
202 let orient = |a: (i32, i32), b: (i32, i32), p: (i32, i32)| -> i8 {
203 let value = (i128::from(b.0) - i128::from(a.0)) * (i128::from(p.1) - i128::from(a.1))
204 - (i128::from(b.1) - i128::from(a.1)) * (i128::from(p.0) - i128::from(a.0));
205 i8::from(value > 0) - i8::from(value < 0)
206 };
207 for i in 0..len {
208 let (p1, p2) = (coords[i], coords[(i + 1) % len]);
209 for j in i + 2..len {
210 if i == 0 && j == len - 1 {
211 continue; }
213 let (q1, q2) = (coords[j], coords[(j + 1) % len]);
214 let (o1, o2) = (orient(p1, p2, q1), orient(p1, p2, q2));
215 let (o3, o4) = (orient(q1, q2, p1), orient(q1, q2, p2));
216 if o1 != o2 && o3 != o4 && o1 != 0 && o2 != 0 && o3 != 0 && o4 != 0 {
217 return true;
218 }
219 }
220 }
221 false
222}
223
224pub type CleanedTopo = (Vec<Vec<u32>>, Vec<Vec<Vec<usize>>>, Vec<Arc<i32>>);
227
228pub fn drop_degenerate_rings(
239 ring_refs: &[Vec<u32>],
240 structure: &[Vec<Vec<usize>>],
241 arcs: Vec<Arc<i32>>,
242 stats: &mut CleanStats,
243) -> CleanedTopo {
244 let ring_ok: Vec<bool> = ring_refs
245 .iter()
246 .map(|refs| !ring_degenerate(&ring_coords_q(refs, &arcs)))
247 .collect();
248
249 let mut new_refs: Vec<Vec<u32>> = Vec::new();
250 let mut new_structure: Vec<Vec<Vec<usize>>> = Vec::with_capacity(structure.len());
251 for feature in structure {
252 let mut feature_polys: Vec<Vec<usize>> = Vec::new();
253 for poly in feature {
254 match poly.first() {
255 Some(&exterior) if ring_ok[exterior] => {}
256 _ => {
257 stats.polys_dropped += 1;
258 stats.rings_dropped += u32::try_from(poly.len()).expect("ring count fits u32");
259 continue;
260 }
261 }
262 let mut poly_rings = Vec::with_capacity(poly.len());
263 for (k, &ring_index) in poly.iter().enumerate() {
264 if k > 0 && !ring_ok[ring_index] {
265 stats.rings_dropped += 1;
266 continue;
267 }
268 poly_rings.push(new_refs.len());
269 new_refs.push(ring_refs[ring_index].clone());
270 }
271 feature_polys.push(poly_rings);
272 }
273 new_structure.push(feature_polys);
274 }
275
276 let mut used = vec![false; arcs.len()];
278 for refs in &new_refs {
279 for &arc_ref in refs {
280 used[(arc_ref >> 1) as usize] = true;
281 }
282 }
283 let mut remap = vec![u32::MAX; arcs.len()];
284 let mut new_arcs = Vec::with_capacity(arcs.len());
285 for (i, arc) in arcs.into_iter().enumerate() {
286 if used[i] {
287 remap[i] = u32::try_from(new_arcs.len()).expect("arc count fits u32");
288 new_arcs.push(arc);
289 } else {
290 stats.arcs_dropped += 1;
291 }
292 }
293 for refs in &mut new_refs {
294 for arc_ref in refs.iter_mut() {
295 *arc_ref = (remap[(*arc_ref >> 1) as usize] << 1) | (*arc_ref & 1);
296 }
297 }
298 (new_refs, new_structure, new_arcs)
299}
300
301#[cfg(test)]
302mod tests {
303 use super::*;
304
305 fn stats() -> CleanStats {
306 CleanStats::default()
307 }
308
309 #[test]
310 fn open_arc_keeps_endpoints_and_kills_spike() {
311 let mut arc = vec![(0, 0), (5, 0), (9, 0), (5, 0), (5, 5)];
313 let mut stats = stats();
314 clean_arc(&mut arc, false, &mut stats);
315 assert_eq!(arc, vec![(0, 0), (5, 0), (5, 5)]);
316 assert!(stats.spikes >= 1);
317 }
318
319 #[test]
320 fn open_arc_multi_vertex_spur_unwinds() {
321 let mut arc = vec![(0, 0), (4, 0), (4, 3), (4, 9), (4, 3), (4, 0), (8, 0)];
323 let mut stats = stats();
324 clean_arc(&mut arc, false, &mut stats);
325 assert_eq!(arc, vec![(0, 0), (8, 0)]);
326 }
327
328 #[test]
329 fn open_arc_partial_retrace_spur() {
330 let mut arc = vec![(0, 0), (10, 0), (3, 0), (3, 4)];
332 let mut stats = stats();
333 clean_arc(&mut arc, false, &mut stats);
334 assert_eq!(arc, vec![(0, 0), (3, 0), (3, 4)]);
335 assert_eq!(stats.spikes, 1);
336 }
337
338 #[test]
339 fn open_arc_collinear_and_dups() {
340 let mut arc = vec![(0, 0), (0, 0), (2, 0), (5, 0), (5, 0), (9, 0)];
341 let mut stats = stats();
342 clean_arc(&mut arc, false, &mut stats);
343 assert_eq!(arc, vec![(0, 0), (9, 0)]);
344 assert_eq!(stats.dups, 2);
345 assert_eq!(stats.collinear, 2);
346 }
347
348 #[test]
349 fn closed_arc_spike_at_start_vertex() {
350 let mut arc = vec![(0, 0), (5, -5), (0, 0), (10, 0), (10, 10), (0, 10), (0, 0)];
353 let mut stats = stats();
354 clean_arc(&mut arc, true, &mut stats);
355 let len = arc.len();
356 assert_eq!(arc[0], arc[len - 1]);
357 let interior: Vec<_> = arc[..len - 1].to_vec();
358 assert_eq!(interior.len(), 4);
359 assert!(!interior.contains(&(5, -5)));
360 }
361
362 #[test]
363 fn closed_arc_collapses_to_degenerate() {
364 let mut arc = vec![(0, 0), (5, 0), (9, 0), (5, 0), (0, 0)];
367 let mut stats = stats();
368 clean_arc(&mut arc, true, &mut stats);
369 assert!(
370 ring_degenerate(&ring_coords_q(&[0 << 1], &[arc.clone()])),
371 "{arc:?}"
372 );
373 }
374
375 #[test]
376 fn degenerate_ring_detection() {
377 assert!(ring_degenerate(&[(0, 0), (5, 0)]));
378 assert!(ring_degenerate(&[(0, 0), (5, 0), (9, 0)])); assert!(!ring_degenerate(&[(0, 0), (5, 0), (5, 5)]));
380 }
381
382 #[test]
383 fn drop_degenerate_hole_keeps_poly_and_compacts_arcs() {
384 let arcs = vec![
386 vec![(0, 0), (10, 0), (10, 10), (0, 10), (0, 0)],
387 vec![(2, 2), (6, 2), (2, 2)],
388 ];
389 let ring_refs = vec![vec![0u32 << 1], vec![1u32 << 1]];
390 let structure = vec![vec![vec![0usize, 1]]];
391 let mut stats = stats();
392 let (refs, s, arcs) = drop_degenerate_rings(&ring_refs, &structure, arcs, &mut stats);
393 assert_eq!(s, vec![vec![vec![0usize]]]);
394 assert_eq!(refs.len(), 1);
395 assert_eq!(arcs.len(), 1);
396 assert_eq!(stats.rings_dropped, 1);
397 assert_eq!(stats.arcs_dropped, 1);
398 assert_eq!(stats.polys_dropped, 0);
399 }
400
401 #[test]
402 fn drop_degenerate_exterior_takes_holes() {
403 let arcs = vec![
404 vec![(0, 0), (10, 0), (0, 0)], vec![(2, 2), (6, 2), (6, 6), (2, 6), (2, 2)], ];
407 let ring_refs = vec![vec![0u32 << 1], vec![1u32 << 1]];
408 let structure = vec![vec![vec![0usize, 1]]];
409 let mut stats = stats();
410 let (refs, s, arcs) = drop_degenerate_rings(&ring_refs, &structure, arcs, &mut stats);
411 assert_eq!(s, vec![Vec::<Vec<usize>>::new()]);
412 assert!(refs.is_empty());
413 assert!(arcs.is_empty());
414 assert_eq!(stats.polys_dropped, 1);
415 assert_eq!(stats.rings_dropped, 2);
416 assert_eq!(stats.arcs_dropped, 2);
417 }
418}