geo/algorithm/
lines_iter.rs

1use crate::{
2    Coord, CoordNum, Line, LineString, MultiLineString, MultiPolygon, Polygon, Rect, Triangle,
3};
4use core::slice;
5use std::fmt::Debug;
6use std::iter;
7
8/// Iterate over lines of a geometry.
9pub trait LinesIter<'a> {
10    type Scalar: CoordNum;
11    type Iter: Iterator<Item = Line<Self::Scalar>>;
12
13    /// Iterate over all exterior and (if any) interior lines of a geometry.
14    ///
15    /// # Examples
16    ///
17    /// ```
18    /// use geo::line_string;
19    /// use geo::lines_iter::LinesIter;
20    /// use geo::{coord, Line};
21    ///
22    /// let ls = line_string![
23    ///     (x: 1., y: 2.),
24    ///     (x: 23., y: 82.),
25    ///     (x: -1., y: 0.),
26    /// ];
27    ///
28    /// let mut iter = ls.lines_iter();
29    /// assert_eq!(
30    ///     Some(Line::new(
31    ///         coord! { x: 1., y: 2. },
32    ///         coord! { x: 23., y: 82. }
33    ///     )),
34    ///     iter.next()
35    /// );
36    /// assert_eq!(
37    ///     Some(Line::new(
38    ///         coord! { x: 23., y: 82. },
39    ///         coord! { x: -1., y: 0. }
40    ///     )),
41    ///     iter.next()
42    /// );
43    /// assert_eq!(None, iter.next());
44    /// ```
45    fn lines_iter(&'a self) -> Self::Iter;
46}
47
48impl<'a, T: CoordNum + 'a> LinesIter<'a> for Line<T> {
49    type Scalar = T;
50    type Iter = iter::Copied<iter::Once<&'a Line<Self::Scalar>>>;
51
52    fn lines_iter(&'a self) -> Self::Iter {
53        iter::once(self).copied()
54    }
55}
56
57impl<'a, T: CoordNum + 'a> LinesIter<'a> for LineString<T> {
58    type Scalar = T;
59    type Iter = LineStringIter<'a, Self::Scalar>;
60
61    fn lines_iter(&'a self) -> Self::Iter {
62        LineStringIter::new(self)
63    }
64}
65
66/// Iterator over lines in a [LineString].
67#[derive(Debug)]
68pub struct LineStringIter<'a, T: CoordNum>(slice::Windows<'a, Coord<T>>);
69
70impl<'a, T: CoordNum> LineStringIter<'a, T> {
71    fn new(line_string: &'a LineString<T>) -> Self {
72        Self(line_string.0.windows(2))
73    }
74}
75
76impl<'a, T: CoordNum> Iterator for LineStringIter<'a, T> {
77    type Item = Line<T>;
78
79    fn next(&mut self) -> Option<Self::Item> {
80        // Can't use LineString::lines() because it returns an `impl Trait`
81        // and there is no way to name that type in `LinesIter::Iter` until [RFC 2071] is stabilized.
82        //
83        // [RFC 2071]: https://rust-lang.github.io/rfcs/2071-impl-trait-existential-types.html
84        self.0.next().map(|w| {
85            // SAFETY: slice::windows(2) is guaranteed to yield a slice with exactly 2 elements
86            unsafe { Line::new(*w.get_unchecked(0), *w.get_unchecked(1)) }
87        })
88    }
89}
90
91type MultiLineStringIter<'a, T> =
92    iter::Flatten<MapLinesIter<'a, slice::Iter<'a, LineString<T>>, LineString<T>>>;
93
94impl<'a, T: CoordNum + 'a> LinesIter<'a> for MultiLineString<T> {
95    type Scalar = T;
96    type Iter = MultiLineStringIter<'a, Self::Scalar>;
97
98    fn lines_iter(&'a self) -> Self::Iter {
99        MapLinesIter(self.0.iter()).flatten()
100    }
101}
102
103type PolygonIter<'a, T> = iter::Chain<
104    LineStringIter<'a, T>,
105    iter::Flatten<MapLinesIter<'a, slice::Iter<'a, LineString<T>>, LineString<T>>>,
106>;
107
108impl<'a, T: CoordNum + 'a> LinesIter<'a> for Polygon<T> {
109    type Scalar = T;
110    type Iter = PolygonIter<'a, Self::Scalar>;
111
112    fn lines_iter(&'a self) -> Self::Iter {
113        self.exterior()
114            .lines_iter()
115            .chain(MapLinesIter(self.interiors().iter()).flatten())
116    }
117}
118
119type MultiPolygonIter<'a, T> =
120    iter::Flatten<MapLinesIter<'a, slice::Iter<'a, Polygon<T>>, Polygon<T>>>;
121
122impl<'a, T: CoordNum + 'a> LinesIter<'a> for MultiPolygon<T> {
123    type Scalar = T;
124    type Iter = MultiPolygonIter<'a, Self::Scalar>;
125
126    fn lines_iter(&'a self) -> Self::Iter {
127        MapLinesIter(self.0.iter()).flatten()
128    }
129}
130
131impl<'a, T: CoordNum + 'a> LinesIter<'a> for Rect<T> {
132    type Scalar = T;
133    type Iter = <[Line<Self::Scalar>; 4] as IntoIterator>::IntoIter;
134
135    fn lines_iter(&'a self) -> Self::Iter {
136        self.to_lines().into_iter()
137    }
138}
139
140impl<'a, T: CoordNum + 'a> LinesIter<'a> for Triangle<T> {
141    type Scalar = T;
142    type Iter = <[Line<Self::Scalar>; 3] as IntoIterator>::IntoIter;
143
144    fn lines_iter(&'a self) -> Self::Iter {
145        self.to_lines().into_iter()
146    }
147}
148
149/// Utility to transform `Iterator<LinesIter>` into `Iterator<Iterator<Line>>`.
150#[derive(Debug)]
151pub struct MapLinesIter<'a, Iter1: Iterator<Item = &'a Iter2>, Iter2: 'a + LinesIter<'a>>(Iter1);
152
153impl<'a, Iter1: Iterator<Item = &'a Iter2>, Iter2: LinesIter<'a>> Iterator
154    for MapLinesIter<'a, Iter1, Iter2>
155{
156    type Item = Iter2::Iter;
157
158    fn next(&mut self) -> Option<Self::Item> {
159        self.0.next().map(|g| g.lines_iter())
160    }
161}
162
163#[cfg(test)]
164mod test {
165
166    use super::LinesIter;
167    use crate::{
168        coord, line_string, polygon, Line, LineString, MultiLineString, MultiPolygon, Rect,
169        Triangle,
170    };
171
172    #[test]
173    fn test_line() {
174        let line = Line::new(coord! { x: 0., y: 0. }, coord! { x: 5., y: 10. });
175        let want = vec![Line::new(coord! { x: 0., y: 0. }, coord! { x: 5., y: 10. })];
176        assert_eq!(want, line.lines_iter().collect::<Vec<_>>());
177    }
178
179    #[test]
180    fn test_empty_line_string() {
181        let ls: LineString = line_string![];
182        assert_eq!(Vec::<Line>::new(), ls.lines_iter().collect::<Vec<_>>());
183    }
184
185    #[test]
186    fn test_open_line_string() {
187        let ls = line_string![(x: 0., y: 0.), (x: 1., y: 1.), (x:2., y: 2.)];
188        let want = vec![
189            Line::new(coord! { x: 0., y: 0. }, coord! { x: 1., y: 1. }),
190            Line::new(coord! { x: 1., y: 1. }, coord! { x: 2., y: 2. }),
191        ];
192        assert_eq!(want, ls.lines_iter().collect::<Vec<_>>());
193    }
194
195    #[test]
196    fn test_closed_line_string() {
197        let mut ls = line_string![(x: 0., y: 0.), (x: 1., y: 1.), (x:2., y: 2.)];
198        ls.close();
199        let want = vec![
200            Line::new(coord! { x: 0., y: 0. }, coord! { x: 1., y: 1. }),
201            Line::new(coord! { x: 1., y: 1. }, coord! { x: 2., y: 2. }),
202            Line::new(coord! { x: 2., y: 2. }, coord! { x: 0., y: 0. }),
203        ];
204        assert_eq!(want, ls.lines_iter().collect::<Vec<_>>());
205    }
206
207    #[test]
208    fn test_multi_line_string() {
209        let mls = MultiLineString::new(vec![
210            line_string![],
211            line_string![(x: 0., y: 0.), (x: 1., y: 1.)],
212            line_string![(x: 0., y: 0.), (x: 1., y: 1.), (x:2., y: 2.)],
213        ]);
214        let want = vec![
215            Line::new(coord! { x: 0., y: 0. }, coord! { x: 1., y: 1. }),
216            Line::new(coord! { x: 0., y: 0. }, coord! { x: 1., y: 1. }),
217            Line::new(coord! { x: 1., y: 1. }, coord! { x: 2., y: 2. }),
218        ];
219        assert_eq!(want, mls.lines_iter().collect::<Vec<_>>());
220    }
221
222    #[test]
223    fn test_polygon() {
224        let p = polygon!(
225            exterior: [(x: 0., y: 0.), (x: 0., y: 10.), (x: 10., y: 10.), (x: 10., y: 0.)],
226            interiors: [
227                [(x: 1., y: 1.), (x: 1., y: 2.), (x: 2., y: 2.), (x: 2., y: 1.)],
228                [(x: 3., y: 3.), (x: 5., y: 3.), (x: 5., y: 5.), (x: 3., y: 5.)],
229            ],
230        );
231        let want = vec![
232            // exterior ring
233            Line::new(coord! { x: 0., y: 0. }, coord! { x: 0., y: 10. }),
234            Line::new(coord! { x: 0., y: 10. }, coord! { x: 10., y: 10. }),
235            Line::new(coord! { x: 10., y: 10. }, coord! { x: 10., y: 0. }),
236            Line::new(coord! { x: 10., y: 0. }, coord! { x: 0., y: 0. }),
237            // first interior ring
238            Line::new(coord! { x: 1., y: 1. }, coord! { x: 1., y: 2. }),
239            Line::new(coord! { x: 1., y: 2. }, coord! { x: 2., y: 2. }),
240            Line::new(coord! { x: 2., y: 2. }, coord! { x: 2., y: 1. }),
241            Line::new(coord! { x: 2., y: 1. }, coord! { x: 1., y: 1. }),
242            // second interior ring
243            Line::new(coord! { x: 3., y: 3. }, coord! { x: 5., y: 3. }),
244            Line::new(coord! { x: 5., y: 3. }, coord! { x: 5., y: 5. }),
245            Line::new(coord! { x: 5., y: 5. }, coord! { x: 3., y: 5. }),
246            Line::new(coord! { x: 3., y: 5. }, coord! { x: 3., y: 3. }),
247        ];
248        assert_eq!(want, p.lines_iter().collect::<Vec<_>>());
249    }
250
251    #[test]
252    fn test_multi_polygon() {
253        let mp = MultiPolygon::new(vec![
254            polygon!(
255                exterior: [(x: 0., y: 0.), (x: 0., y: 10.), (x: 10., y: 10.), (x: 10., y: 0.)],
256                interiors: [[(x: 1., y: 1.), (x: 1., y: 2.), (x: 2., y: 2.), (x: 2., y: 1.)]],
257            ),
258            polygon!(
259                exterior: [(x: 3., y: 3.), (x: 5., y: 3.), (x: 5., y: 5.), (x: 3., y: 5.)],
260                interiors: [],
261            ),
262        ]);
263        let want = vec![
264            // first polygon - exterior ring
265            Line::new(coord! { x: 0., y: 0. }, coord! { x: 0., y: 10. }),
266            Line::new(coord! { x: 0., y: 10. }, coord! { x: 10., y: 10. }),
267            Line::new(coord! { x: 10., y: 10. }, coord! { x: 10., y: 0. }),
268            Line::new(coord! { x: 10., y: 0. }, coord! { x: 0., y: 0. }),
269            // first polygon - interior ring
270            Line::new(coord! { x: 1., y: 1. }, coord! { x: 1., y: 2. }),
271            Line::new(coord! { x: 1., y: 2. }, coord! { x: 2., y: 2. }),
272            Line::new(coord! { x: 2., y: 2. }, coord! { x: 2., y: 1. }),
273            Line::new(coord! { x: 2., y: 1. }, coord! { x: 1., y: 1. }),
274            // second polygon - exterior ring
275            Line::new(coord! { x: 3., y: 3. }, coord! { x: 5., y: 3. }),
276            Line::new(coord! { x: 5., y: 3. }, coord! { x: 5., y: 5. }),
277            Line::new(coord! { x: 5., y: 5. }, coord! { x: 3., y: 5. }),
278            Line::new(coord! { x: 3., y: 5. }, coord! { x: 3., y: 3. }),
279        ];
280        assert_eq!(want, mp.lines_iter().collect::<Vec<_>>());
281    }
282
283    #[test]
284    fn test_rect() {
285        let rect = Rect::new(coord! { x: 0., y: 0. }, coord! { x: 1., y: 2. });
286        let want = rect.to_polygon().lines_iter().collect::<Vec<_>>();
287        assert_eq!(want, rect.lines_iter().collect::<Vec<_>>());
288    }
289
290    #[test]
291    fn test_triangle() {
292        let triangle = Triangle::new(
293            coord! { x: 0., y: 0. },
294            coord! { x: 1., y: 2. },
295            coord! { x: 2., y: 3. },
296        );
297        let want = triangle.to_polygon().lines_iter().collect::<Vec<_>>();
298        assert_eq!(want, triangle.lines_iter().collect::<Vec<_>>());
299    }
300}
geo/algorithm/lines_iter.rs

geo/algorithm/
lines_iter.rs
