1#[cfg(target_arch = "wasm32")]
40mod wasm;
41
42#[derive(Clone, Copy, PartialEq, Debug)]
45pub enum Simplify {
46 None,
48 Rdp { epsilon: f64 },
50 Visvalingam { min_area: f64 },
52 ImaiIri { epsilon: f64 },
55}
56
57pub 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 #[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#[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#[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#[derive(Clone, Copy, PartialEq, Debug)]
149pub struct DensityWeight {
150 pub w_min: f64,
153 pub d_lo: f64,
155 pub d_hi: f64,
157}
158
159impl DensityWeight {
160 pub const DEFAULT_D_LO: f64 = 5.0;
163 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 #[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
191fn 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#[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#[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
235struct RdpVertex {
238 point: (f64, f64),
239 e2: f64,
240 kept: bool,
241}
242
243fn 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
262fn rdp_recurse(vertices: &mut [RdpVertex]) {
265 let [start, interior @ .., end] = &*vertices else {
266 return;
267 };
268 let (start, end) = (start.point, end.point);
269 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#[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#[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#[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 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
333struct VwVertex {
340 point: (f64, f64),
341 w2: f64,
342 previous: usize,
343 next: usize,
344 alive: bool,
345 stamp: u32,
346}
347
348fn 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; }
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#[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
449const II_MAX: usize = 8192;
452
453#[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 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
494struct Wedge {
497 lo: (f64, f64),
498 hi: (f64, f64),
499 any: bool, empty: bool, }
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 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 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 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
562fn 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; 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 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 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 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 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; }
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 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 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 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 fn brute_min(points: &[(f64, f64)], e2: f64) -> usize {
773 let n = points.len();
774 for keep in 2..=n {
776 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 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 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); 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 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 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 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 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 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 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 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 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 assert_eq!(DensityWeight::new(1.0).weight(1e9), 1.0);
1072 }
1073}