geometry_algorithm/
simplify.rs

1//! `simplify(g, max_distance)` — return a Douglas–Peucker-simplified
2//! copy of `g`.
3//!
4//! Mirrors `boost::geometry::simplify(g, max_distance)` from
5//! `boost/geometry/algorithms/simplify.hpp`. The Cartesian default is
6//! [`geometry_strategy::DouglasPeucker`]`<`[`geometry_strategy::PointToSegment`]`<`[`geometry_strategy::Pythagoras`]`>>`,
7//! matching Boost's default from
8//! `boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp`.
9//!
10//! v1 ships linestring simplify only. Ring / polygon simplify (which
11//! must preserve ring closure) lands with the areal-simplify task.
12
13use geometry_cs::{CartesianFamily, CoordinateSystem};
14use geometry_strategy::{DouglasPeucker, PointToSegment, Pythagoras, SimplifyStrategy};
15use geometry_tag::SameAs;
16use geometry_trait::{Linestring, Point, PointMut};
17
18/// Return a Douglas–Peucker-simplified copy of the linestring `g`.
19///
20/// Vertices whose perpendicular distance to the chord between their
21/// retained neighbours is below `max_distance` are dropped; the first
22/// and last vertices are always kept.
23///
24/// Mirrors `boost::geometry::simplify(linestring, max_distance)` from
25/// `boost/geometry/algorithms/simplify.hpp`.
26#[must_use]
27pub fn simplify<G, P>(g: &G, max_distance: f64) -> geometry_model::Linestring<P>
28where
29    G: Linestring<Point = P>,
30    P: Point<Scalar = f64> + PointMut + Default + Copy,
31    <P::Cs as CoordinateSystem>::Family: SameAs<CartesianFamily>,
32{
33    let strategy = DouglasPeucker::<PointToSegment<Pythagoras>>::default();
34    strategy.simplify(g, max_distance)
35}
36
37#[cfg(test)]
38#[allow(
39    clippy::float_cmp,
40    reason = "Simplified coordinates are exact literals."
41)]
42mod tests {
43    //! Reference behaviour from
44    //! `boost/geometry/test/algorithms/simplify.cpp` — a straight
45    //! polyline collapses to its endpoints and a wiggle below tolerance
46    //! is dropped while a spike above tolerance is kept.
47
48    use super::simplify;
49    use geometry_cs::Cartesian;
50    use geometry_model::{Linestring, Point2D, linestring};
51    use geometry_trait::Point as _;
52
53    type Pt = Point2D<f64, Cartesian>;
54
55    fn coords(ls: &Linestring<Pt>) -> alloc::vec::Vec<(f64, f64)> {
56        ls.0.iter().map(|p| (p.get::<0>(), p.get::<1>())).collect()
57    }
58
59    #[test]
60    fn straight_three_point_line_collapses() {
61        let ls: Linestring<Pt> = linestring![(0., 0.), (1., 0.), (2., 0.)];
62        let s = simplify(&ls, 0.5);
63        assert_eq!(coords(&s), alloc::vec![(0., 0.), (2., 0.)]);
64    }
65
66    #[test]
67    fn zigzag_with_tiny_deviation_collapses() {
68        // Every interior vertex sits within 0.05 of the (0,0)-(4,0)
69        // chord, so a 0.5 tolerance drops them all.
70        let ls: Linestring<Pt> =
71            linestring![(0., 0.), (1., 0.05), (2., -0.05), (3., 0.05), (4., 0.)];
72        let s = simplify(&ls, 0.5);
73        assert_eq!(coords(&s), alloc::vec![(0., 0.), (4., 0.)]);
74    }
75
76    #[test]
77    fn spike_above_tolerance_survives() {
78        let ls: Linestring<Pt> = linestring![(0., 0.), (1., 0.01), (2., 5.), (3., 0.01), (4., 0.)];
79        let s = simplify(&ls, 0.5);
80        let c = coords(&s);
81        assert_eq!(c.first().unwrap(), &(0., 0.));
82        assert_eq!(c.last().unwrap(), &(4., 0.));
83        assert!(c.contains(&(2., 5.)));
84    }
85}
geometry_algorithm/simplify.rs

geometry_algorithm/
simplify.rs
