geo/algorithm/intersects/
polygon.rs

1use super::{Intersects, has_disjoint_bboxes};
2use crate::coordinate_position::CoordPos;
3use crate::{BoundingRect, CoordinatePosition, CoordsIter, LinesIter};
4use crate::{
5    Coord, CoordNum, GeoNum, Line, LineString, MultiLineString, MultiPoint, MultiPolygon, Point,
6    Polygon, Rect, Triangle,
7};
8
9impl<T> Intersects<Coord<T>> for Polygon<T>
10where
11    T: GeoNum,
12{
13    fn intersects(&self, p: &Coord<T>) -> bool {
14        self.coordinate_position(p) != CoordPos::Outside
15    }
16}
17
18symmetric_intersects_impl!(Polygon<T>, LineString<T>);
19symmetric_intersects_impl!(Polygon<T>, MultiLineString<T>);
20
21impl<T> Intersects<Line<T>> for Polygon<T>
22where
23    T: GeoNum,
24{
25    fn intersects(&self, line: &Line<T>) -> bool {
26        self.exterior().intersects(line)
27            || self.interiors().iter().any(|inner| inner.intersects(line))
28            || self.intersects(&line.start)
29            || self.intersects(&line.end)
30    }
31}
32
33symmetric_intersects_impl!(Polygon<T>, Point<T>);
34symmetric_intersects_impl!(Polygon<T>, MultiPoint<T>);
35
36impl<T> Intersects<Polygon<T>> for Polygon<T>
37where
38    T: GeoNum,
39{
40    fn intersects(&self, polygon: &Polygon<T>) -> bool {
41        if has_disjoint_bboxes(self, polygon) {
42            return false;
43        }
44
45        // if there are no line intersections among exteriors and interiors,
46        // then either one fully contains the other
47        // or they are disjoint
48
49        // check 1 point of each polygon being within the other
50        self.exterior().coords_iter().take(1).any(|p|polygon.intersects(&p))
51        || polygon.exterior().coords_iter().take(1).any(|p|self.intersects(&p))
52        // exterior exterior
53        || self.exterior().lines_iter().any(|self_line| polygon.exterior().lines_iter().any(|poly_line| self_line.intersects(&poly_line)))
54        // exterior interior
55        ||self.interiors().iter().any(|inner_line_string| polygon.exterior().intersects(inner_line_string))
56        ||polygon.interiors().iter().any(|inner_line_string| self.exterior().intersects(inner_line_string))
57
58        // interior interior (not needed)
59        /*
60           suppose interior-interior is a required check
61           this requires that there are no ext-ext intersections
62           and that there are no ext-int intersections
63           and that self-ext[0] not intersects other
64           and other-ext[0] not intersects self
65           and there is some intersection between self and other
66
67           if ext-ext disjoint, then one ext ring must be within the other ext ring
68
69           suppose self-ext is within other-ext and self-ext[0] is not intersects other
70           then self-ext[0] must be within an interior hole of other-ext
71           if self-ext does not intersect the interior ring which contains self-ext[0],
72           then self is contained within other interior hole
73           and hence self and other cannot intersect
74           therefore for self to intersect other, some part of the self-ext must intersect the other-int ring
75           However, this is a contradiction because one of the premises for requiring this check is that self-ext ring does not intersect any other-int ring
76
77           By symmetry, the mirror case of other-ext ring within self-ext ring is also true
78
79           therefore, if there cannot exist and int-int intersection when all the prior checks are false
80           and so we can skip the interior-interior check
81        */
82    }
83}
84
85symmetric_intersects_impl!(Polygon<T>, MultiPolygon<T>);
86
87symmetric_intersects_impl!(Polygon<T>, Rect<T>);
88
89symmetric_intersects_impl!(Polygon<T>, Triangle<T>);
90
91// Blanket implementation for MultiPolygon
92impl<G, T> Intersects<G> for MultiPolygon<T>
93where
94    T: GeoNum,
95    Polygon<T>: Intersects<G>,
96    G: BoundingRect<T>,
97{
98    fn intersects(&self, rhs: &G) -> bool {
99        if has_disjoint_bboxes(self, rhs) {
100            return false;
101        }
102        self.iter().any(|p| p.intersects(rhs))
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use crate::*;
109    #[test]
110    fn geom_intersects_geom() {
111        let a = Geometry::<f64>::from(polygon![]);
112        let b = Geometry::from(polygon![]);
113        assert!(!a.intersects(&b));
114    }
115}
geo/algorithm/intersects/polygon.rs

geo/algorithm/intersects/
polygon.rs
