geometry_algorithm/
unique.rs

1//! `unique(&mut g)` — collapse consecutive duplicate points.
2//!
3//! Mirrors `boost::geometry::unique` from
4//! `boost/geometry/algorithms/unique.hpp`. Boost uses `std::unique`
5//! and walks the same kind hierarchy as `reverse`. Per-kind:
6//!
7//! * `Linestring`, `Ring`  → `Vec::dedup` on the backing vec
8//! * `Polygon`             → dedup outer + every inner ring
9//! * `MultiLinestring`     → dedup each member
10//! * `MultiPolygon`        → dedup each member polygon
11//!
12//! Two points are equal iff every coordinate matches. Boost uses `==`
13//! on the coordinate type, which for floats is exact equality; we
14//! mirror that via [`Point::get`](geometry_trait::Point::get) per
15//! dimension, driven by [`geometry_trait::fold_dims`].
16
17use geometry_model::{Linestring, MultiLinestring, MultiPolygon, Polygon, Ring};
18use geometry_trait::{
19    Linestring as LinestringTrait, Point as PointTrait, Polygon as PolygonTrait, fold_dims,
20};
21
22/// Collapse runs of coordinate-equal consecutive points in `g`.
23///
24/// Mirrors `boost::geometry::unique(g)` from
25/// `boost/geometry/algorithms/unique.hpp`.
26pub fn unique<G: Unique>(g: &mut G) {
27    g.unique();
28}
29
30/// Per-kind dedup dispatch.
31#[doc(hidden)]
32pub trait Unique {
33    fn unique(&mut self);
34}
35
36/// Coordinate-wise equality. Mirrors Boost's `operator==` path through
37/// `traits::access<P, D>::get` — exact (bitwise-via-`==`) per Boost.
38fn points_equal<P: PointTrait>(a: &P, b: &P) -> bool {
39    // `fold_dims` recurses over the dimensions with a hard-coded const
40    // `D`; the closure receives the runtime index only as a label, so
41    // we re-issue `get::<D>` with matching literals.
42    fold_dims(true, a, |acc, _p, d| {
43        acc && match d {
44            0 => a.get::<0>() == b.get::<0>(),
45            1 => a.get::<1>() == b.get::<1>(),
46            2 => a.get::<2>() == b.get::<2>(),
47            3 => a.get::<3>() == b.get::<3>(),
48            _ => unreachable!("fold_dims caps at MAX_DIM"),
49        }
50    })
51}
52
53fn dedup_vec<P: PointTrait>(v: &mut alloc::vec::Vec<P>) {
54    v.dedup_by(|a, b| points_equal::<P>(a, b));
55}
56
57impl<P: PointTrait> Unique for Linestring<P> {
58    fn unique(&mut self) {
59        dedup_vec(&mut self.0);
60    }
61}
62
63impl<P: PointTrait, const CW: bool, const CL: bool> Unique for Ring<P, CW, CL> {
64    fn unique(&mut self) {
65        dedup_vec(&mut self.0);
66    }
67}
68
69impl<P: PointTrait, const CW: bool, const CL: bool> Unique for Polygon<P, CW, CL> {
70    fn unique(&mut self) {
71        dedup_vec(&mut self.outer.0);
72        for inner in &mut self.inners {
73            dedup_vec(&mut inner.0);
74        }
75    }
76}
77
78impl<L: Unique + LinestringTrait> Unique for MultiLinestring<L> {
79    fn unique(&mut self) {
80        for l in &mut self.0 {
81            l.unique();
82        }
83    }
84}
85
86impl<Pg: Unique + PolygonTrait> Unique for MultiPolygon<Pg> {
87    fn unique(&mut self) {
88        for p in &mut self.0 {
89            p.unique();
90        }
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    //! Reference behaviour from
97    //! `boost/geometry/test/algorithms/unique.cpp`: consecutive
98    //! duplicate points collapse to one; non-consecutive duplicates are
99    //! left alone (Boost only removes *consecutive* runs).
100
101    use super::unique;
102    use geometry_cs::Cartesian;
103    use geometry_model::{Point2D, linestring};
104    use geometry_trait::Linestring as _;
105
106    type P = Point2D<f64, Cartesian>;
107
108    #[test]
109    fn consecutive_duplicates_collapse() {
110        let mut ls: geometry_model::Linestring<P> = linestring![
111            (0.0, 0.0),
112            (0.0, 0.0),
113            (1.0, 1.0),
114            (1.0, 1.0),
115            (1.0, 1.0),
116            (2.0, 2.0)
117        ];
118        unique(&mut ls);
119        assert_eq!(ls.points().count(), 3);
120    }
121
122    #[test]
123    fn non_consecutive_duplicates_are_kept() {
124        let mut ls: geometry_model::Linestring<P> = linestring![(0.0, 0.0), (1.0, 1.0), (0.0, 0.0)];
125        unique(&mut ls);
126        assert_eq!(ls.points().count(), 3);
127    }
128}
geometry_algorithm/unique.rs

geometry_algorithm/
unique.rs
