Skip to main content

utz_encode/
validate.rs

1//! Ring-geometry validation, which finds where assembled rings
2//! self-cross, overlap themselves collinearly, self-touch, or collapse
3//! entirely. It is shared by the `utz_dev_cli quant-clean` report and the
4//! viewer's live problems panel (wasm.rs), so both agree on what
5//! "problematic geometry" means.
6
7use crate::clean::{self, CleanStats};
8use crate::topo::Topology;
9use crate::{Arc, Ring};
10
11#[derive(Clone, Copy, PartialEq, Debug)]
12pub enum Kind {
13    Cross,
14    Overlap,
15}
16
17/// One located defect, in quantized grid units (see [`Bad::locs`]).
18#[derive(Clone, Copy, Debug)]
19pub struct Loc {
20    /// The ring ordinal within the measured iteration.
21    pub ring: usize,
22    pub kind: Kind,
23    pub x: f64,
24    pub y: f64,
25}
26
27#[derive(Default, Clone)]
28pub struct Bad {
29    /// The number of non-adjacent segment pairs that properly cross.
30    pub crossings: usize,
31    /// The number of non-adjacent collinear segment pairs overlapping in
32    /// more than a point.
33    pub overlaps: usize,
34    /// The number of non-adjacent segment pairs touching in exactly one
35    /// point.
36    pub touches: usize,
37    /// The number of rings with fewer than 3 distinct vertices or zero
38    /// area.
39    pub degenerate: usize,
40    pub verts: usize,
41    /// The located crossing/overlap spots (touches are counted but not
42    /// located).
43    pub locs: Vec<Loc>,
44}
45
46/// Sweeps every ring and tallies the problems: self-crossings, collinear
47/// overlaps, self-touches, and degenerate rings.
48#[must_use]
49pub fn measure(rings: impl Iterator<Item = Ring<i32>>) -> Bad {
50    let mut bad = Bad::default();
51    for (ring_index, coords) in rings.enumerate() {
52        bad.verts += coords.len();
53        if clean::ring_degenerate(&coords) {
54            bad.degenerate += 1;
55            continue;
56        }
57        ring_bad(ring_index, &coords, &mut bad);
58    }
59    bad
60}
61
62/// A surviving defect of one feature's geometry, in degrees. This is
63/// what the viewer's problems panel lists.
64#[derive(Clone, Copy, Debug)]
65pub struct Problem {
66    pub lon: f64,
67    pub lat: f64,
68    pub kind: Kind,
69    /// The owning feature index.
70    pub feat: usize,
71}
72
73/// Runs the encoder's quantize, clean, and drop-degenerate pipeline on
74/// already-simplified arcs at `qbits`, then locates every surviving
75/// crossing/overlap. A spot on a shared border is reported once per
76/// owning ring (dedupe by coordinates for display).
77#[must_use]
78pub fn find_problems(
79    topology: &Topology,
80    arc_coords: &[Vec<(f64, f64)>],
81    qbits: u32,
82) -> Vec<Problem> {
83    let qmax = crate::qmax_for(qbits);
84    let mut clean_stats = CleanStats::default();
85    let quantize = |&(lon, lat): &(f64, f64)| (crate::q_lon(lon, qmax), crate::q_lat(lat, qmax));
86    let arcs_q: Vec<Arc<i32>> = arc_coords
87        .iter()
88        .map(|arc| {
89            let mut quantized: Vec<(i32, i32)> = arc.iter().map(quantize).collect();
90            let closed = arc.len() > 1 && arc.first() == arc.last();
91            clean::clean_arc(&mut quantized, closed, &mut clean_stats);
92            quantized
93        })
94        .collect();
95    let (ring_refs, structure, arcs_q) = clean::drop_degenerate_rings(
96        &topology.ring_refs,
97        &topology.structure,
98        arcs_q,
99        &mut clean_stats,
100    );
101
102    let mut owner = vec![usize::MAX; ring_refs.len()];
103    for (feature_index, feature) in structure.iter().enumerate() {
104        for poly in feature {
105            for &ring_index in poly {
106                owner[ring_index] = feature_index;
107            }
108        }
109    }
110    let bad = measure(
111        ring_refs
112            .iter()
113            .map(|refs| clean::ring_coords_q(refs, &arcs_q)),
114    );
115    bad.locs
116        .iter()
117        .map(|location| Problem {
118            lon: crate::dq_lon(location.x, qmax),
119            lat: crate::dq_lat(location.y, qmax),
120            kind: location.kind,
121            feat: owner[location.ring],
122        })
123        .collect()
124}
125
126/// Counts the non-adjacent segment pairs of one ring that intersect,
127/// split by kind. The sweep runs over min-x-sorted segments in
128/// O(n log n + pairs-in-x-overlap), which is fine at report scale.
129/// Crossing/overlap spots land in `bad.locs`.
130///
131/// # Panics
132/// Panics if a ring has more than `u32::MAX` segments.
133pub fn ring_bad(ring_index: usize, ring: &[(i32, i32)], bad: &mut Bad) {
134    let len = ring.len();
135    if len < 4 {
136        return;
137    }
138    let segment = |index: usize| (ring[index], ring[(index + 1) % len]);
139    let min_x = |index: usize| {
140        let (a, b) = segment(index);
141        a.0.min(b.0)
142    };
143    let mut order: Vec<u32> = (0..u32::try_from(len).expect("segment count fits u32")).collect();
144    order.sort_unstable_by_key(|&index| min_x(index as usize));
145    for sweep_position in 0..len {
146        let segment_a = order[sweep_position] as usize;
147        let (p1, p2) = segment(segment_a);
148        let (max_x, min_y, max_y) = (p1.0.max(p2.0), p1.1.min(p2.1), p1.1.max(p2.1));
149        for &other in &order[sweep_position + 1..] {
150            let segment_b = other as usize;
151            let (q1, q2) = segment(segment_b);
152            if q1.0.min(q2.0) > max_x {
153                break;
154            }
155            if segment_a.abs_diff(segment_b) == 1 || segment_a.abs_diff(segment_b) == len - 1 {
156                continue; // adjacent segments share a vertex by construction
157            }
158            if q1.1.max(q2.1) < min_y || q1.1.min(q2.1) > max_y {
159                continue;
160            }
161            match seg_class((p1, p2), (q1, q2)) {
162                Class::Cross => {
163                    bad.crossings += 1;
164                    let (x, y) = cross_point((p1, p2), (q1, q2));
165                    bad.locs.push(Loc {
166                        ring: ring_index,
167                        kind: Kind::Cross,
168                        x,
169                        y,
170                    });
171                }
172                Class::Overlap => {
173                    bad.overlaps += 1;
174                    // midpoint of the shared stretch: average the two middle
175                    // endpoints along the sort order
176                    let mut points = [p1, p2, q1, q2];
177                    points.sort_unstable();
178                    let (x, y) = (
179                        f64::midpoint(f64::from(points[1].0), f64::from(points[2].0)),
180                        f64::midpoint(f64::from(points[1].1), f64::from(points[2].1)),
181                    );
182                    bad.locs.push(Loc {
183                        ring: ring_index,
184                        kind: Kind::Overlap,
185                        x,
186                        y,
187                    });
188                }
189                Class::Touch => bad.touches += 1,
190                Class::None => {}
191            }
192        }
193    }
194}
195
196/// Computes the intersection point of two properly crossing segments
197/// (the denominator is nonzero exactly because they properly cross).
198fn cross_point(
199    (p1, p2): ((i32, i32), (i32, i32)),
200    (q1, q2): ((i32, i32), (i32, i32)),
201) -> (f64, f64) {
202    let (dx, dy) = (f64::from(p2.0 - p1.0), f64::from(p2.1 - p1.1));
203    let (ex, ey) = (f64::from(q2.0 - q1.0), f64::from(q2.1 - q1.1));
204    let denominator = dx * ey - dy * ex;
205    let t = (f64::from(q1.0 - p1.0) * ey - f64::from(q1.1 - p1.1) * ex) / denominator;
206    (f64::from(p1.0) + t * dx, f64::from(p1.1) + t * dy)
207}
208
209enum Class {
210    None,
211    Touch,
212    Cross,
213    Overlap,
214}
215
216fn orient(a: (i32, i32), b: (i32, i32), c: (i32, i32)) -> i128 {
217    (i128::from(b.0) - i128::from(a.0)) * (i128::from(c.1) - i128::from(a.1))
218        - (i128::from(b.1) - i128::from(a.1)) * (i128::from(c.0) - i128::from(a.0))
219}
220
221fn sgn(value: i128) -> i8 {
222    i8::from(value > 0) - i8::from(value < 0)
223}
224
225fn in_bbox(p: (i32, i32), a: (i32, i32), b: (i32, i32)) -> bool {
226    p.0 >= a.0.min(b.0) && p.0 <= a.0.max(b.0) && p.1 >= a.1.min(b.1) && p.1 <= a.1.max(b.1)
227}
228
229fn seg_class((p1, p2): ((i32, i32), (i32, i32)), (q1, q2): ((i32, i32), (i32, i32))) -> Class {
230    let (o1, o2) = (sgn(orient(p1, p2, q1)), sgn(orient(p1, p2, q2)));
231    let (o3, o4) = (sgn(orient(q1, q2, p1)), sgn(orient(q1, q2, p2)));
232    if o1 == 0 && o2 == 0 && o3 == 0 && o4 == 0 {
233        // collinear: project on the dominant axis and compare 1D ranges
234        let flat = p1.0 == p2.0 && q1.0 == q2.0;
235        let axis_value = |p: (i32, i32)| if flat { p.1 } else { p.0 };
236        let (a0, a1) = (
237            axis_value(p1).min(axis_value(p2)),
238            axis_value(p1).max(axis_value(p2)),
239        );
240        let (b0, b1) = (
241            axis_value(q1).min(axis_value(q2)),
242            axis_value(q1).max(axis_value(q2)),
243        );
244        let (lo, hi) = (a0.max(b0), a1.min(b1));
245        return match lo.cmp(&hi) {
246            core::cmp::Ordering::Less => Class::Overlap,
247            core::cmp::Ordering::Equal => Class::Touch,
248            core::cmp::Ordering::Greater => Class::None,
249        };
250    }
251    if o1 != o2 && o3 != o4 && o1 != 0 && o2 != 0 && o3 != 0 && o4 != 0 {
252        return Class::Cross;
253    }
254    // an endpoint of one segment lying on the other = touch
255    if (o1 == 0 && in_bbox(q1, p1, p2))
256        || (o2 == 0 && in_bbox(q2, p1, p2))
257        || (o3 == 0 && in_bbox(p1, q1, q2))
258        || (o4 == 0 && in_bbox(p2, q1, q2))
259    {
260        return Class::Touch;
261    }
262    Class::None
263}
264
265#[cfg(test)]
266mod tests {
267    use super::*;
268
269    #[test]
270    fn bowtie_ring_crosses_once() {
271        // figure-8: segments (0,0)-(10,10) and (10,0)-(0,10) properly cross
272        let ring = vec![(0, 0), (10, 10), (10, 0), (0, 10)];
273        let bad = measure(vec![ring].into_iter());
274        assert_eq!(bad.crossings, 1);
275        assert_eq!(bad.locs.len(), 1);
276        let location = bad.locs[0];
277        assert_eq!((location.x, location.y), (5.0, 5.0));
278    }
279
280    #[test]
281    fn square_ring_is_clean() {
282        let ring = vec![(0, 0), (10, 0), (10, 10), (0, 10)];
283        let bad = measure(vec![ring].into_iter());
284        assert_eq!(
285            (bad.crossings, bad.overlaps, bad.touches, bad.degenerate),
286            (0, 0, 0, 0)
287        );
288    }
289
290    #[test]
291    fn find_problems_locates_bowtie_in_degrees() {
292        // one feature, one ring stored as a single closed arc, bowtie shape
293        // big enough to survive i16 snapping (~0.005° cells)
294        let arc: Vec<(f64, f64)> = vec![(0.0, 0.0), (1.0, 1.0), (1.0, 0.0), (0.0, 1.0), (0.0, 0.0)];
295        let topology = Topology {
296            arc_coords: vec![arc.clone()],
297            ring_refs: vec![vec![0 << 1]],
298            structure: vec![vec![vec![0]]],
299        };
300        let problems = find_problems(&topology, &topology.arc_coords, 16);
301        assert_eq!(problems.len(), 1);
302        assert_eq!(problems[0].feat, 0);
303        assert!(matches!(problems[0].kind, Kind::Cross));
304        assert!(
305            (problems[0].lon - 0.5).abs() < 0.01 && (problems[0].lat - 0.5).abs() < 0.01,
306            "{:?}",
307            problems[0]
308        );
309    }
310}