1use std::collections::HashMap;
10
11use crate::{Arc, Feat};
12pub use utz_simplify::{Simplify, simplify};
14
15use crate::{q_lat, q_lon, qmax_for};
17fn pushb(out: &mut Vec<u8>, value: i32, bits: u32) {
18 let byte_len = bits.div_ceil(8) as usize; out.extend_from_slice(&value.to_le_bytes()[0..byte_len]);
20}
21
22#[must_use]
25pub fn zigzag(value: i64) -> u64 {
26 ((value << 1) ^ (value >> 63)).cast_unsigned()
27}
28pub fn put_varint(out: &mut Vec<u8>, mut value: u64) {
31 loop {
32 let byte = (value & 0x7f) as u8;
33 value >>= 7;
34 if value == 0 {
35 out.push(byte);
36 break;
37 }
38 out.push(byte | 0x80);
39 }
40}
41
42type VId = u32;
43
44pub struct TopoOut {
47 pub bytes: Vec<u8>,
49 pub arcs: usize,
51 pub ring_refs: usize,
53 pub verts: usize,
55 pub simplified: Vec<Feat>,
57}
58
59pub struct Topology {
63 pub arc_coords: Vec<Arc>,
64 pub ring_refs: Vec<Vec<u32>>,
66 pub structure: Vec<Vec<Vec<usize>>>,
69}
70
71impl Topology {
72 #[must_use]
75 pub fn reconstruct(&self, feats: &[Feat], arc_coords: &[Vec<(f64, f64)>]) -> Vec<Feat> {
76 let ring_coords = |ring_index: usize| -> Vec<(f64, f64)> {
77 let mut coords: Vec<(f64, f64)> = Vec::new();
78 for &arc_ref in &self.ring_refs[ring_index] {
79 let (id, reversed) = ((arc_ref >> 1) as usize, (arc_ref & 1) == 1);
80 let mut arc = arc_coords[id].clone();
81 if reversed {
82 arc.reverse();
83 }
84 if coords.last() == arc.first() {
85 arc.remove(0);
86 }
87 coords.extend(arc);
88 }
89 if coords.last() == coords.first() && coords.len() > 1 {
90 coords.pop();
91 }
92 coords
93 };
94 feats
95 .iter()
96 .enumerate()
97 .map(|(feature_index, feature)| {
98 let polys = self.structure[feature_index]
99 .iter()
100 .map(|poly| {
101 poly.iter()
102 .map(|&ring_index| ring_coords(ring_index))
103 .collect()
104 })
105 .collect();
106 Feat {
107 offset: feature.offset,
108 tzid: feature.tzid.clone(),
109 polys,
110 }
111 })
112 .collect()
113 }
114}
115
116#[must_use]
120pub fn encode_topology(feats: &[Feat], epsilon_deg: f64) -> TopoOut {
121 encode_topology_q(feats, epsilon_deg, 24)
122}
123
124#[must_use]
127pub fn encode_topology_q(feats: &[Feat], epsilon_deg: f64, qbits: u32) -> TopoOut {
128 encode_topology_qm(feats, epsilon_deg, qbits, false)
129}
130
131#[must_use]
135pub fn build_topology(feats: &[Feat], epsilon_deg: f64) -> Topology {
136 build_topology_algorithm(
137 feats,
138 Simplify::Rdp {
139 epsilon: epsilon_deg,
140 },
141 )
142}
143
144#[must_use]
147pub fn build_topology_algorithm(feats: &[Feat], algorithm: Simplify) -> Topology {
148 build_topology_impl(feats, algorithm, None)
149}
150
151pub fn build_topology_weighted(
160 feats: &[Feat],
161 algorithm: Simplify,
162 edge_weight: &EdgeWeightFn<'_>,
163) -> Topology {
164 build_topology_impl(feats, algorithm, Some(edge_weight))
165}
166
167pub type EdgeWeightFn<'a> = dyn Fn((f64, f64), (f64, f64)) -> f64 + 'a;
170
171#[expect(
172 clippy::too_many_lines,
173 reason = "one pass over shared vertex/arc tables; stage extraction would thread six mutable maps through every helper"
174)]
175fn build_topology_impl(
176 feats: &[Feat],
177 algorithm: Simplify,
178 edge_weight: Option<&EdgeWeightFn<'_>>,
179) -> Topology {
180 let mut vertex_ids: HashMap<(u64, u64), VId> = HashMap::new();
182 let mut vertex_coords: Vec<(f64, f64)> = Vec::new();
183 let intern_vertex = |x: f64,
184 y: f64,
185 vertex_ids: &mut HashMap<(u64, u64), VId>,
186 vertex_coords: &mut Vec<(f64, f64)>|
187 -> VId {
188 *vertex_ids
189 .entry((x.to_bits(), y.to_bits()))
190 .or_insert_with(|| {
191 vertex_coords.push((x, y));
192 VId::try_from(vertex_coords.len() - 1).expect("vertex id fits u32")
193 })
194 };
195 let mut rings: Vec<Vec<VId>> = Vec::new();
196 let mut structure: Vec<Vec<Vec<usize>>> = Vec::new();
197 for feature in feats {
198 let mut feature_polys = Vec::new();
199 for poly in &feature.polys {
200 let mut poly_rings = Vec::new();
201 for ring in poly {
202 let vertex_seq: Vec<VId> = ring
203 .iter()
204 .map(|&(x, y)| intern_vertex(x, y, &mut vertex_ids, &mut vertex_coords))
205 .collect();
206 poly_rings.push(rings.len());
207 rings.push(vertex_seq);
208 }
209 feature_polys.push(poly_rings);
210 }
211 structure.push(feature_polys);
212 }
213
214 let mut owners: HashMap<(VId, VId), Vec<u32>> = HashMap::new();
216 for (ring_index, vertex_seq) in rings.iter().enumerate() {
217 let len = vertex_seq.len();
218 for i in 0..len {
219 let (a, b) = (vertex_seq[i], vertex_seq[(i + 1) % len]);
220 let key = if a < b { (a, b) } else { (b, a) };
221 let entry = owners.entry(key).or_default();
222 let ring_index_u32 = u32::try_from(ring_index).expect("ring id fits u32");
223 if entry.last() != Some(&ring_index_u32) {
224 entry.push(ring_index_u32);
225 }
226 }
227 }
228 let mut signature_ids: HashMap<Vec<u32>, u32> = HashMap::new();
229 let mut edge_signature: HashMap<(VId, VId), u32> = HashMap::new();
230 for (edge, owner_rings) in &owners {
231 let mut sorted_owners = owner_rings.clone();
232 sorted_owners.sort_unstable();
233 sorted_owners.dedup();
234 let next = u32::try_from(signature_ids.len()).expect("arc id fits u32");
235 let id = *signature_ids.entry(sorted_owners).or_insert(next);
236 edge_signature.insert(*edge, id);
237 }
238 let signature =
239 |a: VId, b: VId| -> u32 { edge_signature[&if a < b { (a, b) } else { (b, a) }] };
240
241 let mut arc_ids: HashMap<Vec<VId>, u32> = HashMap::new();
243 let mut arcs: Vec<Vec<VId>> = Vec::new();
244 let mut ring_refs: Vec<Vec<u32>> = vec![Vec::new(); rings.len()];
245 let intern = |vertex_seq: Vec<VId>,
246 arc_ids: &mut HashMap<Vec<VId>, u32>,
247 arcs: &mut Vec<Vec<VId>>|
248 -> u32 {
249 let mut reversed = vertex_seq.clone();
250 reversed.reverse();
251 let (canonical, direction) = if vertex_seq <= reversed {
252 (vertex_seq, 0u32)
253 } else {
254 (reversed, 1u32)
255 };
256 let next = u32::try_from(arcs.len()).expect("arc id fits u32");
257 let id = *arc_ids.entry(canonical.clone()).or_insert_with(|| {
258 arcs.push(canonical);
259 next
260 });
261 (id << 1) | direction
262 };
263 for (ring_index, vertex_seq) in rings.iter().enumerate() {
264 let len = vertex_seq.len();
265 if len == 0 {
266 continue;
267 }
268 let mut cuts: Vec<usize> = Vec::new();
269 for i in 0..len {
270 if signature(vertex_seq[(i + len - 1) % len], vertex_seq[i])
271 != signature(vertex_seq[i], vertex_seq[(i + 1) % len])
272 {
273 cuts.push(i);
274 }
275 }
276 if cuts.is_empty() {
277 let min_vertex = *vertex_seq.iter().min().unwrap();
288 let mut best: Option<(Vec<VId>, bool)> = None; for i in (0..len).filter(|&i| vertex_seq[i] == min_vertex) {
290 let forward_walk: Vec<VId> = (0..=len).map(|k| vertex_seq[(i + k) % len]).collect();
291 let backward_walk: Vec<VId> =
292 (0..=len).map(|k| vertex_seq[(i + len - k) % len]).collect();
293 for (candidate, is_forward) in [(forward_walk, true), (backward_walk, false)] {
294 if best
295 .as_ref()
296 .is_none_or(|(best_walk, _)| candidate < *best_walk)
297 {
298 best = Some((candidate, is_forward));
299 }
300 }
301 }
302 let (canonical, forward) = best.unwrap();
303 let walk = if forward {
304 canonical
305 } else {
306 let mut reversed = canonical;
307 reversed.reverse();
308 reversed
309 };
310 ring_refs[ring_index].push(intern(walk, &mut arc_ids, &mut arcs));
311 } else {
312 for j in 0..cuts.len() {
313 let (start, end) = (cuts[j], cuts[(j + 1) % cuts.len()]);
314 let mut arc_seq = Vec::new();
315 let mut k = start;
316 loop {
317 arc_seq.push(vertex_seq[k]);
318 if k == end {
319 break;
320 }
321 k = (k + 1) % len;
322 }
323 ring_refs[ring_index].push(intern(arc_seq, &mut arc_ids, &mut arcs));
324 }
325 }
326 }
327
328 let arc_coords: Vec<Arc> = arcs
330 .iter()
331 .map(|arc| {
332 let coords: Vec<(f64, f64)> = arc
333 .iter()
334 .map(|&vertex_id| vertex_coords[vertex_id as usize])
335 .collect();
336 match edge_weight {
337 None => simplify(algorithm, &coords),
338 Some(weight_fn) => {
339 let edge_weights: Vec<f64> = coords
340 .windows(2)
341 .map(|pair| weight_fn(pair[0], pair[1]))
342 .collect();
343 let vertex_weights: Vec<f64> = (0..coords.len())
344 .map(|i| {
345 let left = if i > 0 {
346 edge_weights[i - 1]
347 } else {
348 f64::INFINITY
349 };
350 let right = edge_weights.get(i).copied().unwrap_or(f64::INFINITY);
351 left.min(right).min(1.0) })
353 .collect();
354 utz_simplify::simplify_weighted(algorithm, &coords, &vertex_weights)
355 }
356 }
357 })
358 .collect();
359
360 Topology {
361 arc_coords,
362 ring_refs,
363 structure,
364 }
365}
366
367#[must_use]
370#[expect(
375 clippy::too_many_lines,
376 reason = "linear serialization of one container; the stages share the running buffer and section offsets"
377)]
378pub fn encode_topology_qm(
379 feats: &[Feat],
380 epsilon_deg: f64,
381 qbits: u32,
382 abs_fixed: bool,
383) -> TopoOut {
384 let qmax = qmax_for(qbits);
385 let topo = build_topology(feats, epsilon_deg);
386 let Topology {
387 arc_coords,
388 ring_refs,
389 structure,
390 } = &topo;
391 let verts: usize = arc_coords.iter().map(std::vec::Vec::len).sum();
392 let simplified = topo.reconstruct(feats, arc_coords);
393
394 let total_refs: usize = ring_refs.iter().map(std::vec::Vec::len).sum();
396 let mut pool: Vec<String> = Vec::new();
397 let mut tzid_indices: HashMap<String, u16> = HashMap::new();
398 for feature in feats {
399 if let Some(tzid) = &feature.tzid
400 && !tzid_indices.contains_key(tzid)
401 {
402 tzid_indices.insert(
403 tzid.clone(),
404 u16::try_from(pool.len()).expect("tzid pool index fits u16"),
405 );
406 pool.push(tzid.clone());
407 }
408 }
409 let mut out = Vec::new();
410 out.extend_from_slice(&0x4E45_4442u32.to_le_bytes());
411 out.extend_from_slice(
412 &u32::try_from(feats.len())
413 .expect("feature count fits u32")
414 .to_le_bytes(),
415 );
416 out.extend_from_slice(
417 &u16::try_from(pool.len())
418 .expect("tzid pool count fits u16")
419 .to_le_bytes(),
420 );
421 for tzid in &pool {
422 out.extend_from_slice(
423 &u16::try_from(tzid.len())
424 .expect("tzid length fits u16")
425 .to_le_bytes(),
426 );
427 out.extend_from_slice(tzid.as_bytes());
428 }
429 out.extend_from_slice(
430 &u32::try_from(arc_coords.len())
431 .expect("arc count fits u32")
432 .to_le_bytes(),
433 );
434 for arc in arc_coords {
435 put_varint(&mut out, arc.len() as u64);
436 let (mut previous_x, mut previous_y) = (0i64, 0i64);
437 for (i, &(lon, lat)) in arc.iter().enumerate() {
438 let (current_x, current_y) = (i64::from(q_lon(lon, qmax)), i64::from(q_lat(lat, qmax)));
439 if abs_fixed || i == 0 {
440 pushb(
441 &mut out,
442 i32::try_from(current_x).expect("quantized coord fits i32"),
443 qbits,
444 );
445 pushb(
446 &mut out,
447 i32::try_from(current_y).expect("quantized coord fits i32"),
448 qbits,
449 );
450 } else {
451 put_varint(&mut out, zigzag(current_x - previous_x));
452 put_varint(&mut out, zigzag(current_y - previous_y));
453 }
454 previous_x = current_x;
455 previous_y = current_y;
456 }
457 }
458 for (feature_index, feature) in feats.iter().enumerate() {
459 #[expect(clippy::cast_possible_truncation, reason = "f32 header field")]
460 let offset32 = feature.offset as f32;
461 out.extend_from_slice(&offset32.to_le_bytes());
462 let tzid_index = feature
463 .tzid
464 .as_ref()
465 .map_or(0xFFFF, |tzid| tzid_indices[tzid]);
466 out.extend_from_slice(&tzid_index.to_le_bytes());
467 let (mut min_x, mut min_y, mut max_x, mut max_y) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
468 for poly in &feature.polys {
469 for ring in poly {
470 for &(lon, lat) in ring {
471 let (x, y) = (q_lon(lon, qmax), q_lat(lat, qmax));
472 min_x = min_x.min(x);
473 min_y = min_y.min(y);
474 max_x = max_x.max(x);
475 max_y = max_y.max(y);
476 }
477 }
478 }
479 for value in [min_x, min_y, max_x, max_y] {
480 pushb(&mut out, value, qbits);
481 }
482 out.extend_from_slice(
483 &u16::try_from(structure[feature_index].len())
484 .expect("poly count fits u16")
485 .to_le_bytes(),
486 );
487 for poly in &structure[feature_index] {
488 out.extend_from_slice(
489 &u16::try_from(poly.len())
490 .expect("ring count fits u16")
491 .to_le_bytes(),
492 );
493 for &ring_index in poly {
494 put_varint(&mut out, ring_refs[ring_index].len() as u64);
495 for &arc_ref in &ring_refs[ring_index] {
496 put_varint(&mut out, u64::from(arc_ref));
497 }
498 }
499 }
500 }
501 TopoOut {
502 bytes: out,
503 arcs: arc_coords.len(),
504 ring_refs: total_refs,
505 verts,
506 simplified,
507 }
508}
509
510#[cfg(test)]
511mod tests {
512 use super::*;
513 use crate::{Poly, Ring};
514
515 fn two_squares() -> Vec<Feat> {
518 let shared: Vec<(f64, f64)> = (0..=10)
519 .map(|i| {
520 (
521 1.0 + if i % 2 == 1 { 0.001 } else { 0.0 },
522 f64::from(i) / 10.0,
523 )
524 })
525 .collect(); let mut left: Ring = vec![(0.0, 0.0)];
527 left.extend(&shared); left.push((0.0, 1.0));
529 let mut right: Ring = vec![(2.0, 0.0), (2.0, 1.0)];
530 right.extend(shared.iter().rev()); let make_feature = |ring: Ring| Feat {
532 offset: 0.0,
533 tzid: None,
534 polys: vec![vec![ring] as Poly],
535 };
536 vec![make_feature(left), make_feature(right)]
537 }
538
539 #[test]
544 fn shared_island_ring_interns_once() {
545 let island: Ring = vec![(1.0, 1.0), (2.0, 1.0), (2.0, 2.0), (1.0, 2.0)];
546 let hole: Ring = vec![(2.0, 2.0), (2.0, 1.0), (1.0, 1.0), (1.0, 2.0)];
548 let sea: Ring = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 3.0), (0.0, 3.0)];
549 let feats = vec![
550 Feat {
551 offset: 0.0,
552 tzid: None,
553 polys: vec![vec![island] as Poly],
554 },
555 Feat {
556 offset: 1.0,
557 tzid: None,
558 polys: vec![vec![sea, hole] as Poly],
559 },
560 ];
561 let topology = build_topology_algorithm(&feats, Simplify::Rdp { epsilon: 0.0 });
562 assert_eq!(
564 topology.arc_coords.len(),
565 2,
566 "island ring duplicated: {:?}",
567 topology.arc_coords
568 );
569 let reconstructed = topology.reconstruct(&feats, &topology.arc_coords);
571 for (feature, original) in reconstructed.iter().zip(&feats) {
572 for (polys, original_polys) in feature.polys.iter().zip(&original.polys) {
573 for (ring, original_ring) in polys.iter().zip(original_polys) {
574 let mut actual: Vec<_> = ring
575 .iter()
576 .map(|&(x, y)| (x.to_bits(), y.to_bits()))
577 .collect();
578 let mut expected: Vec<_> = original_ring
579 .iter()
580 .map(|&(x, y)| (x.to_bits(), y.to_bits()))
581 .collect();
582 actual.sort_unstable();
583 expected.sort_unstable();
584 assert_eq!(actual, expected);
585 }
586 }
587 }
588 }
589
590 #[test]
595 fn shared_pinched_ring_interns_once() {
596 let eight: Ring = vec![
597 (0.0, 0.0),
598 (1.0, 0.0),
599 (1.0, 1.0),
600 (0.0, 0.0),
601 (-1.0, 0.0),
602 (-1.0, -1.0),
603 ];
604 let eight_rev: Ring = vec![
606 (1.0, 1.0),
607 (1.0, 0.0),
608 (0.0, 0.0),
609 (-1.0, -1.0),
610 (-1.0, 0.0),
611 (0.0, 0.0),
612 ];
613 let feats = vec![
614 Feat {
615 offset: 0.0,
616 tzid: None,
617 polys: vec![vec![eight] as Poly],
618 },
619 Feat {
620 offset: 1.0,
621 tzid: None,
622 polys: vec![vec![eight_rev] as Poly],
623 },
624 ];
625 let topology = build_topology_algorithm(&feats, Simplify::Rdp { epsilon: 0.0 });
626 assert_eq!(
627 topology.arc_coords.len(),
628 1,
629 "pinched ring duplicated: {:?}",
630 topology.arc_coords
631 );
632 let reconstructed = topology.reconstruct(&feats, &topology.arc_coords);
634 for (feature, original) in reconstructed.iter().zip(&feats) {
635 let mut actual: Vec<_> = feature.polys[0][0]
636 .iter()
637 .map(|&(x, y)| (x.to_bits(), y.to_bits()))
638 .collect();
639 let mut expected: Vec<_> = original.polys[0][0]
640 .iter()
641 .map(|&(x, y)| (x.to_bits(), y.to_bits()))
642 .collect();
643 actual.sort_unstable();
644 expected.sort_unstable();
645 assert_eq!(actual, expected);
646 }
647 }
648
649 #[test]
650 fn weighted_all_ones_matches_unweighted() {
651 let feats = two_squares();
652 let unweighted = build_topology_algorithm(&feats, Simplify::Rdp { epsilon: 0.01 });
653 let weighted =
654 build_topology_weighted(&feats, Simplify::Rdp { epsilon: 0.01 }, &|_, _| 1.0);
655 assert_eq!(unweighted.arc_coords, weighted.arc_coords);
656 assert_eq!(unweighted.ring_refs, weighted.ring_refs);
657 }
658
659 #[test]
660 fn weighted_shared_arc_consistent() {
661 let feats = two_squares();
662 let (kept_bump, dropped_bump) = ((1.001, 0.5), (1.001, 0.1));
663 let weight = |a: (f64, f64), b: (f64, f64)| {
666 if (0.42..=0.58).contains(&f64::midpoint(a.1, b.1)) {
667 0.05
668 } else {
669 1.0
670 }
671 };
672 let topology = build_topology_weighted(&feats, Simplify::Rdp { epsilon: 0.01 }, &weight);
673 let reconstructed = topology.reconstruct(&feats, &topology.arc_coords);
674 for feature in &reconstructed {
675 let ring = &feature.polys[0][0];
676 assert!(ring.contains(&kept_bump), "{ring:?}");
678 assert!(!ring.contains(&dropped_bump), "{ring:?}");
680 }
681 let reconstructed_unweighted = {
683 let unweighted = build_topology_algorithm(&feats, Simplify::Rdp { epsilon: 0.01 });
684 unweighted.reconstruct(&feats, &unweighted.arc_coords)
685 };
686 assert!(!reconstructed_unweighted[0].polys[0][0].contains(&kept_bump));
687 }
688}