geometry/
polygon.rs

1//! Integer coordinate polygons.
2
3use std::cmp::Ordering;
4
5use serde::{Deserialize, Serialize};
6
7use crate::bbox::Bbox;
8use crate::contains::{Containment, Contains};
9use crate::point::Point;
10use crate::rect::Rect;
11use crate::transform::{TransformMut, TransformRef, Transformation, TranslateMut, TranslateRef};
12
13/// A polygon, with vertex coordinates given
14#[derive(Debug, Default, Clone, Serialize, Deserialize, Hash, PartialEq, Eq, PartialOrd, Ord)]
15pub struct Polygon {
16    /// Vector of points that make up the polygon.
17    points: Vec<Point>,
18}
19
20impl Polygon {
21    /// Creates a polygon with given vertices.
22    pub fn from_verts(vec: Vec<Point>) -> Self {
23        Self { points: vec }
24    }
25
26    /// Returns the bottom y-coordinate in the polygon.
27    ///
28    /// # Example
29    ///
30    /// ```
31    /// # use geometry::prelude::*;
32    /// let points = vec![
33    ///     Point { x: 0, y: 0 },
34    ///     Point { x: 1, y: 2 },
35    ///     Point { x: -4, y: 5 },
36    /// ];
37    /// let polygon = Polygon::from_verts(points);
38    /// assert_eq!(polygon.bot(), 0);
39    /// ```
40    pub fn bot(&self) -> i64 {
41        self.points.iter().map(|point| point.y).min().unwrap()
42    }
43
44    /// Returns the top y-coordinate in the polygon.
45    ///
46    /// # Example
47    ///
48    /// ```
49    /// # use geometry::prelude::*;
50    /// let points = vec![
51    ///     Point { x: 0, y: 0 },
52    ///     Point { x: 1, y: 2 },
53    ///     Point { x: -4, y: 5 },
54    /// ];
55    /// let polygon = Polygon::from_verts(points);
56    /// assert_eq!(polygon.top(), 5);
57    /// ```
58    pub fn top(&self) -> i64 {
59        self.points.iter().map(|point| point.y).max().unwrap()
60    }
61
62    /// Returns the leftmost x-coordinate in the polygon.
63    ///
64    /// # Example
65    ///
66    /// ```
67    /// # use geometry::prelude::*;
68    /// let points = vec![
69    ///     Point { x: 0, y: 0 },
70    ///     Point { x: 1, y: 2 },
71    ///     Point { x: -4, y: 5 },
72    /// ];
73    /// let polygon = Polygon::from_verts(points);
74    /// assert_eq!(polygon.left(), -4);
75    /// ```
76    pub fn left(&self) -> i64 {
77        self.points.iter().map(|point| point.x).min().unwrap()
78    }
79
80    /// Returns the rightmost x-coordinate in the polygon.
81    ///
82    /// # Example
83    ///
84    /// ```
85    /// # use geometry::prelude::*;
86    /// let points = vec![
87    ///     Point { x: 0, y: 0 },
88    ///     Point { x: 1, y: 2 },
89    ///     Point { x: -4, y: 5 },
90    /// ];
91    /// let polygon = Polygon::from_verts(points);
92    /// assert_eq!(polygon.right(), 1);
93    /// ```
94    pub fn right(&self) -> i64 {
95        self.points.iter().map(|point| point.x).max().unwrap()
96    }
97
98    /// Returns a the vector of points representing the polygon.
99    pub fn points(&self) -> &Vec<Point> {
100        &self.points
101    }
102
103    /// Returns the center point of the polygon.
104    ///
105    /// Returns a point with x-coordinate equal to the average of all x-coordinates
106    /// and y-coordinate equal to the average of all y-coordinates.
107    /// Note that the current behavior is to round down.
108    ///
109    /// # Example
110    ///
111    /// ```
112    /// # use geometry::prelude::*;
113    /// let points = vec![
114    ///     Point { x: 0, y: 0 },
115    ///     Point { x: 1, y: 2 },
116    ///     Point { x: -4, y: 5 },
117    /// ];
118    /// let polygon = Polygon::from_verts(points);
119    /// assert_eq!(polygon.center(), Point::new(-1, 2));
120    /// ```
121    pub fn center(&self) -> Point {
122        let x = self.points.iter().map(|point| point.x).sum::<i64>() / self.points.len() as i64;
123        let y = self.points.iter().map(|point| point.y).sum::<i64>() / self.points.len() as i64;
124        Point::new(x, y)
125    }
126}
127
128impl Bbox for Polygon {
129    fn bbox(&self) -> Option<Rect> {
130        let polygon = self;
131        Rect::from_sides_option(
132            polygon.left(),
133            polygon.bot(),
134            polygon.right(),
135            polygon.top(),
136        )
137    }
138}
139
140impl TranslateRef for Polygon {
141    fn translate_ref(&self, p: Point) -> Self {
142        Self {
143            points: self.points.translate_ref(p),
144        }
145    }
146}
147
148impl TranslateMut for Polygon {
149    fn translate_mut(&mut self, p: Point) {
150        self.points.translate_mut(p);
151    }
152}
153
154impl TransformRef for Polygon {
155    fn transform_ref(&self, trans: Transformation) -> Self {
156        Self {
157            points: self.points.transform_ref(trans),
158        }
159    }
160}
161
162impl TransformMut for Polygon {
163    fn transform_mut(&mut self, trans: Transformation) {
164        self.points.transform_mut(trans);
165    }
166}
167
168impl Contains<Point> for Polygon {
169    /// Determines if a point is contained within a polygon.
170    ///
171    /// # Example
172    ///
173    /// ```
174    /// # use geometry::prelude::*;
175    /// let points = vec![
176    ///     Point { x: -4, y: 0 },
177    ///     Point { x: 0, y: 0 },
178    ///     Point { x: 1, y: 2 },
179    ///     Point { x: 2, y: 2 },
180    ///     Point { x: -4, y: 5 },
181    /// ];
182    /// let p1 = Point::new(0,0);
183    /// let p2 = Point::new(0,4);
184    /// let p3 = Point::new(-5,3);
185    /// let p4 = Point::new(-2,4);
186    /// let p5 = Point::new(-2,2);
187    /// let polygon = Polygon::from_verts(points);
188    /// assert_eq!(polygon.contains(&p1), Containment::Full);
189    /// assert_eq!(polygon.contains(&p2), Containment::None);
190    /// assert_eq!(polygon.contains(&p3), Containment::None);
191    /// assert_eq!(polygon.contains(&p4), Containment::Full);
192    /// assert_eq!(polygon.contains(&p5), Containment::Full);
193    /// ```
194    fn contains(&self, p: &Point) -> Containment {
195        use std::cmp::{max, min};
196        let mut contains = false;
197        for i in 0..self.points().len() {
198            let p0 = self.points[i];
199            let p1 = self.points[(i + 1) % self.points.len()];
200            // Ensure counter-clockwise ordering.
201            let (p0, p1) = if p0.y < p1.y { (p0, p1) } else { (p1, p0) };
202            let miny = min(p0.y, p1.y);
203            let maxy = max(p0.y, p1.y);
204            if p.y >= miny && p.y <= maxy {
205                let dy = p1.y - p0.y;
206                let dx = p1.x - p0.x;
207                let test = -(p.x - p0.x) * dy + (p.y - p0.y) * dx;
208                match test.cmp(&0) {
209                    Ordering::Greater => {
210                        // Note: this edge cannot be horizontal.
211                        if p.y > miny {
212                            contains = !contains;
213                        }
214                    }
215                    Ordering::Equal => {
216                        if p.x >= min(p0.x, p1.x) && p.x <= max(p0.x, p1.x) {
217                            return Containment::Full;
218                        }
219                    }
220                    _ => {}
221                }
222            }
223        }
224
225        if contains {
226            Containment::Full
227        } else {
228            Containment::None
229        }
230    }
231}
232
233#[cfg(test)]
234mod tests {
235    use geometry::prelude::*;
236
237    #[test]
238    fn point_in_polygon() {
239        let points = vec![
240            Point { x: -4, y: 0 },
241            Point { x: 0, y: 0 },
242            Point { x: 1, y: 2 },
243            Point { x: 2, y: 2 },
244            Point { x: -4, y: 5 },
245        ];
246        let p1 = Point::new(0, 0);
247        let p2 = Point::new(0, 4);
248        let p3 = Point::new(-5, 3);
249        let p4 = Point::new(-2, 4);
250        let p5 = Point::new(-2, 2);
251        let polygon = Polygon::from_verts(points);
252        assert_eq!(polygon.contains(&p1), Containment::Full);
253        assert_eq!(polygon.contains(&p2), Containment::None);
254        assert_eq!(polygon.contains(&p3), Containment::None);
255        assert_eq!(polygon.contains(&p4), Containment::Full);
256        assert_eq!(polygon.contains(&p5), Containment::Full);
257
258        let points = vec![
259            Point::new(-10, 0),
260            Point::new(-10, -10),
261            Point::new(10, -10),
262            Point::new(10, 0),
263            Point::new(5, 0),
264            Point::new(5, 5),
265            Point::new(-5, 5),
266            Point::new(-5, 0),
267        ];
268
269        let polygon = Polygon::from_verts(points);
270        assert_eq!(polygon.contains(&Point::new(-10, 5)), Containment::None);
271        assert_eq!(polygon.contains(&Point::new(-10, 3)), Containment::None);
272        assert_eq!(polygon.contains(&Point::new(0, 5)), Containment::Full);
273        assert_eq!(polygon.contains(&Point::new(5, 5)), Containment::Full);
274        assert_eq!(polygon.contains(&Point::new(0, 2)), Containment::Full);
275        assert_eq!(polygon.contains(&Point::new(-5, -5)), Containment::Full);
276        assert_eq!(polygon.contains(&Point::new(-10, -10)), Containment::Full);
277        assert_eq!(polygon.contains(&Point::new(-10, -12)), Containment::None);
278        assert_eq!(polygon.contains(&Point::new(12, -10)), Containment::None);
279        assert_eq!(polygon.contains(&Point::new(7, 3)), Containment::None);
280        assert_eq!(polygon.contains(&Point::new(5, 3)), Containment::Full);
281
282        let points = vec![
283            Point::new(0, 0),
284            Point::new(0, 5),
285            Point::new(10, 5),
286            Point::new(10, 0),
287        ];
288
289        let polygon = Polygon::from_verts(points);
290        assert_eq!(polygon.contains(&Point::new(-1, 0)), Containment::None);
291        assert_eq!(polygon.contains(&Point::new(0, 0)), Containment::Full);
292        assert_eq!(polygon.contains(&Point::new(3, 0)), Containment::Full);
293        assert_eq!(polygon.contains(&Point::new(10, 0)), Containment::Full);
294        assert_eq!(polygon.contains(&Point::new(12, 0)), Containment::None);
295        assert_eq!(polygon.contains(&Point::new(-1, 5)), Containment::None);
296        assert_eq!(polygon.contains(&Point::new(0, 5)), Containment::Full);
297        assert_eq!(polygon.contains(&Point::new(3, 5)), Containment::Full);
298        assert_eq!(polygon.contains(&Point::new(10, 5)), Containment::Full);
299        assert_eq!(polygon.contains(&Point::new(12, 5)), Containment::None);
300
301        let points = vec![Point::new(0, 0), Point::new(10, 10), Point::new(20, 0)];
302
303        let polygon = Polygon::from_verts(points);
304        assert_eq!(polygon.contains(&Point::new(0, 10)), Containment::None);
305        assert_eq!(polygon.contains(&Point::new(10, 10)), Containment::Full);
306        assert_eq!(polygon.contains(&Point::new(20, 10)), Containment::None);
307        assert_eq!(polygon.contains(&Point::new(3, 3)), Containment::Full);
308        assert_eq!(polygon.contains(&Point::new(14, 6)), Containment::Full);
309        assert_eq!(polygon.contains(&Point::new(2, 1)), Containment::Full);
310        assert_eq!(polygon.contains(&Point::new(12, 7)), Containment::Full);
311        assert_eq!(polygon.contains(&Point::new(-2, 0)), Containment::None);
312        assert_eq!(polygon.contains(&Point::new(0, 0)), Containment::Full);
313        assert_eq!(polygon.contains(&Point::new(10, 0)), Containment::Full);
314        assert_eq!(polygon.contains(&Point::new(20, 0)), Containment::Full);
315        assert_eq!(polygon.contains(&Point::new(21, 0)), Containment::None);
316    }
317}
geometry/polygon.rs

geometry/
polygon.rs
