geo/algorithm/
chaikin_smoothing.rs

1use std::ops::Mul;
2
3use num_traits::FromPrimitive;
4
5use crate::{coord, Coord, CoordFloat, LineString, MultiLineString, MultiPolygon, Polygon};
6
7/// Smoothen `LineString`, `Polygon`, `MultiLineString` and `MultiPolygon` using Chaikins algorithm.
8///
9/// [Chaikins smoothing algorithm](http://www.idav.ucdavis.edu/education/CAGDNotes/Chaikins-Algorithm/Chaikins-Algorithm.html)
10///
11/// Each iteration of the smoothing doubles the number of vertices of the geometry, so in some
12/// cases it may make sense to apply a simplification afterwards to remove insignificant
13/// coordinates.
14///
15/// This implementation preserves the start and end vertices of an open linestring and
16/// smoothes the corner between start and end of a closed linestring.
17pub trait ChaikinSmoothing<T>
18where
19    T: CoordFloat + FromPrimitive,
20{
21    /// create a new geometry with the Chaikin smoothing being
22    /// applied `n_iterations` times.
23    fn chaikin_smoothing(&self, n_iterations: usize) -> Self;
24}
25
26impl<T> ChaikinSmoothing<T> for LineString<T>
27where
28    T: CoordFloat + FromPrimitive,
29{
30    fn chaikin_smoothing(&self, n_iterations: usize) -> Self {
31        if n_iterations == 0 {
32            self.clone()
33        } else {
34            let mut smooth = smoothen_linestring(self);
35            for _ in 0..(n_iterations - 1) {
36                smooth = smoothen_linestring(&smooth);
37            }
38            smooth
39        }
40    }
41}
42
43impl<T> ChaikinSmoothing<T> for MultiLineString<T>
44where
45    T: CoordFloat + FromPrimitive,
46{
47    fn chaikin_smoothing(&self, n_iterations: usize) -> Self {
48        MultiLineString::new(
49            self.0
50                .iter()
51                .map(|ls| ls.chaikin_smoothing(n_iterations))
52                .collect(),
53        )
54    }
55}
56
57impl<T> ChaikinSmoothing<T> for Polygon<T>
58where
59    T: CoordFloat + FromPrimitive,
60{
61    fn chaikin_smoothing(&self, n_iterations: usize) -> Self {
62        Polygon::new(
63            self.exterior().chaikin_smoothing(n_iterations),
64            self.interiors()
65                .iter()
66                .map(|ls| ls.chaikin_smoothing(n_iterations))
67                .collect(),
68        )
69    }
70}
71
72impl<T> ChaikinSmoothing<T> for MultiPolygon<T>
73where
74    T: CoordFloat + FromPrimitive,
75{
76    fn chaikin_smoothing(&self, n_iterations: usize) -> Self {
77        MultiPolygon::new(
78            self.0
79                .iter()
80                .map(|poly| poly.chaikin_smoothing(n_iterations))
81                .collect(),
82        )
83    }
84}
85
86fn smoothen_linestring<T>(linestring: &LineString<T>) -> LineString<T>
87where
88    T: CoordFloat + Mul<T> + FromPrimitive,
89{
90    let mut out_coords: Vec<_> = Vec::with_capacity(linestring.0.len() * 2);
91
92    if let (Some(first), Some(last)) = (linestring.0.first(), linestring.0.last()) {
93        if first != last {
94            // preserve start coordinate when the linestring is open
95            out_coords.push(*first);
96        }
97    }
98    for window_coordinates in linestring.0.windows(2) {
99        let (q, r) = smoothen_coordinates(window_coordinates[0], window_coordinates[1]);
100        out_coords.push(q);
101        out_coords.push(r);
102    }
103
104    if let (Some(first), Some(last)) = (linestring.0.first(), linestring.0.last()) {
105        if first != last {
106            // preserve the last coordinate of an open linestring
107            out_coords.push(*last);
108        } else {
109            // smoothen the edge between the beginning and the end in closed
110            // linestrings while keeping the linestring closed.
111            if let Some(out_first) = out_coords.first().copied() {
112                out_coords.push(out_first);
113            }
114        }
115    }
116    out_coords.into()
117}
118
119fn smoothen_coordinates<T>(c0: Coord<T>, c1: Coord<T>) -> (Coord<T>, Coord<T>)
120where
121    T: CoordFloat + Mul<T> + FromPrimitive,
122{
123    let q = coord! {
124        x: (T::from(0.75).unwrap() * c0.x) + (T::from(0.25).unwrap() * c1.x),
125        y: (T::from(0.75).unwrap() * c0.y) + (T::from(0.25).unwrap() * c1.y),
126    };
127    let r = coord! {
128        x: (T::from(0.25).unwrap() * c0.x) + (T::from(0.75).unwrap() * c1.x),
129        y: (T::from(0.25).unwrap() * c0.y) + (T::from(0.75).unwrap() * c1.y),
130    };
131    (q, r)
132}
133
134#[cfg(test)]
135mod test {
136    use crate::ChaikinSmoothing;
137    use crate::{LineString, Polygon};
138
139    #[test]
140    fn linestring_open() {
141        let ls = LineString::from(vec![(3.0, 0.0), (6.0, 3.0), (3.0, 6.0), (0.0, 3.0)]);
142        let ls_out = ls.chaikin_smoothing(1);
143        assert_eq!(
144            ls_out,
145            LineString::from(vec![
146                (3.0, 0.0),
147                (3.75, 0.75),
148                (5.25, 2.25),
149                (5.25, 3.75),
150                (3.75, 5.25),
151                (2.25, 5.25),
152                (0.75, 3.75),
153                (0.0, 3.0),
154            ])
155        );
156    }
157
158    #[test]
159    fn linestring_closed() {
160        let ls = LineString::from(vec![
161            (3.0, 0.0),
162            (6.0, 3.0),
163            (3.0, 6.0),
164            (0.0, 3.0),
165            (3.0, 0.0),
166        ]);
167        let ls_out = ls.chaikin_smoothing(1);
168        assert_eq!(
169            ls_out,
170            LineString::from(vec![
171                (3.75, 0.75),
172                (5.25, 2.25),
173                (5.25, 3.75),
174                (3.75, 5.25),
175                (2.25, 5.25),
176                (0.75, 3.75),
177                (0.75, 2.25),
178                (2.25, 0.75),
179                (3.75, 0.75)
180            ])
181        );
182    }
183
184    #[test]
185    fn polygon() {
186        let poly = Polygon::new(
187            LineString::from(vec![
188                (3.0, 0.0),
189                (6.0, 3.0),
190                (3.0, 6.0),
191                (0.0, 3.0),
192                (3.0, 0.0),
193            ]),
194            vec![],
195        );
196        let poly_out = poly.chaikin_smoothing(1);
197        assert_eq!(
198            poly_out.exterior(),
199            &LineString::from(vec![
200                (3.75, 0.75),
201                (5.25, 2.25),
202                (5.25, 3.75),
203                (3.75, 5.25),
204                (2.25, 5.25),
205                (0.75, 3.75),
206                (0.75, 2.25),
207                (2.25, 0.75),
208                (3.75, 0.75)
209            ])
210        );
211    }
212}
geo/algorithm/chaikin_smoothing.rs

geo/algorithm/
chaikin_smoothing.rs
