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
129    use geometry_model::{MultiLinestring, MultiPolygon, Point, Point3D, Polygon, Ring, polygon};
130    use geometry_trait::{
131        MultiLinestring as _, MultiPolygon as _, PointMut as _, Polygon as _, Ring as _,
132    };
133
134    /// A `Ring` collapses consecutive duplicate vertices.
135    #[test]
136    fn ring_dedups_consecutive_vertices() {
137        let mut r: Ring<P> = Ring::from_vec(vec![
138            P::new(0.0, 0.0),
139            P::new(0.0, 0.0),
140            P::new(1.0, 0.0),
141            P::new(1.0, 1.0),
142            P::new(1.0, 1.0),
143        ]);
144        unique(&mut r);
145        assert_eq!(r.points().count(), 3);
146    }
147
148    /// A `Polygon` dedups its exterior *and* every interior ring.
149    #[test]
150    fn polygon_dedups_outer_and_holes() {
151        let mut p: Polygon<P> = polygon![
152            [
153                (0.0, 0.0),
154                (0.0, 0.0),
155                (10.0, 0.0),
156                (10.0, 10.0),
157                (0.0, 10.0),
158                (0.0, 0.0)
159            ],
160            [(2.0, 2.0), (2.0, 2.0), (4.0, 2.0), (4.0, 4.0), (2.0, 2.0)]
161        ];
162        unique(&mut p);
163        assert_eq!(p.exterior().points().count(), 5); // one leading dup dropped
164        let hole = p.interiors().next().unwrap();
165        assert_eq!(hole.points().count(), 4); // one leading dup dropped
166    }
167
168    /// A `MultiLinestring` dedups each member independently.
169    #[test]
170    fn multi_linestring_dedups_each_member() {
171        let mut mls: MultiLinestring<geometry_model::Linestring<P>> = MultiLinestring(vec![
172            linestring![(0.0, 0.0), (0.0, 0.0), (1.0, 1.0)],
173            linestring![(2.0, 2.0), (3.0, 3.0), (3.0, 3.0)],
174        ]);
175        unique(&mut mls);
176        let counts: Vec<usize> = mls.linestrings().map(|l| l.points().count()).collect();
177        assert_eq!(counts, vec![2, 2]);
178    }
179
180    /// A `MultiPolygon` dedups each member polygon.
181    #[test]
182    fn multi_polygon_dedups_each_member() {
183        let member: Polygon<P> =
184            polygon![[(0.0, 0.0), (0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 0.0)]];
185        let mut mpg: MultiPolygon<Polygon<P>> = MultiPolygon(vec![member.clone(), member]);
186        unique(&mut mpg);
187        for pg in mpg.polygons() {
188            assert_eq!(pg.exterior().points().count(), 4);
189        }
190    }
191
192    /// `points_equal` compares the third ordinate for 3D points — the
193    /// `2 =>` arm. Two points equal in x,y but differing in z are *not*
194    /// merged.
195    #[test]
196    fn three_d_points_compare_all_three_ordinates() {
197        type P3 = Point3D<f64, Cartesian>;
198        let mut ls: geometry_model::Linestring<P3> = geometry_model::Linestring(vec![
199            P3::new(0.0, 0.0, 0.0),
200            P3::new(0.0, 0.0, 1.0), // same x,y — different z: kept
201            P3::new(0.0, 0.0, 1.0), // exact duplicate: dropped
202        ]);
203        unique(&mut ls);
204        assert_eq!(ls.points().count(), 2);
205    }
206
207    /// `points_equal` reaches the `3 =>` arm for 4D points (`MAX_DIM)`:
208    /// two points differing only in the fourth ordinate are distinct.
209    #[test]
210    fn four_d_points_compare_the_fourth_ordinate() {
211        type P4 = Point<f64, 4, Cartesian>;
212        let mut a = P4::default();
213        a.set::<0>(1.0);
214        a.set::<1>(2.0);
215        a.set::<2>(3.0);
216        a.set::<3>(4.0);
217        let mut b = a;
218        b.set::<3>(9.0); // differ only in the 4th ordinate
219        let dup = a;
220        let mut ls: geometry_model::Linestring<P4> = geometry_model::Linestring(vec![a, b, dup]);
221        unique(&mut ls);
222        // a, b differ (4th ordinate); dup == a but is not adjacent to a,
223        // so nothing collapses.
224        assert_eq!(ls.points().count(), 3);
225    }
226}
geometry_algorithm/unique.rs

geometry_algorithm/
unique.rs
