Skip to main content

utz_encode/
clean.rs

1//! Post-quantization cleanup of the shared arcs. Snapping arc vertices to a
2//! coarse grid (especially i16, ~611 m cells) collapses nearby vertices and
3//! folds thin features onto themselves, leaving consecutive duplicates,
4//! zero-area spurs where the path reverses over itself ("spikes"), and
5//! rings whose area vanishes entirely. Left in, the spurs self-overlap and
6//! flip the runtime's even-odd PIP parity inside the fold.
7//!
8//! Every fix runs on the shared arcs (or drops whole rings), never on one
9//! polygon in isolation, so neighbouring zones stay stitched by
10//! construction; cleaning a border cleans it identically for both owners.
11
12use crate::{Arc, Ring};
13
14#[derive(Clone, Copy, Default, Debug)]
15pub struct CleanStats {
16    /// The number of consecutive duplicate vertices removed.
17    pub dups: u32,
18    /// The number of zero-area spur vertices removed (the path reverses
19    /// along the same line).
20    pub spikes: u32,
21    /// The number of collinear pass-through vertices removed (no geometry
22    /// change).
23    pub collinear: u32,
24    /// The number of degenerate rings dropped (fewer than 3 distinct
25    /// vertices, or area 0).
26    pub rings_dropped: u32,
27    /// The number of polygons dropped because their exterior ring
28    /// degenerated.
29    pub polys_dropped: u32,
30    /// The number of arcs left unreferenced by ring drops; they are removed
31    /// and the ids compacted.
32    pub arcs_dropped: u32,
33}
34
35enum Kind {
36    Spike,
37    Collinear,
38    Keep,
39}
40
41/// Classifies how the path bends at `q` between `p` and `r` (both distinct
42/// from `q`).
43fn 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
56/// Removes quantization artifacts from one quantized arc, in place.
57///
58/// An interior vertex goes when it duplicates its predecessor, when the path
59/// reverses over it along the same line (a zero-area spike; the pass
60/// iterates, so multi-vertex spurs unwind fully), or when it lies
61/// collinearly between its
62/// neighbours. `closed` arcs (cut-free rings, stored with first == last) are
63/// cleaned cyclically so artifacts at the arbitrary start vertex are caught
64/// too; open arcs never lose their endpoints: those are junctions shared
65/// with other arcs.
66pub 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/// Assembles one ring's quantized coords from its signed arc refs, the
157/// integer twin of `Topology::reconstruct()`'s ring assembly.
158#[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/// Reports whether the ring collapsed under quantization: fewer than 3
179/// vertices remain, or the shoelace area is exactly 0 with no proper
180/// self-crossing. The crossing exemption
181/// matters: a bowtie with equal opposite lobes has signed area 0 yet still
182/// covers both lobes under the runtime's even-odd rule. Dropping it would
183/// lose real coverage. The computation is exact in i128 for all qbits.
184#[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
197/// Reports whether any pair of non-adjacent ring segments properly crosses
198/// (their interiors intersect). The scan is O(n²), but it is only reached
199/// for zero-area rings, which quantization keeps tiny.
200fn 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; // adjacent around the wrap
212            }
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
224/// The `(ring_refs, structure, arcs)` triple mirroring `Topology`'s fields,
225/// with arcs quantized to integer coordinates.
226pub type CleanedTopo = (Vec<Vec<u32>>, Vec<Vec<Vec<usize>>>, Vec<Arc<i32>>);
227
228/// Drops rings that quantization collapsed to zero area: a degenerate hole
229/// vanishes alone, and a degenerate exterior takes its holes with it. Arcs
230/// that no surviving ring references are removed, and their ids are
231/// compacted. Returns the
232/// filtered `(ring_refs, structure, arcs)` mirroring `Topology`'s fields.
233/// Dropping a zero-area ring can't open a crack with a neighbour: there was
234/// no area to disagree about.
235///
236/// # Panics
237/// Panics if a polygon has more than `u32::MAX` rings.
238pub 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    // compact arc ids to the surviving rings
277    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        // A-B-A retrace in the middle of an arc
312        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        // spur wanders out two vertices and retraces exactly
322        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        // reverses along the same line but not onto an existing vertex
331        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        // ring stored first == last, spur sits exactly on the start vertex —
351        // the open-arc pass can't touch it, the cyclic pass must
352        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        // entire ring snaps onto one line; whatever remnant survives must
365        // read as a degenerate ring so the ring-level drop removes it
366        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)])); // zero area
379        assert!(!ring_degenerate(&[(0, 0), (5, 0), (5, 5)]));
380    }
381
382    #[test]
383    fn drop_degenerate_hole_keeps_poly_and_compacts_arcs() {
384        // poly 0: square exterior (arc 0, closed) + zero-area hole (arc 1)
385        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)],                // flat exterior
405            vec![(2, 2), (6, 2), (6, 6), (2, 6), (2, 2)], // healthy hole
406        ];
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}