geo_types/geometry/
polygon.rs

1use crate::{CoordFloat, CoordNum, LineString, Point, Rect, Triangle};
2use alloc::vec;
3use alloc::vec::Vec;
4use num_traits::{Float, Signed};
5
6/// A bounded two-dimensional area.
7///
8/// A `Polygon`’s outer boundary (_exterior ring_) is represented by a
9/// [`LineString`]. It may contain zero or more holes (_interior rings_), also
10/// represented by `LineString`s.
11///
12/// A `Polygon` can be created with the [`Polygon::new`] constructor or the [`polygon!`][`crate::polygon!`] macro.
13///
14/// # Semantics
15///
16/// The _boundary_ of the polygon is the union of the
17/// boundaries of the exterior and interiors. The interior
18/// is all the points inside the polygon (not on the
19/// boundary).
20///
21/// The `Polygon` structure guarantees that all exterior and interior rings will
22/// be _closed_, such that the first and last `Coord` of each ring has
23/// the same value.
24///
25/// # Validity
26///
27/// - The exterior and interior rings must be valid
28///   `LinearRing`s (see [`LineString`]).
29///
30/// - No two rings in the boundary may cross, and may
31///   intersect at a `Point` only as a tangent. In other
32///   words, the rings must be distinct, and for every pair of
33///   common points in two of the rings, there must be a
34///   neighborhood (a topological open set) around one that
35///   does not contain the other point.
36///
37/// - The closure of the interior of the `Polygon` must
38///   equal the `Polygon` itself. For instance, the exterior
39///   may not contain a spike.
40///
41/// - The interior of the polygon must be a connected
42///   point-set. That is, any two distinct points in the
43///   interior must admit a curve between these two that lies
44///   in the interior.
45///
46/// Refer to section 6.1.11.1 of the OGC-SFA for a formal
47/// definition of validity. Besides the closed `LineString`
48/// guarantee, the `Polygon` structure does not enforce
49/// validity at this time. For example, it is possible to
50/// construct a `Polygon` that has:
51///
52/// - fewer than 3 coordinates per `LineString` ring
53/// - interior rings that intersect other interior rings
54/// - interior rings that extend beyond the exterior ring
55///
56/// # `LineString` closing operation
57///
58/// Some APIs on `Polygon` result in a closing operation on a `LineString`. The
59/// operation is as follows:
60///
61/// If a `LineString`’s first and last `Coord` have different values, a
62/// new `Coord` will be appended to the `LineString` with a value equal to
63/// the first `Coord`.
64///
65/// [`LineString`]: line_string/struct.LineString.html
66#[derive(Eq, PartialEq, Clone, Hash)]
67#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
68pub struct Polygon<T: CoordNum = f64> {
69    exterior: LineString<T>,
70    interiors: Vec<LineString<T>>,
71}
72
73impl<T: CoordNum> Polygon<T> {
74    /// Create a new `Polygon` with the provided exterior `LineString` ring and
75    /// interior `LineString` rings.
76    ///
77    /// Upon calling `new`, the exterior and interior `LineString` rings [will
78    /// be closed].
79    ///
80    /// [will be closed]: #linestring-closing-operation
81    ///
82    /// # Examples
83    ///
84    /// Creating a `Polygon` with no interior rings:
85    ///
86    /// ```
87    /// use geo_types::{LineString, Polygon};
88    ///
89    /// let polygon = Polygon::new(
90    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
91    ///     vec![],
92    /// );
93    /// ```
94    ///
95    /// Creating a `Polygon` with an interior ring:
96    ///
97    /// ```
98    /// use geo_types::{LineString, Polygon};
99    ///
100    /// let polygon = Polygon::new(
101    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
102    ///     vec![LineString::from(vec![
103    ///         (0.1, 0.1),
104    ///         (0.9, 0.9),
105    ///         (0.9, 0.1),
106    ///         (0.1, 0.1),
107    ///     ])],
108    /// );
109    /// ```
110    ///
111    /// If the first and last `Coord`s of the exterior or interior
112    /// `LineString`s no longer match, those `LineString`s [will be closed]:
113    ///
114    /// ```
115    /// use geo_types::{coord, LineString, Polygon};
116    ///
117    /// let mut polygon = Polygon::new(LineString::from(vec![(0., 0.), (1., 1.), (1., 0.)]), vec![]);
118    ///
119    /// assert_eq!(
120    ///     polygon.exterior(),
121    ///     &LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.),])
122    /// );
123    /// ```
124    pub fn new(mut exterior: LineString<T>, mut interiors: Vec<LineString<T>>) -> Self {
125        exterior.close();
126        for interior in &mut interiors {
127            interior.close();
128        }
129        Self {
130            exterior,
131            interiors,
132        }
133    }
134
135    /// Consume the `Polygon`, returning the exterior `LineString` ring and
136    /// a vector of the interior `LineString` rings.
137    ///
138    /// # Examples
139    ///
140    /// ```
141    /// use geo_types::{LineString, Polygon};
142    ///
143    /// let mut polygon = Polygon::new(
144    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
145    ///     vec![LineString::from(vec![
146    ///         (0.1, 0.1),
147    ///         (0.9, 0.9),
148    ///         (0.9, 0.1),
149    ///         (0.1, 0.1),
150    ///     ])],
151    /// );
152    ///
153    /// let (exterior, interiors) = polygon.into_inner();
154    ///
155    /// assert_eq!(
156    ///     exterior,
157    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.),])
158    /// );
159    ///
160    /// assert_eq!(
161    ///     interiors,
162    ///     vec![LineString::from(vec![
163    ///         (0.1, 0.1),
164    ///         (0.9, 0.9),
165    ///         (0.9, 0.1),
166    ///         (0.1, 0.1),
167    ///     ])]
168    /// );
169    /// ```
170    pub fn into_inner(self) -> (LineString<T>, Vec<LineString<T>>) {
171        (self.exterior, self.interiors)
172    }
173
174    /// Return a reference to the exterior `LineString` ring.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// use geo_types::{LineString, Polygon};
180    ///
181    /// let exterior = LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]);
182    ///
183    /// let polygon = Polygon::new(exterior.clone(), vec![]);
184    ///
185    /// assert_eq!(polygon.exterior(), &exterior);
186    /// ```
187    pub fn exterior(&self) -> &LineString<T> {
188        &self.exterior
189    }
190
191    /// Execute the provided closure `f`, which is provided with a mutable
192    /// reference to the exterior `LineString` ring.
193    ///
194    /// After the closure executes, the exterior `LineString` [will be closed].
195    ///
196    /// # Examples
197    ///
198    /// ```
199    /// use geo_types::{coord, LineString, Polygon};
200    ///
201    /// let mut polygon = Polygon::new(
202    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
203    ///     vec![],
204    /// );
205    ///
206    /// polygon.exterior_mut(|exterior| {
207    ///     exterior.0[1] = coord! { x: 1., y: 2. };
208    /// });
209    ///
210    /// assert_eq!(
211    ///     polygon.exterior(),
212    ///     &LineString::from(vec![(0., 0.), (1., 2.), (1., 0.), (0., 0.),])
213    /// );
214    /// ```
215    ///
216    /// If the first and last `Coord`s of the exterior `LineString` no
217    /// longer match, the `LineString` [will be closed]:
218    ///
219    /// ```
220    /// use geo_types::{coord, LineString, Polygon};
221    ///
222    /// let mut polygon = Polygon::new(
223    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
224    ///     vec![],
225    /// );
226    ///
227    /// polygon.exterior_mut(|exterior| {
228    ///     exterior.0[0] = coord! { x: 0., y: 1. };
229    /// });
230    ///
231    /// assert_eq!(
232    ///     polygon.exterior(),
233    ///     &LineString::from(vec![(0., 1.), (1., 1.), (1., 0.), (0., 0.), (0., 1.),])
234    /// );
235    /// ```
236    ///
237    /// [will be closed]: #linestring-closing-operation
238    pub fn exterior_mut<F>(&mut self, f: F)
239    where
240        F: FnOnce(&mut LineString<T>),
241    {
242        f(&mut self.exterior);
243        self.exterior.close();
244    }
245
246    /// Fallible alternative to [`exterior_mut`](Polygon::exterior_mut).
247    pub fn try_exterior_mut<F, E>(&mut self, f: F) -> Result<(), E>
248    where
249        F: FnOnce(&mut LineString<T>) -> Result<(), E>,
250    {
251        f(&mut self.exterior)?;
252        self.exterior.close();
253        Ok(())
254    }
255
256    /// Return a slice of the interior `LineString` rings.
257    ///
258    /// # Examples
259    ///
260    /// ```
261    /// use geo_types::{coord, LineString, Polygon};
262    ///
263    /// let interiors = vec![LineString::from(vec![
264    ///     (0.1, 0.1),
265    ///     (0.9, 0.9),
266    ///     (0.9, 0.1),
267    ///     (0.1, 0.1),
268    /// ])];
269    ///
270    /// let polygon = Polygon::new(
271    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
272    ///     interiors.clone(),
273    /// );
274    ///
275    /// assert_eq!(interiors, polygon.interiors());
276    /// ```
277    pub fn interiors(&self) -> &[LineString<T>] {
278        &self.interiors
279    }
280
281    /// Execute the provided closure `f`, which is provided with a mutable
282    /// reference to the interior `LineString` rings.
283    ///
284    /// After the closure executes, each of the interior `LineString`s [will be
285    /// closed].
286    ///
287    /// # Examples
288    ///
289    /// ```
290    /// use geo_types::{coord, LineString, Polygon};
291    ///
292    /// let mut polygon = Polygon::new(
293    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
294    ///     vec![LineString::from(vec![
295    ///         (0.1, 0.1),
296    ///         (0.9, 0.9),
297    ///         (0.9, 0.1),
298    ///         (0.1, 0.1),
299    ///     ])],
300    /// );
301    ///
302    /// polygon.interiors_mut(|interiors| {
303    ///     interiors[0].0[1] = coord! { x: 0.8, y: 0.8 };
304    /// });
305    ///
306    /// assert_eq!(
307    ///     polygon.interiors(),
308    ///     &[LineString::from(vec![
309    ///         (0.1, 0.1),
310    ///         (0.8, 0.8),
311    ///         (0.9, 0.1),
312    ///         (0.1, 0.1),
313    ///     ])]
314    /// );
315    /// ```
316    ///
317    /// If the first and last `Coord`s of any interior `LineString` no
318    /// longer match, those `LineString`s [will be closed]:
319    ///
320    /// ```
321    /// use geo_types::{coord, LineString, Polygon};
322    ///
323    /// let mut polygon = Polygon::new(
324    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
325    ///     vec![LineString::from(vec![
326    ///         (0.1, 0.1),
327    ///         (0.9, 0.9),
328    ///         (0.9, 0.1),
329    ///         (0.1, 0.1),
330    ///     ])],
331    /// );
332    ///
333    /// polygon.interiors_mut(|interiors| {
334    ///     interiors[0].0[0] = coord! { x: 0.1, y: 0.2 };
335    /// });
336    ///
337    /// assert_eq!(
338    ///     polygon.interiors(),
339    ///     &[LineString::from(vec![
340    ///         (0.1, 0.2),
341    ///         (0.9, 0.9),
342    ///         (0.9, 0.1),
343    ///         (0.1, 0.1),
344    ///         (0.1, 0.2),
345    ///     ])]
346    /// );
347    /// ```
348    ///
349    /// [will be closed]: #linestring-closing-operation
350    pub fn interiors_mut<F>(&mut self, f: F)
351    where
352        F: FnOnce(&mut [LineString<T>]),
353    {
354        f(&mut self.interiors);
355        for interior in &mut self.interiors {
356            interior.close();
357        }
358    }
359
360    /// Fallible alternative to [`interiors_mut`](Self::interiors_mut).
361    pub fn try_interiors_mut<F, E>(&mut self, f: F) -> Result<(), E>
362    where
363        F: FnOnce(&mut [LineString<T>]) -> Result<(), E>,
364    {
365        f(&mut self.interiors)?;
366        for interior in &mut self.interiors {
367            interior.close();
368        }
369        Ok(())
370    }
371
372    /// Add an interior ring to the `Polygon`.
373    ///
374    /// The new `LineString` interior ring [will be closed]:
375    ///
376    /// # Examples
377    ///
378    /// ```
379    /// use geo_types::{coord, LineString, Polygon};
380    ///
381    /// let mut polygon = Polygon::new(
382    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
383    ///     vec![],
384    /// );
385    ///
386    /// assert_eq!(polygon.interiors().len(), 0);
387    ///
388    /// polygon.interiors_push(vec![(0.1, 0.1), (0.9, 0.9), (0.9, 0.1)]);
389    ///
390    /// assert_eq!(
391    ///     polygon.interiors(),
392    ///     &[LineString::from(vec![
393    ///         (0.1, 0.1),
394    ///         (0.9, 0.9),
395    ///         (0.9, 0.1),
396    ///         (0.1, 0.1),
397    ///     ])]
398    /// );
399    /// ```
400    ///
401    /// [will be closed]: #linestring-closing-operation
402    pub fn interiors_push(&mut self, new_interior: impl Into<LineString<T>>) {
403        let mut new_interior = new_interior.into();
404        new_interior.close();
405        self.interiors.push(new_interior);
406    }
407
408    /// Wrap-around previous-vertex
409    fn previous_vertex(&self, current_vertex: usize) -> usize
410    where
411        T: Float,
412    {
413        (current_vertex + (self.exterior.0.len() - 1) - 1) % (self.exterior.0.len() - 1)
414    }
415
416    /// Count the total number of rings (interior and exterior) in the polygon
417    ///
418    /// # Examples
419    ///
420    /// ```
421    /// use geo_types::{coord, LineString, Polygon};
422    ///
423    /// let polygon = Polygon::new(
424    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
425    ///     vec![],
426    /// );
427    ///
428    /// assert_eq!(polygon.num_rings(), 1);
429    ///
430    /// let polygon = Polygon::new(
431    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
432    ///     vec![LineString::from(vec![(0.1, 0.1), (0.9, 0.9), (0.9, 0.1)])],
433    /// );
434    ///
435    /// assert_eq!(polygon.num_rings(), 2);
436    /// ```
437    pub fn num_rings(&self) -> usize {
438        self.num_interior_rings() + 1
439    }
440
441    /// Count the number of interior rings in the polygon
442    ///
443    /// # Examples
444    ///
445    /// ```
446    /// use geo_types::{coord, LineString, Polygon};
447    ///
448    /// let polygon = Polygon::new(
449    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
450    ///     vec![],
451    /// );
452    ///
453    /// assert_eq!(polygon.num_interior_rings(), 0);
454    ///
455    /// let polygon = Polygon::new(
456    ///     LineString::from(vec![(0., 0.), (1., 1.), (1., 0.), (0., 0.)]),
457    ///     vec![LineString::from(vec![(0.1, 0.1), (0.9, 0.9), (0.9, 0.1)])],
458    /// );
459    ///
460    /// assert_eq!(polygon.num_interior_rings(), 1);
461    /// ```
462    pub fn num_interior_rings(&self) -> usize {
463        self.interiors.len()
464    }
465}
466
467// used to check the sign of a vec of floats
468#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
469enum ListSign {
470    Empty,
471    Positive,
472    Negative,
473    Mixed,
474}
475
476impl<T: CoordFloat + Signed> Polygon<T> {
477    /// Determine whether a Polygon is convex
478    // For each consecutive pair of edges of the polygon (each triplet of points),
479    // compute the z-component of the cross product of the vectors defined by the
480    // edges pointing towards the points in increasing order.
481    // Take the cross product of these vectors
482    // The polygon is convex if the z-components of the cross products are either
483    // all positive or all negative. Otherwise, the polygon is non-convex.
484    // see: http://stackoverflow.com/a/1881201/416626
485    #[deprecated(
486        since = "0.6.1",
487        note = "Please use `geo::is_convex` on `poly.exterior()` instead"
488    )]
489    pub fn is_convex(&self) -> bool {
490        let convex = self
491            .exterior
492            .0
493            .iter()
494            .enumerate()
495            .map(|(idx, _)| {
496                let prev_1 = self.previous_vertex(idx);
497                let prev_2 = self.previous_vertex(prev_1);
498                Point::from(self.exterior[prev_2]).cross_prod(
499                    Point::from(self.exterior[prev_1]),
500                    Point::from(self.exterior[idx]),
501                )
502            })
503            // accumulate and check cross-product result signs in a single pass
504            // positive implies ccw convexity, negative implies cw convexity
505            // anything else implies non-convexity
506            .fold(ListSign::Empty, |acc, n| match (acc, n.is_positive()) {
507                (ListSign::Empty, true) | (ListSign::Positive, true) => ListSign::Positive,
508                (ListSign::Empty, false) | (ListSign::Negative, false) => ListSign::Negative,
509                _ => ListSign::Mixed,
510            });
511        convex != ListSign::Mixed
512    }
513}
514
515impl<T: CoordNum> From<Rect<T>> for Polygon<T> {
516    fn from(r: Rect<T>) -> Self {
517        Polygon::new(
518            vec![
519                (r.min().x, r.min().y),
520                (r.max().x, r.min().y),
521                (r.max().x, r.max().y),
522                (r.min().x, r.max().y),
523                (r.min().x, r.min().y),
524            ]
525            .into(),
526            Vec::new(),
527        )
528    }
529}
530
531impl<T: CoordNum> From<Triangle<T>> for Polygon<T> {
532    fn from(t: Triangle<T>) -> Self {
533        Polygon::new(vec![t.0, t.1, t.2, t.0].into(), Vec::new())
534    }
535}
536
537#[cfg(any(feature = "approx", test))]
538mod approx_integration {
539    use super::*;
540    use approx::{AbsDiffEq, RelativeEq, UlpsEq};
541
542    impl<T> RelativeEq for Polygon<T>
543    where
544        T: CoordNum + RelativeEq<Epsilon = T>,
545    {
546        #[inline]
547        fn default_max_relative() -> Self::Epsilon {
548            T::default_max_relative()
549        }
550
551        /// Equality assertion within a relative limit.
552        ///
553        /// # Examples
554        ///
555        /// ```
556        /// use geo_types::{Polygon, polygon};
557        ///
558        /// let a: Polygon<f32> = polygon![(x: 0., y: 0.), (x: 5., y: 0.), (x: 7., y: 9.), (x: 0., y: 0.)];
559        /// let b: Polygon<f32> = polygon![(x: 0., y: 0.), (x: 5., y: 0.), (x: 7.01, y: 9.), (x: 0., y: 0.)];
560        ///
561        /// approx::assert_relative_eq!(a, b, max_relative=0.1);
562        /// approx::assert_relative_ne!(a, b, max_relative=0.001);
563        /// ```
564        ///
565        fn relative_eq(
566            &self,
567            other: &Self,
568            epsilon: Self::Epsilon,
569            max_relative: Self::Epsilon,
570        ) -> bool {
571            if !self
572                .exterior
573                .relative_eq(&other.exterior, epsilon, max_relative)
574            {
575                return false;
576            }
577
578            if self.interiors.len() != other.interiors.len() {
579                return false;
580            }
581            let mut zipper = self.interiors.iter().zip(other.interiors.iter());
582            zipper.all(|(lhs, rhs)| lhs.relative_eq(rhs, epsilon, max_relative))
583        }
584    }
585
586    impl<T> AbsDiffEq for Polygon<T>
587    where
588        T: CoordNum + AbsDiffEq<Epsilon = T>,
589    {
590        type Epsilon = T;
591
592        #[inline]
593        fn default_epsilon() -> Self::Epsilon {
594            T::default_epsilon()
595        }
596
597        /// Equality assertion with an absolute limit.
598        ///
599        /// # Examples
600        ///
601        /// ```
602        /// use geo_types::{Polygon, polygon};
603        ///
604        /// let a: Polygon<f32> = polygon![(x: 0., y: 0.), (x: 5., y: 0.), (x: 7., y: 9.), (x: 0., y: 0.)];
605        /// let b: Polygon<f32> = polygon![(x: 0., y: 0.), (x: 5., y: 0.), (x: 7.01, y: 9.), (x: 0., y: 0.)];
606        ///
607        /// approx::assert_abs_diff_eq!(a, b, epsilon=0.1);
608        /// approx::assert_abs_diff_ne!(a, b, epsilon=0.001);
609        /// ```
610        fn abs_diff_eq(&self, other: &Self, epsilon: Self::Epsilon) -> bool {
611            if !self.exterior.abs_diff_eq(&other.exterior, epsilon) {
612                return false;
613            }
614
615            if self.interiors.len() != other.interiors.len() {
616                return false;
617            }
618            let mut zipper = self.interiors.iter().zip(other.interiors.iter());
619            zipper.all(|(lhs, rhs)| lhs.abs_diff_eq(rhs, epsilon))
620        }
621    }
622
623    impl<T> UlpsEq for Polygon<T>
624    where
625        T: CoordNum + UlpsEq<Epsilon = T>,
626    {
627        fn default_max_ulps() -> u32 {
628            T::default_max_ulps()
629        }
630
631        fn ulps_eq(&self, other: &Self, epsilon: Self::Epsilon, max_ulps: u32) -> bool {
632            if !self.exterior.ulps_eq(&other.exterior, epsilon, max_ulps) {
633                return false;
634            }
635            if self.interiors.len() != other.interiors.len() {
636                return false;
637            }
638            let mut zipper = self.interiors.iter().zip(other.interiors.iter());
639            zipper.all(|(lhs, rhs)| lhs.ulps_eq(rhs, epsilon, max_ulps))
640        }
641    }
642}
643
644#[cfg(any(
645    feature = "rstar_0_8",
646    feature = "rstar_0_9",
647    feature = "rstar_0_10",
648    feature = "rstar_0_11",
649    feature = "rstar_0_12"
650))]
651macro_rules! impl_rstar_polygon {
652    ($rstar:ident) => {
653        impl<T> $rstar::RTreeObject for Polygon<T>
654        where
655            T: ::num_traits::Float + ::$rstar::RTreeNum,
656        {
657            type Envelope = ::$rstar::AABB<Point<T>>;
658
659            fn envelope(&self) -> Self::Envelope {
660                self.exterior.envelope()
661            }
662        }
663    };
664}
665
666#[cfg(feature = "rstar_0_8")]
667impl_rstar_polygon!(rstar_0_8);
668
669#[cfg(feature = "rstar_0_9")]
670impl_rstar_polygon!(rstar_0_9);
671
672#[cfg(feature = "rstar_0_10")]
673impl_rstar_polygon!(rstar_0_10);
674
675#[cfg(feature = "rstar_0_11")]
676impl_rstar_polygon!(rstar_0_11);
677
678#[cfg(feature = "rstar_0_12")]
679impl_rstar_polygon!(rstar_0_12);
geo_types/geometry/polygon.rs

geo_types/geometry/
polygon.rs
