Skip to main content

utz_encode/
topo.rs

1//! The TopoJSON-style shared-arc topology builder. Shared borders are cut
2//! into *arcs* at junctions, each arc is stored ONCE as i24 delta+varint,
3//! and every ring is a list
4//! of signed arc references. Optional topology-aware Ramer–Douglas–Peucker
5//! (RDP) line simplification runs on each arc a single time (endpoints fixed),
6//! so neighbouring polygons stay stitched. Other open-polyline simplifiers
7//! could slot into the same per-arc pass.
8
9use std::collections::HashMap;
10
11use crate::{Arc, Feat};
12// simplification lives in utz_simplify (shared with the viz HTML via WASM)
13pub use utz_simplify::{Simplify, simplify};
14
15// quantization parameterized by bit-width (i16 abs, i24 abs, i32 abs, ...)
16use 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; // bytes per axis (i16->2, i24->3, i32->4)
19    out.extend_from_slice(&value.to_le_bytes()[0..byte_len]);
20}
21
22/// Zigzag-encodes a signed delta for [`put_varint()`]; the reader's
23/// inverse is `utz::format::unzigzag()`.
24#[must_use]
25pub fn zigzag(value: i64) -> u64 {
26    ((value << 1) ^ (value >> 63)).cast_unsigned()
27}
28/// Appends `value` as a varint, low 7 bits per byte with the high bit
29/// as continuation; the reader's inverse is `utz::format::read_varint()`.
30pub 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
44/// A serialized topology plus the counts and reconstructed geometry the
45/// measurement tools report on.
46pub struct TopoOut {
47    /// The serialized arc store (i24 delta+varint).
48    pub bytes: Vec<u8>,
49    /// The number of shared arcs stored.
50    pub arcs: usize,
51    /// The number of ring-to-arc references across all rings.
52    pub ring_refs: usize,
53    /// The number of vertices actually stored (after simplification).
54    pub verts: usize,
55    /// The geometry reconstructed from the (simplified) arcs.
56    pub simplified: Vec<Feat>,
57}
58
59/// The shared-arc topology itself, before any serialization: this is what
60/// the container encoder (encode.rs) consumes. Arc coords are f64 and
61/// already RDP-simplified.
62pub struct Topology {
63    pub arc_coords: Vec<Arc>,
64    /// The signed arc refs of each ring (`id << 1 | reversed`).
65    pub ring_refs: Vec<Vec<u32>>,
66    /// The feature → polygon → ring nesting; the innermost values index
67    /// into `ring_refs`.
68    pub structure: Vec<Vec<Vec<usize>>>,
69}
70
71impl Topology {
72    /// Reconstructs feature geometry from (possibly re-quantized) arc
73    /// coords.
74    #[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/// Builds and serializes the shared-arc topology at the default i24
117/// quantization: [`build_topology()`] runs first, followed by arc-store
118/// serialization.
119#[must_use]
120pub fn encode_topology(feats: &[Feat], epsilon_deg: f64) -> TopoOut {
121    encode_topology_q(feats, epsilon_deg, 24)
122}
123
124/// `qbits` selects the absolute grid: 16 gives i16 (~611 m lon), 24 gives
125/// i24 (~2.4 m), and 32 gives cm precision.
126#[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/// Builds the topology: vertices are deduped, shared arcs are cut at
132/// junctions, and topology-aware RDP runs on each arc exactly once with
133/// endpoints fixed.
134#[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/// This is [`build_topology()`] with the simplification algorithm as a knob
145/// (the `utz_simplify` menu: RDP, Visvalingam–Whyatt, Imai–Iri, or None).
146#[must_use]
147pub fn build_topology_algorithm(feats: &[Feat], algorithm: Simplify) -> Topology {
148    build_topology_impl(feats, algorithm, None)
149}
150
151/// This is [`build_topology_algorithm()`] with spatially varying tolerance:
152/// `edge_weight(a, b)`
153/// returns the tolerance multiplier for one arc edge (in practice
154/// `DensityWeight::weight(DensityGrid::max_along(a, b))`), and each vertex
155/// simplifies under the *smallest* multiplier of its incident edges, so a
156/// long edge crossing a dense area pins both flanking vertices. Weights are a
157/// pure function of arc geometry and every shared arc is simplified exactly
158/// once, so neighbouring zones stay stitched by construction.
159pub 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
167/// The tolerance multiplier for the edge `a`–`b` (see
168/// [`build_topology_weighted()`]).
169pub 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    // 1. dedup vertices (bit-exact) -> ids + coords
181    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    // 2. owner signature per undirected edge
215    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    // 3. cut rings into arcs at junctions; dedup arcs (sequence or reverse)
242    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            // junction-free closed ring (an island / lone hole): the same
278            // ring shared by two features (island outline = hole of the zone
279            // around it) must intern to ONE arc regardless of where each
280            // feature's ring starts or which way it winds. Canonical form =
281            // lexicographically smallest closed walk over BOTH directions
282            // from every occurrence of the smallest vertex id (a pinched
283            // ring can pass through it twice, and the per-direction lexmins
284            // can differ — picking only the forward one would make the two
285            // windings disagree). intern() gets the ring's own-winding walk
286            // so its direction bit still preserves ring orientation.
287            let min_vertex = *vertex_seq.iter().min().unwrap();
288            let mut best: Option<(Vec<VId>, bool)> = None; // (closed walk, forward here?)
289            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    // 4. arc coords (+ topology-aware simplification, each arc once)
329    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) // refine-only, endpoints kept anyway
352                        })
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/// `abs_fixed` stores arc vertices as fixed-width absolute ints
368/// (random-access) instead of the default delta + zigzag-varint stream.
369#[must_use]
370///
371/// # Panics
372/// Panics if a count or quantized coordinate exceeds its serialized width
373/// (u16 pool/poly counts, u32 arc ids, i32 coords).
374#[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    // 5. serialize
395    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    /// Two unit squares sharing the x=1 border, whose shared edge carries
516    /// interior vertices with 0.001 bumps (fodder for simplification).
517    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(); // (1,0) … (1,1), odd indices bumped east
526        let mut left: Ring = vec![(0.0, 0.0)];
527        left.extend(&shared); // up the shared border
528        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()); // down the shared border
531        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    /// An island whose outline is also the hole of the zone around it: the
540    /// same closed ring, but each feature starts it at a different vertex and
541    /// winds it the opposite way (exactly the Cyprus case). The topology must
542    /// intern that ring as ONE arc, not two rotated copies.
543    #[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        // same cycle, rotated to a different start and reversed
547        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        // sea outline + island ring shared once = 2 arcs, not 3
563        assert_eq!(
564            topology.arc_coords.len(),
565            2,
566            "island ring duplicated: {:?}",
567            topology.arc_coords
568        );
569        // reconstruction must still round-trip both features' ring vertex sets
570        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    /// A pinched (figure-eight) ring passes through its smallest vertex
591    /// twice, so the lexicographically smallest FORWARD rotation differs
592    /// between the two windings. Canonicalization must consider both walk
593    /// directions or the two features intern two different arcs.
594    #[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        // same cycle, reversed and rotated to a different start
605        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        // both rings still round-trip their vertex multiset
633        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        // "dense" stretch around y=0.5: edges whose midpoint falls in it get a
664        // small multiplier (0.05 * 0.01 = 0.0005 < the 0.001 bumps)
665        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            // the weighted stretch survives in BOTH zones (arc shared once)…
677            assert!(ring.contains(&kept_bump), "{ring:?}");
678            // …and the uniform-weight stretches still simplify away
679            assert!(!ring.contains(&dropped_bump), "{ring:?}");
680        }
681        // unweighted at the same epsilon drops every bump
682        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}