1use 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#[derive(Clone, Copy, Debug)]
19pub struct Loc {
20 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 pub crossings: usize,
31 pub overlaps: usize,
34 pub touches: usize,
37 pub degenerate: usize,
40 pub verts: usize,
41 pub locs: Vec<Loc>,
44}
45
46#[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#[derive(Clone, Copy, Debug)]
65pub struct Problem {
66 pub lon: f64,
67 pub lat: f64,
68 pub kind: Kind,
69 pub feat: usize,
71}
72
73#[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
126pub 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; }
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 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
196fn 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 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 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 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 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}