Skip to main content

utz_simplify/
lib.rs

1//! Open-polyline simplification algorithms, shared between the builder
2//! (`utz_build`, whose per-arc pass is topology-aware) and the tuning-viewer
3//! HTML (compiled to WASM so the browser preview runs the exact code the
4//! builder runs, with no JS reimplementation drift).
5//!
6//! All functions take an open polyline, always keep both endpoints, and return
7//! ≥ 2 points. Units are the caller's (the builder works in degrees; convert
8//! meters with ~111 320 m/deg and areas with its square). Three algorithms are
9//! on the menu:
10//!
11//! - [`rdp()`] is Ramer–Douglas–Peucker (Ramer 1972; Douglas & Peucker 1973),
12//!   which guarantees a max perpendicular deviation ≤ ε. It is the default.
13//! - [`visvalingam()`] is Visvalingam–Whyatt (1993), which iteratively drops
14//!   the point spanning the smallest triangle. Its parameter is an *area*, not
15//!   a distance: there is no ε-style deviation bound, but the result is often
16//!   a cartographically nicer caricature at the same vertex budget.
17//! - [`imai_iri()`] is Imai–Iri (1988), which finds the provably *minimum*
18//!   number of vertices for a given deviation bound ε (the shortest path over
19//!   the shortcut graph). It gives the same guarantee as RDP with
20//!   fewer-or-equal points and more build time.
21//!
22//! Corridor/streaming algorithms (Reumann–Witkam, Opheim, Lang, Zhao–Saalfeld)
23//! were considered and rejected: they trade quality-per-vertex for single-pass
24//! speed, which is worthless at build time.
25//!
26//! Each algorithm also has a weighted variant ([`simplify_weighted()`],
27//! `*_w`): a per-vertex tolerance multiplier `weights[i]` makes the effective
28//! parameter `epsilon * weights[i]` (for Visvalingam it is
29//! `min_area * weights[i]²`, because areas scale as distance²). The builder
30//! uses this for population-density-aware refinement: denser areas get smaller
31//! multipliers, so boundaries stay precise where people live.
32//! `weights[i] = 1.0` everywhere reproduces the scalar functions exactly.
33//!
34//! [`rdp()`]: ../utz_simplify/fn.rdp.html
35//! [`visvalingam()`]: ../utz_simplify/fn.visvalingam.html
36//! [`imai_iri()`]: ../utz_simplify/fn.imai_iri.html
37//! [`simplify_weighted()`]: ../utz_simplify/fn.simplify_weighted.html
38
39#[cfg(target_arch = "wasm32")]
40mod wasm;
41
42/// The algorithm choice and its parameter, for callers that thread the choice
43/// through knobs.
44#[derive(Clone, Copy, PartialEq, Debug)]
45pub enum Simplify {
46    /// Keeps every vertex.
47    None,
48    /// Ramer–Douglas–Peucker with a max deviation of `epsilon`.
49    Rdp { epsilon: f64 },
50    /// Visvalingam–Whyatt, which drops triangles smaller than `min_area`.
51    Visvalingam { min_area: f64 },
52    /// Imai–Iri minimum-vertex simplification within a max deviation of
53    /// `epsilon`.
54    ImaiIri { epsilon: f64 },
55}
56
57/// The algorithm codes [`Simplify::from_code()`] accepts, which are also
58/// the WASM exports' ABI ids. They match the header bytes of the asset
59/// format's `SimplifyAlgorithm` enum (`utz_common`), pinned by a
60/// dev-dependency test rather than a real dependency: this crate stays
61/// dependency-free.
62pub const ALGORITHM_NONE: u32 = 0;
63pub const ALGORITHM_RDP: u32 = 1;
64pub const ALGORITHM_VISVALINGAM: u32 = 2;
65pub const ALGORITHM_IMAI_IRI: u32 = 3;
66
67impl Simplify {
68    /// The algorithm an [`ALGORITHM_NONE`]-family code names, carrying
69    /// `param` as the algorithm's own parameter: a max deviation ε for
70    /// RDP and Imai–Iri, a minimum triangle area for Visvalingam. No ε²
71    /// derivation happens here; an ε-driven caller applies that policy
72    /// itself (see `utz_encode::encode::to_simplify()`). An unknown code
73    /// simplifies as [`Simplify::None`], so coordinates pass through.
74    #[must_use]
75    pub fn from_code(code: u32, param: f64) -> Simplify {
76        match code {
77            ALGORITHM_RDP => Simplify::Rdp { epsilon: param },
78            ALGORITHM_VISVALINGAM => Simplify::Visvalingam { min_area: param },
79            ALGORITHM_IMAI_IRI => Simplify::ImaiIri { epsilon: param },
80            _ => Simplify::None,
81        }
82    }
83}
84
85/// Dispatches on [`Simplify`].
86#[must_use]
87pub fn simplify(algorithm: Simplify, points: &[(f64, f64)]) -> Vec<(f64, f64)> {
88    match algorithm {
89        Simplify::None => points.to_vec(),
90        Simplify::Rdp { epsilon } => rdp(points, epsilon),
91        Simplify::Visvalingam { min_area } => visvalingam(points, min_area),
92        Simplify::ImaiIri { epsilon } => imai_iri(points, epsilon),
93    }
94}
95
96/// [`simplify()`] with per-vertex tolerance multipliers: the effective
97/// parameter at `points[i]` is `param * weights[i]` (for Visvalingam,
98/// `min_area * weights[i]²`). Callers pass one strictly positive weight per
99/// point; all-ones weights reproduce [`simplify()`].
100///
101/// # Panics
102///
103/// Panics if `points.len() != weights.len()`.
104#[must_use]
105pub fn simplify_weighted(
106    algorithm: Simplify,
107    points: &[(f64, f64)],
108    weights: &[f64],
109) -> Vec<(f64, f64)> {
110    assert_eq!(points.len(), weights.len(), "one weight per point");
111    match algorithm {
112        Simplify::None => points.to_vec(),
113        Simplify::Rdp { epsilon } => rdp_w(points, epsilon, weights),
114        Simplify::Visvalingam { min_area } => visvalingam_w(points, min_area, weights),
115        Simplify::ImaiIri { epsilon } => imai_iri_w(points, epsilon, weights),
116    }
117}
118
119/// The map from population density to tolerance multiplier: the
120/// [`weight()`](Self::weight) method takes a density in people/km² and
121/// returns the multiplier to apply to the simplification tolerance there.
122/// The map is shared by the builder and the live viewer (it is compiled
123/// into the WASM module so the browser's weighting slider runs the same
124/// code).
125///
126/// [`weight()`](Self::weight) evaluates a piecewise curve over density `d`,
127/// shaped by two knees (`d_lo`, `d_hi`) and a floor (`w_min`):
128///
129/// - Below `d_lo` the weight is 1, leaving the baseline tolerance
130///   untouched. Oceans, deserts, and other empty areas therefore simplify
131///   exactly as they would unweighted, so enabling weighting causes zero
132///   size regression there.
133/// - Above `d_hi` the weight saturates at `w_min`, giving city cores the
134///   finest tolerance the model allows (with `w_min = 0.1`, one tenth of
135///   the baseline).
136/// - Between the knees the curve is the power law
137///   `weight(d) = (d / d_lo)^-k`, which is a straight line in log-log
138///   space. The exponent `k = ln(1/w_min) / ln(d_hi/d_lo)` is the unique
139///   one that meets both knees continuously. A power law fits because
140///   population density spans orders of magnitude: each doubling of
141///   density tightens the weight by the same factor, rather than spending
142///   the whole ramp on the first sliver of the range as a linear
143///   interpolation would.
144///
145/// Every weight is ≤ 1, so the map only ever refines: weighted
146/// simplification keeps at least the boundary detail of the unweighted
147/// baseline and adds more where people live.
148#[derive(Clone, Copy, PartialEq, Debug)]
149pub struct DensityWeight {
150    /// The multiplier at saturation (0.1 gives dense areas one tenth the
151    /// epsilon).
152    pub w_min: f64,
153    /// The density (people/km²) below which the weight stays 1.
154    pub d_lo: f64,
155    /// The density above which the weight saturates at `w_min`.
156    pub d_hi: f64,
157}
158
159impl DensityWeight {
160    /// The default for `d_lo`: below ~5 people/km², nobody is misassigned
161    /// that matters.
162    pub const DEFAULT_D_LO: f64 = 5.0;
163    /// The default for `d_hi`: ~2000 people/km² is already a dense city.
164    pub const DEFAULT_D_HI: f64 = 2000.0;
165
166    #[must_use]
167    pub fn new(w_min: f64) -> Self {
168        Self {
169            w_min,
170            d_lo: Self::DEFAULT_D_LO,
171            d_hi: Self::DEFAULT_D_HI,
172        }
173    }
174
175    /// Returns the tolerance multiplier ∈ [`w_min`, 1] for a density in
176    /// people/km². A NaN density or `w_min ≥ 1` returns 1, which turns
177    /// weighting off.
178    #[must_use]
179    pub fn weight(&self, density: f64) -> f64 {
180        if density.is_nan() || density <= self.d_lo || self.w_min >= 1.0 {
181            return 1.0;
182        }
183        if density >= self.d_hi {
184            return self.w_min;
185        }
186        let k = self.w_min.recip().ln() / (self.d_hi / self.d_lo).ln();
187        (density / self.d_lo).powf(-k).clamp(self.w_min, 1.0)
188    }
189}
190
191/// The squared distance from `p` to the segment `a`–`b`.
192fn seg_dist2(p: (f64, f64), a: (f64, f64), b: (f64, f64)) -> f64 {
193    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
194    let len2 = dx * dx + dy * dy;
195    if len2 == 0.0 {
196        return (p.0 - a.0).powi(2) + (p.1 - a.1).powi(2);
197    }
198    let t = (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / len2).clamp(0.0, 1.0);
199    let (cx, cy) = (a.0 + t * dx, a.1 + t * dy);
200    (p.0 - cx).powi(2) + (p.1 - cy).powi(2)
201}
202
203/// Runs Ramer–Douglas–Peucker, keeping both endpoints; the result has
204/// ≥ 2 points.
205#[must_use]
206pub fn rdp(points: &[(f64, f64)], epsilon: f64) -> Vec<(f64, f64)> {
207    if points.len() < 3 || epsilon <= 0.0 {
208        return points.to_vec();
209    }
210    let e2 = epsilon * epsilon;
211    rdp_mark(points, |_| e2)
212        .into_iter()
213        .filter_map(|vertex| vertex.kept.then_some(vertex.point))
214        .collect()
215}
216
217/// [`rdp()`] with per-vertex multipliers: the deviation at `points[i]` stays
218/// ≤ `epsilon * weights[i]`.
219///
220/// # Panics
221///
222/// Panics if `points.len() != weights.len()`.
223#[must_use]
224pub fn rdp_w(points: &[(f64, f64)], epsilon: f64, weights: &[f64]) -> Vec<(f64, f64)> {
225    assert_eq!(points.len(), weights.len(), "one weight per point");
226    if points.len() < 3 || epsilon <= 0.0 {
227        return points.to_vec();
228    }
229    rdp_mark(points, |i| (epsilon * weights[i]).powi(2))
230        .into_iter()
231        .filter_map(|vertex| vertex.kept.then_some(vertex.point))
232        .collect()
233}
234
235/// One working vertex of the RDP pass: the point, its squared tolerance,
236/// and whether the pass keeps it.
237struct RdpVertex {
238    point: (f64, f64),
239    e2: f64,
240    kept: bool,
241}
242
243/// Runs RDP and returns every vertex with its `kept` flag set (the Imai–Iri
244/// prefilter needs kept points mapped back to original indices, so nothing
245/// is dropped here). `e2_of(i)` gives the squared tolerance at `points[i]`.
246fn rdp_mark(points: &[(f64, f64)], e2_of: impl Fn(usize) -> f64) -> Vec<RdpVertex> {
247    let mut vertices: Vec<RdpVertex> = points
248        .iter()
249        .enumerate()
250        .map(|(i, &point)| RdpVertex {
251            point,
252            e2: e2_of(i),
253            kept: false,
254        })
255        .collect();
256    vertices.first_mut().unwrap().kept = true;
257    vertices.last_mut().unwrap().kept = true;
258    rdp_recurse(&mut vertices);
259    vertices
260}
261
262/// The recursive core: `vertices` spans one shortcut segment, endpoint to
263/// endpoint, and both endpoints are already kept.
264fn rdp_recurse(vertices: &mut [RdpVertex]) {
265    let [start, interior @ .., end] = &*vertices else {
266        return;
267    };
268    let (start, end) = (start.point, end.point);
269    // farthest point, measured in units of its own tolerance; an empty
270    // interior leaves the ratio at 0, which ends the recursion below.
271    // zipping (1..) indexes each vertex by its position in `vertices` (the
272    // split below needs that), not its position in `interior`
273    let (mut farthest_index, mut farthest_ratio) = (0, 0.0);
274    for (i, vertex) in (1..).zip(interior) {
275        let ratio = seg_dist2(vertex.point, start, end) / vertex.e2;
276        if ratio > farthest_ratio {
277            farthest_ratio = ratio;
278            farthest_index = i;
279        }
280    }
281    if farthest_ratio > 1.0 {
282        vertices[farthest_index].kept = true;
283        rdp_recurse(&mut vertices[..=farthest_index]);
284        rdp_recurse(&mut vertices[farthest_index..]);
285    }
286}
287
288/// Runs Visvalingam–Whyatt: it repeatedly removes the interior point whose
289/// triangle (prev, point, next) has the smallest area, while that area is
290/// < `min_area`. Ties break on the lower index for reproducible builds.
291#[must_use]
292pub fn visvalingam(points: &[(f64, f64)], min_area: f64) -> Vec<(f64, f64)> {
293    vw_impl(points, min_area, |_| 1.0)
294}
295
296/// [`visvalingam()`] with per-vertex multipliers: `points[i]` is dropped while
297/// its triangle area is < `min_area * weights[i]²` (areas scale as
298/// distance²).
299///
300/// # Panics
301///
302/// Panics if `points.len() != weights.len()`.
303#[must_use]
304pub fn visvalingam_w(points: &[(f64, f64)], min_area: f64, weights: &[f64]) -> Vec<(f64, f64)> {
305    assert_eq!(points.len(), weights.len(), "one weight per point");
306    vw_impl(points, min_area, |i| weights[i] * weights[i])
307}
308
309/// A heap entry for [`vw_impl()`]; the max-heap is ordered by a Reverse-style
310/// negated comparison so the smallest effective area pops first.
311#[derive(PartialEq)]
312struct VwEntry {
313    area: f64,
314    index: usize,
315    stamp: u32,
316}
317impl Eq for VwEntry {}
318impl Ord for VwEntry {
319    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
320        // BinaryHeap is a max-heap: invert so the smallest area pops first
321        other
322            .area
323            .total_cmp(&self.area)
324            .then(other.index.cmp(&self.index))
325    }
326}
327impl PartialOrd for VwEntry {
328    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
329        Some(self.cmp(other))
330    }
331}
332
333/// One working vertex of the VW pass: the point, its squared weight, its
334/// neighbors in the doubly linked list of surviving vertices, and the
335/// liveness/staleness state the heap entries are checked against. The
336/// endpoint sentinels (`previous` of the first vertex, `next` of the last)
337/// are out of bounds but never followed, because endpoints are never
338/// removed.
339struct VwVertex {
340    point: (f64, f64),
341    w2: f64,
342    previous: usize,
343    next: usize,
344    alive: bool,
345    stamp: u32,
346}
347
348/// The shared VW core: heap entries hold the *effective* area
349/// `triangle_area / w2`, compared against the unscaled `min_area` (division
350/// by 1.0 is bit-exact, so the scalar path is unchanged).
351fn vw_impl(points: &[(f64, f64)], min_area: f64, w2_of: impl Fn(usize) -> f64) -> Vec<(f64, f64)> {
352    let n = points.len();
353    if n < 3 || min_area <= 0.0 {
354        return points.to_vec();
355    }
356    let triangle_area = |a: (f64, f64), b: (f64, f64), c: (f64, f64)| -> f64 {
357        0.5 * ((b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)).abs()
358    };
359    let mut vertices: Vec<VwVertex> = points
360        .iter()
361        .enumerate()
362        .map(|(i, &point)| VwVertex {
363            point,
364            w2: w2_of(i),
365            previous: i.wrapping_sub(1),
366            next: i + 1,
367            alive: true,
368            stamp: 0,
369        })
370        .collect();
371    let effective_area = |vertices: &[VwVertex], i: usize| -> f64 {
372        let vertex = &vertices[i];
373        triangle_area(
374            vertices[vertex.previous].point,
375            vertex.point,
376            vertices[vertex.next].point,
377        ) / vertex.w2
378    };
379
380    let mut heap = std::collections::BinaryHeap::with_capacity(n);
381    for i in 1..n - 1 {
382        heap.push(VwEntry {
383            area: effective_area(&vertices, i),
384            index: i,
385            stamp: 0,
386        });
387    }
388    while let Some(entry) = heap.pop() {
389        if !vertices[entry.index].alive || entry.stamp != vertices[entry.index].stamp {
390            continue; // stale entry
391        }
392        if entry.area >= min_area {
393            break;
394        }
395        vertices[entry.index].alive = false;
396        let (previous_index, next_index) =
397            (vertices[entry.index].previous, vertices[entry.index].next);
398        vertices[previous_index].next = next_index;
399        vertices[next_index].previous = previous_index;
400        for neighbor in [previous_index, next_index] {
401            if neighbor != 0 && neighbor != n - 1 {
402                vertices[neighbor].stamp += 1;
403                heap.push(VwEntry {
404                    area: effective_area(&vertices, neighbor),
405                    index: neighbor,
406                    stamp: vertices[neighbor].stamp,
407                });
408            }
409        }
410    }
411    vertices
412        .into_iter()
413        .filter_map(|vertex| vertex.alive.then_some(vertex.point))
414        .collect()
415}
416
417/// Runs Imai–Iri: it returns the minimum-vertex polyline whose deviation from
418/// `points` is ≤ `epsilon` (a BFS finds the fewest hops from the first to the last
419/// point over the graph of "shortcut" segments that stay within `epsilon` of
420/// every skipped point).
421///
422/// The exact core is ~O(n²) (Chan–Chin wedges, O(1) amortized per shortcut
423/// check); very long inputs are RDP prefiltered with an *adaptive* slice of
424/// the budget: the prefilter starts at `epsilon/10` (Imai–Iri's vertex count is
425/// driven by its share, so it gets as much as possible: an even split kept
426/// MORE points than plain RDP on real arcs) and escalates toward the `epsilon/2`
427/// cap only while the prefiltered arc stays too big. Deviation bounds
428/// compose, so the total stays ≤ `epsilon`; prefiltered results are near-optimal
429/// rather than optimal.
430#[must_use]
431pub fn imai_iri(points: &[(f64, f64)], epsilon: f64) -> Vec<(f64, f64)> {
432    if points.len() < 3 || epsilon <= 0.0 {
433        return points.to_vec();
434    }
435    if points.len() <= II_MAX {
436        return imai_iri_core(points, |_| epsilon);
437    }
438    let mut pre_epsilon = epsilon * 0.1;
439    loop {
440        let prefiltered = rdp(points, pre_epsilon);
441        if prefiltered.len() <= 2 * II_MAX || pre_epsilon >= epsilon * 0.5 {
442            let rest = epsilon - pre_epsilon;
443            return imai_iri_core(&prefiltered, |_| rest);
444        }
445        pre_epsilon = (pre_epsilon * 2.0).min(epsilon * 0.5);
446    }
447}
448
449/// Caps the lazy backward-row bitsets at `2·II_MAX` points, ≈ 32 MB of
450/// transient memory.
451const II_MAX: usize = 8192;
452
453/// [`imai_iri()`] with per-vertex multipliers: the deviation at `points[i]`
454/// stays ≤ `epsilon * weights[i]`. Above `II_MAX` points the RDP prefilter
455/// composes per point, so that bound is exact only where `weights` is locally
456/// ~constant across a prefilter shortcut (a negligible caveat for weights
457/// sampled from a coarse grid through a smooth map); the global
458/// `epsilon * max(weights)` bound always holds.
459///
460/// # Panics
461///
462/// Panics if `points.len() != weights.len()`.
463#[must_use]
464pub fn imai_iri_w(points: &[(f64, f64)], epsilon: f64, weights: &[f64]) -> Vec<(f64, f64)> {
465    assert_eq!(points.len(), weights.len(), "one weight per point");
466    if points.len() < 3 || epsilon <= 0.0 {
467        return points.to_vec();
468    }
469    if points.len() <= II_MAX {
470        return imai_iri_core(points, |i| epsilon * weights[i]);
471    }
472    // mirrors the scalar adaptive prefilter arithmetic exactly, so all-ones
473    // weights stay bit-identical to imai_iri
474    let mut pre_epsilon = epsilon * 0.1;
475    loop {
476        let vertices = rdp_mark(points, |i| (pre_epsilon * weights[i]).powi(2));
477        let kept_count = vertices.iter().filter(|vertex| vertex.kept).count();
478        if kept_count <= 2 * II_MAX || pre_epsilon >= epsilon * 0.5 {
479            let kept_indices: Vec<usize> = vertices
480                .iter()
481                .enumerate()
482                .filter_map(|(i, vertex)| vertex.kept.then_some(i))
483                .collect();
484            let prefiltered: Vec<(f64, f64)> = kept_indices.iter().map(|&i| points[i]).collect();
485            let rest = epsilon - pre_epsilon;
486            return imai_iri_core(&prefiltered, |prefiltered_index| {
487                rest * weights[kept_indices[prefiltered_index]]
488            });
489        }
490        pre_epsilon = (pre_epsilon * 2.0).min(epsilon * 0.5);
491    }
492}
493
494/// An angular interval of directions, ≤ π wide and shrinking under
495/// intersection: `u` is inside iff `cross(lo, u) ≥ 0 ∧ cross(u, hi) ≥ 0`.
496struct Wedge {
497    lo: (f64, f64),
498    hi: (f64, f64),
499    any: bool,   // no constraint yet — full circle
500    empty: bool, // intersection pinched shut — nothing valid beyond here
501}
502
503fn cross(a: (f64, f64), b: (f64, f64)) -> f64 {
504    a.0 * b.1 - a.1 * b.0
505}
506
507impl Wedge {
508    fn new() -> Self {
509        Wedge {
510            lo: (0.0, 0.0),
511            hi: (0.0, 0.0),
512            any: true,
513            empty: false,
514        }
515    }
516    /// Intersects with the wedge of directions whose ray from the anchor
517    /// passes within ε of a point at unit direction `center`; `sin_phi` is
518    /// ε/dist.
519    fn add(&mut self, center: (f64, f64), sin_phi: f64) {
520        let cos_phi = (1.0 - sin_phi * sin_phi).max(0.0).sqrt();
521        let lo = (
522            center.0 * cos_phi + center.1 * sin_phi,
523            -center.0 * sin_phi + center.1 * cos_phi,
524        );
525        let hi = (
526            center.0 * cos_phi - center.1 * sin_phi,
527            center.0 * sin_phi + center.1 * cos_phi,
528        );
529        if self.any {
530            (self.lo, self.hi, self.any) = (lo, hi, false);
531            return;
532        }
533        // Two arcs each ≤ π wide intersect iff an endpoint of one lies inside
534        // the other; when they do, the intersection is [ccw-most start,
535        // cw-most end] by MEMBERSHIP, not by pairwise cross comparison — a
536        // disjoint interval > 180° away otherwise slips through unchanged.
537        let in_current = |u: (f64, f64)| cross(self.lo, u) >= 0.0 && cross(u, self.hi) >= 0.0;
538        let in_new = |u: (f64, f64)| cross(lo, u) >= 0.0 && cross(u, hi) >= 0.0;
539        let (lo_in, hi_in) = (in_current(lo), in_current(hi));
540        if !(lo_in || hi_in || in_new(self.lo)) {
541            self.empty = true;
542            return;
543        }
544        if lo_in {
545            self.lo = lo;
546        }
547        if hi_in {
548            self.hi = hi;
549        }
550        // float-slop safety: a hairline wedge may come out inverted — treat
551        // as empty (rejects a valid shortcut at worst, never accepts a bad one)
552        if cross(self.lo, self.hi) < 0.0 {
553            self.empty = true;
554        }
555    }
556    fn contains(&self, direction: (f64, f64)) -> bool {
557        !self.empty
558            && (self.any || (cross(self.lo, direction) >= 0.0 && cross(direction, self.hi) >= 0.0))
559    }
560}
561
562/// Runs the ray-validity sweep from `points[from]`: it walks `ks` (the
563/// intermediate points in sweep order), calling `visit(k_target, ok)` where
564/// `ok` holds iff the ray from `points[from]` toward `points[k_target]` stays
565/// within ε of every point already swept.
566/// `dist(p_k, seg(i,j)) ≤ ε_k ⟺ ray-from-i ok ∧ ray-from-j ok`, so two
567/// sweeps decide segment validity exactly. The Chan–Chin lemma is pointwise
568/// in `k`, so each point may carry its own tolerance `epsilon_of(k)`.
569fn ray_sweep(
570    points: &[(f64, f64)],
571    from: usize,
572    ks: impl Iterator<Item = usize>,
573    epsilon_of: impl Fn(usize) -> f64 + Copy,
574    mut visit: impl FnMut(usize, bool) -> bool,
575) {
576    let anchor = points[from];
577    let mut wedge = Wedge::new();
578    let mut has_far = false; // some swept point is > its ε from the anchor
579    for k in ks {
580        let delta = (points[k].0 - anchor.0, points[k].1 - anchor.1);
581        let ok = if delta == (0.0, 0.0) {
582            !has_far
583        } else {
584            wedge.contains(delta)
585        };
586        if !visit(k, ok) {
587            return;
588        }
589        // fold k into the constraints for the points swept after it
590        let dist = (delta.0 * delta.0 + delta.1 * delta.1).sqrt();
591        let epsilon_k = epsilon_of(k);
592        if dist > epsilon_k {
593            has_far = true;
594            wedge.add((delta.0 / dist, delta.1 / dist), epsilon_k / dist);
595            if wedge.empty {
596                // constraints only accumulate — nothing further can be valid
597                while visit(usize::MAX, false) {}
598                return;
599            }
600        }
601    }
602}
603
604fn imai_iri_core(
605    points: &[(f64, f64)],
606    epsilon_of: impl Fn(usize) -> f64 + Copy,
607) -> Vec<(f64, f64)> {
608    let n = points.len();
609    let words = n.div_ceil(64);
610    // lazily computed backward rows: bit i of row j ⟺ ray from p_j toward
611    // p_i stays within ε of every point strictly between i and j
612    let mut backward_rows: Vec<Option<Vec<u64>>> = vec![None; n];
613    let backward_row = |j: usize| -> Vec<u64> {
614        let mut bits = vec![0u64; words];
615        ray_sweep(points, j, (0..j).rev(), epsilon_of, |i, ok| {
616            if i != usize::MAX && ok {
617                bits[i / 64] |= 1 << (i % 64);
618            }
619            i != usize::MAX && i > 0
620        });
621        bits
622    };
623
624    // BFS level by level: first time a node is reached = fewest hops
625    let mut parent = vec![usize::MAX; n];
626    let mut frontier = vec![0usize];
627    parent[0] = 0;
628    'bfs: while !frontier.is_empty() {
629        let mut next_frontier = Vec::new();
630        for &i in &frontier {
631            let mut done = false;
632            ray_sweep(points, i, i + 1..n, epsilon_of, |j, forward_ok| {
633                if j == usize::MAX {
634                    return false; // wedge pinched shut — stop this sweep
635                }
636                if forward_ok && parent[j] == usize::MAX {
637                    let row = backward_rows[j].get_or_insert_with(|| backward_row(j));
638                    if row[i / 64] >> (i % 64) & 1 == 1 {
639                        parent[j] = i;
640                        if j == n - 1 {
641                            done = true;
642                            return false;
643                        }
644                        next_frontier.push(j);
645                    }
646                }
647                true
648            });
649            if done {
650                break 'bfs;
651            }
652        }
653        frontier = next_frontier;
654    }
655    let mut path = vec![n - 1];
656    while *path.last().unwrap() != 0 {
657        path.push(parent[*path.last().unwrap()]);
658    }
659    path.iter().rev().map(|&i| points[i]).collect()
660}
661
662#[cfg(test)]
663mod tests {
664    use super::*;
665
666    #[test]
667    fn algorithm_codes_match_the_header_bytes() {
668        use utz_common::SimplifyAlgorithm;
669        assert_eq!(ALGORITHM_NONE, SimplifyAlgorithm::None as u32);
670        assert_eq!(ALGORITHM_RDP, SimplifyAlgorithm::Rdp as u32);
671        assert_eq!(ALGORITHM_VISVALINGAM, SimplifyAlgorithm::Visvalingam as u32);
672        assert_eq!(ALGORITHM_IMAI_IRI, SimplifyAlgorithm::ImaiIri as u32);
673    }
674
675    /// deterministic pseudo-random polyline (LCG, same recipe as pip tests)
676    fn wiggle(n: usize, seed: u64) -> Vec<(f64, f64)> {
677        let mut lcg = utz_common::Lcg::new(seed);
678        (0..n)
679            .map(
680                #[expect(
681                    clippy::cast_precision_loss,
682                    reason = "i < n ≤ II_MAX+2000 ≪ 2^53; test x-spacing"
683                )]
684                |i| (i as f64 * 0.1, lcg.unit_f64() * 2.0 - 1.0),
685            )
686            .collect()
687    }
688
689    fn max_deviation(original: &[(f64, f64)], simplified: &[(f64, f64)]) -> f64 {
690        // every original point must be near some simplified segment
691        original
692            .iter()
693            .map(|&point| {
694                simplified
695                    .windows(2)
696                    .map(|window| seg_dist2(point, window[0], window[1]))
697                    .fold(f64::INFINITY, f64::min)
698            })
699            .fold(0.0, f64::max)
700            .sqrt()
701    }
702
703    #[test]
704    fn endpoints_always_kept() {
705        let points = wiggle(50, 1);
706        for out in [
707            rdp(&points, 0.5),
708            visvalingam(&points, 0.5),
709            imai_iri(&points, 0.5),
710        ] {
711            assert_eq!(out.first(), points.first());
712            assert_eq!(out.last(), points.last());
713            assert!(out.len() >= 2);
714        }
715    }
716
717    #[test]
718    fn collinear_collapses() {
719        let line: Vec<(f64, f64)> = (0..10).map(|i| (f64::from(i), 0.0)).collect();
720        assert_eq!(rdp(&line, 0.01).len(), 2);
721        assert_eq!(visvalingam(&line, 0.01).len(), 2);
722        assert_eq!(imai_iri(&line, 0.01).len(), 2);
723    }
724
725    #[test]
726    fn spike_survives() {
727        let mut line: Vec<(f64, f64)> = (0..10).map(|i| (f64::from(i), 0.0)).collect();
728        line[5] = (5.0, 3.0);
729        assert!(rdp(&line, 0.5).contains(&(5.0, 3.0)));
730        assert!(visvalingam(&line, 0.5).contains(&(5.0, 3.0)));
731        // imai_iri may route around the spike's neighbours but must stay in bound
732        assert!(max_deviation(&line, &imai_iri(&line, 0.5)) <= 0.5 + 1e-12);
733    }
734
735    #[test]
736    fn epsilon_bound_honored() {
737        for seed in 1..=20u64 {
738            let points = wiggle(200, seed);
739            for epsilon in [0.05, 0.2, 0.8] {
740                assert!(
741                    max_deviation(&points, &rdp(&points, epsilon)) <= epsilon + 1e-12,
742                    "rdp seed {seed}"
743                );
744                assert!(
745                    max_deviation(&points, &imai_iri(&points, epsilon)) <= epsilon + 1e-12,
746                    "ii seed {seed}"
747                );
748            }
749        }
750    }
751
752    #[test]
753    fn imai_iri_never_more_verts_than_rdp() {
754        for seed in 1..=20u64 {
755            let points = wiggle(200, seed);
756            for epsilon in [0.05, 0.2, 0.8] {
757                let (rdp_len, imai_iri_len) = (
758                    rdp(&points, epsilon).len(),
759                    imai_iri(&points, epsilon).len(),
760                );
761                assert!(
762                    imai_iri_len <= rdp_len,
763                    "seed {seed} epsilon {epsilon}: imai-iri {imai_iri_len} > rdp {rdp_len}"
764                );
765            }
766        }
767    }
768
769    #[test]
770    fn imai_iri_optimal_vs_bruteforce() {
771        // exhaustively check minimality on small inputs
772        fn brute_min(points: &[(f64, f64)], e2: f64) -> usize {
773            let n = points.len();
774            // BFS is the definition of minimal; validate against subset search
775            for keep in 2..=n {
776                // try all interior subsets of size keep-2
777                fn combos(n: usize, k: usize) -> Vec<Vec<usize>> {
778                    if k == 0 {
779                        return vec![vec![]];
780                    }
781                    let mut out = Vec::new();
782                    for first in 1..n - 1 {
783                        for mut rest in combos(n, k - 1) {
784                            if rest.first().is_none_or(|&index| index > first) {
785                                rest.insert(0, first);
786                                out.push(rest);
787                            }
788                        }
789                    }
790                    out
791                }
792                for interior in combos(n, keep - 2) {
793                    let mut indices = vec![0];
794                    indices.extend(interior);
795                    indices.push(n - 1);
796                    let ok = indices.windows(2).all(|window| {
797                        points[window[0] + 1..window[1]].iter().all(|&point| {
798                            seg_dist2(point, points[window[0]], points[window[1]]) <= e2
799                        })
800                    });
801                    if ok {
802                        return keep;
803                    }
804                }
805            }
806            n
807        }
808        for seed in 1..=10u64 {
809            let points = wiggle(9, seed);
810            for epsilon in [0.1, 0.4, 1.0] {
811                let imai_iri_len = imai_iri(&points, epsilon).len();
812                let optimal_len = brute_min(&points, epsilon * epsilon);
813                assert_eq!(imai_iri_len, optimal_len, "seed {seed} epsilon {epsilon}");
814            }
815        }
816    }
817
818    #[test]
819    fn visvalingam_monotone_in_threshold() {
820        let points = wiggle(200, 7);
821        let mut last = usize::MAX;
822        for min_area in [0.001, 0.01, 0.1, 1.0] {
823            let n = visvalingam(&points, min_area).len();
824            assert!(n <= last);
825            last = n;
826        }
827    }
828
829    #[test]
830    fn dispatch_matches_direct() {
831        let points = wiggle(100, 3);
832        assert_eq!(simplify(Simplify::None, &points), points);
833        assert_eq!(
834            simplify(Simplify::Rdp { epsilon: 0.2 }, &points),
835            rdp(&points, 0.2)
836        );
837        assert_eq!(
838            simplify(Simplify::Visvalingam { min_area: 0.2 }, &points),
839            visvalingam(&points, 0.2)
840        );
841        assert_eq!(
842            simplify(Simplify::ImaiIri { epsilon: 0.2 }, &points),
843            imai_iri(&points, 0.2)
844        );
845    }
846
847    /// naive O(n) per-check BFS: the reference the wedge core must match
848    fn imai_iri_naive(points: &[(f64, f64)], epsilon: f64) -> Vec<(f64, f64)> {
849        let n = points.len();
850        let e2 = epsilon * epsilon;
851        let valid = |i: usize, j: usize| {
852            points[i + 1..j]
853                .iter()
854                .all(|&point| seg_dist2(point, points[i], points[j]) <= e2)
855        };
856        let mut parent = vec![usize::MAX; n];
857        let mut frontier = vec![0usize];
858        parent[0] = 0;
859        'bfs: while !frontier.is_empty() {
860            let mut next_frontier = Vec::new();
861            for &i in &frontier {
862                for (j, parent_entry) in parent.iter_mut().enumerate().skip(i + 1) {
863                    if *parent_entry == usize::MAX && valid(i, j) {
864                        *parent_entry = i;
865                        if j == n - 1 {
866                            break 'bfs;
867                        }
868                        next_frontier.push(j);
869                    }
870                }
871            }
872            frontier = next_frontier;
873        }
874        let mut path = vec![n - 1];
875        while *path.last().unwrap() != 0 {
876            path.push(parent[*path.last().unwrap()]);
877        }
878        path.iter().rev().map(|&i| points[i]).collect()
879    }
880
881    #[test]
882    fn wedge_core_matches_naive() {
883        // the disjoint-interval wraparound bug needed n ≈ thousands to
884        // surface — cover both small and large inputs
885        for seed in 1..=30u64 {
886            let points = wiggle(400, seed);
887            for epsilon in [0.03, 0.1, 0.3, 0.9] {
888                let (wedge_len, naive_len) = (
889                    imai_iri_core(&points, |_| epsilon).len(),
890                    imai_iri_naive(&points, epsilon).len(),
891                );
892                assert_eq!(
893                    wedge_len, naive_len,
894                    "seed {seed} epsilon {epsilon}: wedge {wedge_len} != naive {naive_len}"
895                );
896            }
897        }
898        for seed in 1..=3u64 {
899            let points = wiggle(3000, seed);
900            for epsilon in [0.3, 0.9] {
901                let (wedge_len, naive_len) = (
902                    imai_iri_core(&points, |_| epsilon).len(),
903                    imai_iri_naive(&points, epsilon).len(),
904                );
905                assert_eq!(
906                    wedge_len, naive_len,
907                    "seed {seed} epsilon {epsilon} (n=3000): wedge {wedge_len} != naive {naive_len}"
908                );
909            }
910        }
911    }
912
913    #[test]
914    fn long_arc_prefilter_keeps_bound() {
915        let points = wiggle(II_MAX + 2000, 11); // > II_MAX → adaptive rdp prefilter + core
916        let epsilon = 0.3;
917        let out = imai_iri(&points, epsilon);
918        assert!(max_deviation(&points, &out) <= epsilon + 1e-12);
919        assert!(out.len() < points.len());
920    }
921
922    /// distance from one original point to the simplified polyline
923    fn point_dev(point: (f64, f64), simplified: &[(f64, f64)]) -> f64 {
924        simplified
925            .windows(2)
926            .map(|window| seg_dist2(point, window[0], window[1]))
927            .fold(f64::INFINITY, f64::min)
928            .sqrt()
929    }
930
931    /// deterministic pseudo-random weights in [lo, 1]
932    fn rand_weights(n: usize, lo: f64, seed: u64) -> Vec<f64> {
933        let mut lcg = utz_common::Lcg::new(seed);
934        (0..n).map(|_| lo + (1.0 - lo) * lcg.unit_f64()).collect()
935    }
936
937    #[test]
938    fn weighted_uniform_matches_scalar() {
939        for seed in 1..=10u64 {
940            let points = wiggle(300, seed);
941            let ones = vec![1.0; points.len()];
942            for epsilon in [0.05, 0.2, 0.8] {
943                assert_eq!(
944                    rdp_w(&points, epsilon, &ones),
945                    rdp(&points, epsilon),
946                    "rdp seed {seed}"
947                );
948                assert_eq!(
949                    visvalingam_w(&points, epsilon, &ones),
950                    visvalingam(&points, epsilon),
951                    "vw seed {seed}"
952                );
953                assert_eq!(
954                    imai_iri_w(&points, epsilon, &ones),
955                    imai_iri(&points, epsilon),
956                    "ii seed {seed}"
957                );
958            }
959        }
960        // prefilter path: the weighted adaptive loop mirrors the scalar one
961        let points = wiggle(II_MAX + 2000, 5);
962        let ones = vec![1.0; points.len()];
963        assert_eq!(imai_iri_w(&points, 0.3, &ones), imai_iri(&points, 0.3));
964    }
965
966    #[test]
967    fn weighted_per_point_bound() {
968        // n ≤ II_MAX so the imai-iri bound is exact (no prefilter composition)
969        for seed in 1..=10u64 {
970            let points = wiggle(300, seed);
971            let weights = rand_weights(points.len(), 0.1, seed);
972            let epsilon = 0.4;
973            for out in [
974                rdp_w(&points, epsilon, &weights),
975                imai_iri_w(&points, epsilon, &weights),
976            ] {
977                for (i, &point) in points.iter().enumerate() {
978                    let (deviation, bound) = (point_dev(point, &out), epsilon * weights[i]);
979                    assert!(
980                        deviation <= bound + 1e-12,
981                        "seed {seed} pt {i}: {deviation} > {bound}"
982                    );
983                }
984            }
985        }
986    }
987
988    #[test]
989    fn weighted_refines_locally() {
990        // a bump under the uniform tolerance vanishes — until its weight drops
991        let mut line: Vec<(f64, f64)> = (0..10).map(|i| (f64::from(i), 0.0)).collect();
992        line[5] = (5.0, 0.3);
993        let bump = line[5];
994        let mut weights = vec![1.0; line.len()];
995        weights[5] = 0.1;
996        assert!(!rdp(&line, 0.5).contains(&bump));
997        assert!(rdp_w(&line, 0.5, &weights).contains(&bump));
998        assert!(!visvalingam(&line, 0.5).contains(&bump));
999        assert!(visvalingam_w(&line, 0.5, &weights).contains(&bump));
1000        // every imai-iri shortcut spanning the bump misses it by 0.3 > 0.05,
1001        // so the bump itself must be a shortcut endpoint
1002        assert!(!imai_iri(&line, 0.5).contains(&bump));
1003        assert!(imai_iri_w(&line, 0.5, &weights).contains(&bump));
1004    }
1005
1006    #[test]
1007    fn weighted_long_arc_prefilter_bound() {
1008        // > II_MAX: per-point bound may relax where weights vary within a
1009        // prefilter shortcut, but the global epsilon·max(weights) bound always
1010        // holds
1011        let points = wiggle(II_MAX + 2000, 13);
1012        #[expect(
1013            clippy::cast_precision_loss,
1014            reason = "i < points.len() = II_MAX+2000 ≪ 2^53; test weights"
1015        )]
1016        let weights: Vec<f64> = (0..points.len())
1017            .map(|i| 0.6 + 0.4 * (i as f64 / 500.0).sin())
1018            .collect();
1019        let epsilon = 0.3;
1020        let out = imai_iri_w(&points, epsilon, &weights);
1021        assert!(out.len() < points.len());
1022        for &point in &points {
1023            assert!(point_dev(point, &out) <= epsilon + 1e-12);
1024        }
1025    }
1026
1027    #[test]
1028    fn weighted_dispatch_matches_direct() {
1029        let points = wiggle(100, 3);
1030        let weights = rand_weights(points.len(), 0.2, 9);
1031        assert_eq!(simplify_weighted(Simplify::None, &points, &weights), points);
1032        assert_eq!(
1033            simplify_weighted(Simplify::Rdp { epsilon: 0.2 }, &points, &weights),
1034            rdp_w(&points, 0.2, &weights)
1035        );
1036        assert_eq!(
1037            simplify_weighted(Simplify::Visvalingam { min_area: 0.2 }, &points, &weights),
1038            visvalingam_w(&points, 0.2, &weights)
1039        );
1040        assert_eq!(
1041            simplify_weighted(Simplify::ImaiIri { epsilon: 0.2 }, &points, &weights),
1042            imai_iri_w(&points, 0.2, &weights)
1043        );
1044    }
1045
1046    #[test]
1047    #[expect(
1048        clippy::float_cmp,
1049        reason = "weight() knees are exact early-returns (1.0/w_min); approximate equality would weaken the test"
1050    )]
1051    fn density_weight_shape() {
1052        let model = DensityWeight::new(0.1);
1053        assert_eq!(model.weight(0.0), 1.0);
1054        assert_eq!(model.weight(model.d_lo), 1.0);
1055        assert_eq!(model.weight(1e12), 0.1);
1056        assert_eq!(model.weight(f64::NAN), 1.0);
1057        // continuous at both knees, monotone nonincreasing between
1058        assert!((model.weight(model.d_lo * 1.0001) - 1.0).abs() < 1e-3);
1059        assert!((model.weight(model.d_hi * 0.9999) - 0.1).abs() < 1e-3);
1060        let mut last = 1.0;
1061        for i in 0..100 {
1062            let density = model.d_lo * (model.d_hi / model.d_lo).powf(f64::from(i) / 99.0);
1063            let weight = model.weight(density);
1064            assert!(
1065                weight <= last + 1e-15 && (model.w_min..=1.0).contains(&weight),
1066                "density={density} weight={weight}"
1067            );
1068            last = weight;
1069        }
1070        // weighting off
1071        assert_eq!(DensityWeight::new(1.0).weight(1e9), 1.0);
1072    }
1073}