geo/algorithm/
winding_order.rs

1use super::kernels::*;
2use crate::coords_iter::CoordsIter;
3use crate::utils::EitherIter;
4use crate::{CoordNum, LineString, Point};
5use geo_types::PointsIter;
6use std::iter::Rev;
7
8/// Iterates through a list of `Point`s
9#[allow(missing_debug_implementations)]
10pub struct Points<'a, T>(pub(crate) EitherIter<PointsIter<'a, T>, Rev<PointsIter<'a, T>>>)
11where
12    T: CoordNum + 'a;
13
14impl<'a, T> Iterator for Points<'a, T>
15where
16    T: CoordNum,
17{
18    type Item = Point<T>;
19
20    #[inline]
21    fn next(&mut self) -> Option<Self::Item> {
22        self.0.next()
23    }
24
25    #[inline]
26    fn size_hint(&self) -> (usize, Option<usize>) {
27        self.0.size_hint()
28    }
29}
30
31impl<'a, T> ExactSizeIterator for Points<'a, T>
32where
33    T: CoordNum,
34{
35    #[inline]
36    fn len(&self) -> usize {
37        self.0.len()
38    }
39}
40
41/// How a linestring is wound, clockwise or counter-clockwise
42#[derive(PartialEq, Clone, Debug, Eq, Copy)]
43pub enum WindingOrder {
44    Clockwise,
45    CounterClockwise,
46}
47
48impl WindingOrder {
49    #[allow(dead_code)]
50    pub(crate) fn inverse(&self) -> Self {
51        match self {
52            WindingOrder::Clockwise => WindingOrder::CounterClockwise,
53            WindingOrder::CounterClockwise => WindingOrder::Clockwise,
54        }
55    }
56}
57
58/// Determine and operate on how a [`LineString`] is
59/// wound. This functionality, and our implementation is
60/// based on [CGAL's Polygon_2::orientation].
61///
62/// [CGAL's Polygon_2::orientation]: //doc.cgal.org/latest/Polygon/classCGAL_1_1Polygon__2.html#a4ce8b4b8395406243ac16c2a120ffc15
63pub trait Winding {
64    type Scalar: CoordNum;
65
66    /// Return the winding order of this object if it
67    /// contains at least three distinct coordinates, and
68    /// `None` otherwise.
69    fn winding_order(&self) -> Option<WindingOrder>;
70
71    /// True iff this is wound clockwise
72    fn is_cw(&self) -> bool {
73        self.winding_order() == Some(WindingOrder::Clockwise)
74    }
75
76    /// True iff this is wound counterclockwise
77    fn is_ccw(&self) -> bool {
78        self.winding_order() == Some(WindingOrder::CounterClockwise)
79    }
80
81    /// Iterate over the points in a clockwise order
82    ///
83    /// The object isn't changed, and the points are returned either in order, or in reverse
84    /// order, so that the resultant order makes it appear clockwise
85    fn points_cw(&self) -> Points<Self::Scalar>;
86
87    /// Iterate over the points in a counter-clockwise order
88    ///
89    /// The object isn't changed, and the points are returned either in order, or in reverse
90    /// order, so that the resultant order makes it appear counter-clockwise
91    fn points_ccw(&self) -> Points<Self::Scalar>;
92
93    /// Change this object's points so they are in clockwise winding order
94    fn make_cw_winding(&mut self);
95
96    /// Change this line's points so they are in counterclockwise winding order
97    fn make_ccw_winding(&mut self);
98
99    /// Return a clone of this object, but in the specified winding order
100    fn clone_to_winding_order(&self, winding_order: WindingOrder) -> Self
101    where
102        Self: Sized + Clone,
103    {
104        let mut new: Self = self.clone();
105        new.make_winding_order(winding_order);
106        new
107    }
108
109    /// Change the winding order so that it is in this winding order
110    fn make_winding_order(&mut self, winding_order: WindingOrder) {
111        match winding_order {
112            WindingOrder::Clockwise => self.make_cw_winding(),
113            WindingOrder::CounterClockwise => self.make_ccw_winding(),
114        }
115    }
116}
117
118impl<T, K> Winding for LineString<T>
119where
120    T: HasKernel<Ker = K>,
121    K: Kernel<T>,
122{
123    type Scalar = T;
124
125    fn winding_order(&self) -> Option<WindingOrder> {
126        // If linestring has at most 3 coords, it is either
127        // not closed, or is at most two distinct points.
128        // Either way, the WindingOrder is unspecified.
129        if self.coords_count() < 4 || !self.is_closed() {
130            return None;
131        }
132
133        let increment = |x: &mut usize| {
134            *x += 1;
135            if *x >= self.coords_count() {
136                *x = 0;
137            }
138        };
139
140        let decrement = |x: &mut usize| {
141            if *x == 0 {
142                *x = self.coords_count() - 1;
143            } else {
144                *x -= 1;
145            }
146        };
147
148        use crate::utils::least_index;
149        let i = least_index(&self.0);
150
151        let mut next = i;
152        increment(&mut next);
153        while self.0[next] == self.0[i] {
154            if next == i {
155                // We've looped too much. There aren't
156                // enough unique coords to compute orientation.
157                return None;
158            }
159            increment(&mut next);
160        }
161
162        let mut prev = i;
163        decrement(&mut prev);
164        while self.0[prev] == self.0[i] {
165            // Note: we don't need to check if prev == i as
166            // the previous loop succeeded, and so we have
167            // at least two distinct elements in the list
168            decrement(&mut prev);
169        }
170
171        match K::orient2d(self.0[prev], self.0[i], self.0[next]) {
172            Orientation::CounterClockwise => Some(WindingOrder::CounterClockwise),
173            Orientation::Clockwise => Some(WindingOrder::Clockwise),
174            _ => None,
175        }
176    }
177
178    /// Iterate over the points in a clockwise order
179    ///
180    /// The Linestring isn't changed, and the points are returned either in order, or in reverse
181    /// order, so that the resultant order makes it appear clockwise
182    fn points_cw(&self) -> Points<Self::Scalar> {
183        match self.winding_order() {
184            Some(WindingOrder::CounterClockwise) => Points(EitherIter::B(self.points().rev())),
185            _ => Points(EitherIter::A(self.points())),
186        }
187    }
188
189    /// Iterate over the points in a counter-clockwise order
190    ///
191    /// The Linestring isn't changed, and the points are returned either in order, or in reverse
192    /// order, so that the resultant order makes it appear counter-clockwise
193    fn points_ccw(&self) -> Points<Self::Scalar> {
194        match self.winding_order() {
195            Some(WindingOrder::Clockwise) => Points(EitherIter::B(self.points().rev())),
196            _ => Points(EitherIter::A(self.points())),
197        }
198    }
199
200    /// Change this line's points so they are in clockwise winding order
201    fn make_cw_winding(&mut self) {
202        if let Some(WindingOrder::CounterClockwise) = self.winding_order() {
203            self.0.reverse();
204        }
205    }
206
207    /// Change this line's points so they are in counterclockwise winding order
208    fn make_ccw_winding(&mut self) {
209        if let Some(WindingOrder::Clockwise) = self.winding_order() {
210            self.0.reverse();
211        }
212    }
213}
214
215#[cfg(test)]
216mod test {
217    use super::*;
218    use crate::Point;
219
220    #[test]
221    fn robust_winding_float() {
222        // 3 points forming a triangle
223        let a = Point::new(0., 0.);
224        let b = Point::new(2., 0.);
225        let c = Point::new(1., 2.);
226
227        // Verify open linestrings return None
228        let mut ls = LineString::from(vec![a.0, b.0, c.0]);
229        assert!(ls.winding_order().is_none());
230
231        ls.0.push(ls.0[0]);
232        assert_eq!(ls.winding_order(), Some(WindingOrder::CounterClockwise));
233
234        ls.make_cw_winding();
235        assert_eq!(ls.winding_order(), Some(WindingOrder::Clockwise));
236    }
237
238    #[test]
239    fn robust_winding_integer() {
240        // 3 points forming a triangle
241        let a = Point::new(0i64, 0);
242        let b = Point::new(2, 0);
243        let c = Point::new(1, 2);
244
245        // Verify open linestrings return None
246        let mut ls = LineString::from(vec![a.0, b.0, c.0]);
247        assert!(ls.winding_order().is_none());
248
249        ls.0.push(ls.0[0]);
250        assert!(ls.is_ccw());
251
252        let ccw_ls: Vec<_> = ls.points_ccw().collect();
253
254        ls.make_cw_winding();
255        assert!(ls.is_cw());
256
257        assert_eq!(&ls.points_ccw().collect::<Vec<_>>(), &ccw_ls,);
258    }
259}
geo/algorithm/winding_order.rs

geo/algorithm/
winding_order.rs
