geo/algorithm/
densify.rs

1use crate::{
2    CoordFloat, EuclideanLength, Line, LineInterpolatePoint, LineString, MultiLineString,
3    MultiPolygon, Point, Polygon, Rect, Triangle,
4};
5
6/// Return a new linear geometry containing both existing and new interpolated coordinates with
7/// a maximum distance of `max_distance` between them.
8///
9/// Note: `max_distance` must be greater than 0.
10///
11/// # Examples
12/// ```
13/// use geo::{coord, Line, LineString};
14/// use geo::Densify;
15///
16/// let line: Line<f64> = Line::new(coord! {x: 0.0, y: 6.0}, coord! {x: 1.0, y: 8.0});
17/// let correct: LineString<f64> = vec![[0.0, 6.0], [0.5, 7.0], [1.0, 8.0]].into();
18/// let max_dist = 2.0;
19/// let densified = line.densify(max_dist);
20/// assert_eq!(densified, correct);
21///```
22pub trait Densify<F: CoordFloat> {
23    type Output;
24
25    fn densify(&self, max_distance: F) -> Self::Output;
26}
27
28// Helper for densification trait
29fn densify_line<T: CoordFloat>(line: Line<T>, container: &mut Vec<Point<T>>, max_distance: T) {
30    assert!(max_distance > T::zero());
31    container.push(line.start_point());
32    let num_segments = (line.euclidean_length() / max_distance)
33        .ceil()
34        .to_u64()
35        .unwrap();
36    // distance "unit" for this line segment
37    let frac = T::one() / T::from(num_segments).unwrap();
38    for segment_idx in 1..num_segments {
39        let ratio = frac * T::from(segment_idx).unwrap();
40        let interpolated_point = line
41            .line_interpolate_point(ratio)
42            .expect("ratio should be between 0..1");
43        container.push(interpolated_point);
44    }
45}
46
47impl<T> Densify<T> for MultiPolygon<T>
48where
49    T: CoordFloat,
50    Line<T>: EuclideanLength<T>,
51    LineString<T>: EuclideanLength<T>,
52{
53    type Output = MultiPolygon<T>;
54
55    fn densify(&self, max_distance: T) -> Self::Output {
56        MultiPolygon::new(
57            self.iter()
58                .map(|polygon| polygon.densify(max_distance))
59                .collect(),
60        )
61    }
62}
63
64impl<T> Densify<T> for Polygon<T>
65where
66    T: CoordFloat,
67    Line<T>: EuclideanLength<T>,
68    LineString<T>: EuclideanLength<T>,
69{
70    type Output = Polygon<T>;
71
72    fn densify(&self, max_distance: T) -> Self::Output {
73        let densified_exterior = self.exterior().densify(max_distance);
74        let densified_interiors = self
75            .interiors()
76            .iter()
77            .map(|ring| ring.densify(max_distance))
78            .collect();
79        Polygon::new(densified_exterior, densified_interiors)
80    }
81}
82
83impl<T> Densify<T> for MultiLineString<T>
84where
85    T: CoordFloat,
86    Line<T>: EuclideanLength<T>,
87    LineString<T>: EuclideanLength<T>,
88{
89    type Output = MultiLineString<T>;
90
91    fn densify(&self, max_distance: T) -> Self::Output {
92        MultiLineString::new(
93            self.iter()
94                .map(|linestring| linestring.densify(max_distance))
95                .collect(),
96        )
97    }
98}
99
100impl<T> Densify<T> for LineString<T>
101where
102    T: CoordFloat,
103    Line<T>: EuclideanLength<T>,
104    LineString<T>: EuclideanLength<T>,
105{
106    type Output = LineString<T>;
107
108    fn densify(&self, max_distance: T) -> Self::Output {
109        let mut new_line = vec![];
110        self.lines()
111            .for_each(|line| densify_line(line, &mut new_line, max_distance));
112        // we're done, push the last coordinate on to finish
113        new_line.push(self.points().last().unwrap());
114        LineString::from(new_line)
115    }
116}
117
118impl<T> Densify<T> for Line<T>
119where
120    T: CoordFloat,
121    Line<T>: EuclideanLength<T>,
122    LineString<T>: EuclideanLength<T>,
123{
124    type Output = LineString<T>;
125
126    fn densify(&self, max_distance: T) -> Self::Output {
127        let mut new_line = vec![];
128        densify_line(*self, &mut new_line, max_distance);
129        // we're done, push the last coordinate on to finish
130        new_line.push(self.end_point());
131        LineString::from(new_line)
132    }
133}
134
135impl<T> Densify<T> for Triangle<T>
136where
137    T: CoordFloat,
138    Line<T>: EuclideanLength<T>,
139    LineString<T>: EuclideanLength<T>,
140{
141    type Output = Polygon<T>;
142
143    fn densify(&self, max_distance: T) -> Self::Output {
144        self.to_polygon().densify(max_distance)
145    }
146}
147
148impl<T> Densify<T> for Rect<T>
149where
150    T: CoordFloat,
151    Line<T>: EuclideanLength<T>,
152    LineString<T>: EuclideanLength<T>,
153{
154    type Output = Polygon<T>;
155
156    fn densify(&self, max_distance: T) -> Self::Output {
157        self.to_polygon().densify(max_distance)
158    }
159}
160
161#[cfg(test)]
162mod tests {
163    use super::*;
164    use crate::{coord, Coord};
165
166    #[test]
167    fn test_polygon_densify() {
168        let linestring: LineString<f64> =
169            vec![[-5.0, 0.0], [0.0, 5.0], [5.0, 0.0], [-5.0, 0.0]].into();
170        let interior: LineString<f64> =
171            vec![[-3.0, 0.0], [0.0, 3.0], [3.0, 0.0], [-3.0, 0.0]].into();
172        let polygon = Polygon::new(linestring, vec![interior]);
173        let correct_ext: LineString<f64> = LineString(vec![
174            Coord { x: -5.0, y: 0.0 },
175            Coord { x: -3.75, y: 1.25 },
176            Coord { x: -2.5, y: 2.5 },
177            Coord { x: -1.25, y: 3.75 },
178            Coord { x: 0.0, y: 5.0 },
179            Coord { x: 1.25, y: 3.75 },
180            Coord { x: 2.5, y: 2.5 },
181            Coord { x: 3.75, y: 1.25 },
182            Coord { x: 5.0, y: 0.0 },
183            Coord { x: 3.0, y: 0.0 },
184            Coord { x: 1.0, y: 0.0 },
185            Coord {
186                x: -1.0000000000000009,
187                y: 0.0,
188            },
189            Coord { x: -3.0, y: 0.0 },
190            Coord { x: -5.0, y: 0.0 },
191        ]);
192        let correct_int: LineString<f64> = LineString(vec![
193            Coord { x: -3.0, y: 0.0 },
194            Coord { x: -2.0, y: 1.0 },
195            Coord { x: -1.0, y: 2.0 },
196            Coord { x: 0.0, y: 3.0 },
197            Coord { x: 1.0, y: 2.0 },
198            Coord { x: 2.0, y: 1.0 },
199            Coord { x: 3.0, y: 0.0 },
200            Coord { x: 1.0, y: 0.0 },
201            Coord { x: -1.0, y: 0.0 },
202            Coord { x: -3.0, y: 0.0 },
203        ]);
204        let correct_polygon = Polygon::new(correct_ext, vec![correct_int]);
205        let max_dist = 2.0;
206        let densified = polygon.densify(max_dist);
207        assert_eq!(densified, correct_polygon);
208    }
209
210    #[test]
211    fn test_linestring_densify() {
212        let linestring: LineString<f64> =
213            vec![[-1.0, 0.0], [0.0, 0.0], [0.0, 6.0], [1.0, 8.0]].into();
214        let correct: LineString<f64> = vec![
215            [-1.0, 0.0],
216            [0.0, 0.0],
217            [0.0, 2.0],
218            [0.0, 4.0],
219            [0.0, 6.0],
220            [0.5, 7.0],
221            [1.0, 8.0],
222        ]
223        .into();
224        let max_dist = 2.0;
225        let densified = linestring.densify(max_dist);
226        assert_eq!(densified, correct);
227    }
228
229    #[test]
230    fn test_line_densify() {
231        let line: Line<f64> = Line::new(coord! {x: 0.0, y: 6.0}, coord! {x: 1.0, y: 8.0});
232        let correct: LineString<f64> = vec![[0.0, 6.0], [0.5, 7.0], [1.0, 8.0]].into();
233        let max_dist = 2.0;
234        let densified = line.densify(max_dist);
235        assert_eq!(densified, correct);
236    }
237}
geo/algorithm/densify.rs

geo/algorithm/
densify.rs
