geo/algorithm/contains/
mod.rs

1/// Checks if `rhs` is completely contained within `self`.
2/// More formally, the interior of `rhs` has non-empty
3/// (set-theoretic) intersection but neither the interior,
4/// nor the boundary of `rhs` intersects the exterior of
5/// `self`. In other words, the [DE-9IM] intersection matrix
6/// of `(rhs, self)` is `T*F**F***`.
7///
8/// [DE-9IM]: https://en.wikipedia.org/wiki/DE-9IM
9///
10/// # Examples
11///
12/// ```
13/// use geo::Contains;
14/// use geo::{line_string, point, Polygon};
15///
16/// let line_string = line_string![
17///     (x: 0., y: 0.),
18///     (x: 2., y: 0.),
19///     (x: 2., y: 2.),
20///     (x: 0., y: 2.),
21///     (x: 0., y: 0.),
22/// ];
23///
24/// let polygon = Polygon::new(line_string.clone(), vec![]);
25///
26/// // Point in Point
27/// assert!(point!(x: 2., y: 0.).contains(&point!(x: 2., y: 0.)));
28///
29/// // Point in Linestring
30/// assert!(line_string.contains(&point!(x: 2., y: 0.)));
31///
32/// // Point in Polygon
33/// assert!(polygon.contains(&point!(x: 1., y: 1.)));
34/// ```
35pub trait Contains<Rhs = Self> {
36    fn contains(&self, rhs: &Rhs) -> bool;
37}
38
39mod geometry;
40mod geometry_collection;
41mod line;
42mod line_string;
43mod point;
44mod polygon;
45mod rect;
46mod triangle;
47
48macro_rules! impl_contains_from_relate {
49    ($for:ty,  [$($target:ty),*]) => {
50        $(
51            impl<T> Contains<$target> for $for
52            where
53                T: GeoFloat
54            {
55                fn contains(&self, target: &$target) -> bool {
56                    use $crate::algorithm::Relate;
57                    self.relate(target).is_contains()
58                }
59            }
60        )*
61    };
62}
63pub(crate) use impl_contains_from_relate;
64
65macro_rules! impl_contains_geometry_for {
66    ($geom_type: ty) => {
67        impl<T> Contains<Geometry<T>> for $geom_type
68        where
69            T: GeoFloat,
70        {
71            fn contains(&self, geometry: &Geometry<T>) -> bool {
72                match geometry {
73                    Geometry::Point(g) => self.contains(g),
74                    Geometry::Line(g) => self.contains(g),
75                    Geometry::LineString(g) => self.contains(g),
76                    Geometry::Polygon(g) => self.contains(g),
77                    Geometry::MultiPoint(g) => self.contains(g),
78                    Geometry::MultiLineString(g) => self.contains(g),
79                    Geometry::MultiPolygon(g) => self.contains(g),
80                    Geometry::GeometryCollection(g) => self.contains(g),
81                    Geometry::Rect(g) => self.contains(g),
82                    Geometry::Triangle(g) => self.contains(g),
83                }
84            }
85        }
86    };
87}
88pub(crate) use impl_contains_geometry_for;
89
90// ┌───────┐
91// │ Tests │
92// └───────┘
93
94#[cfg(test)]
95mod test {
96    use crate::line_string;
97    use crate::Contains;
98    use crate::{coord, Coord, Line, LineString, MultiPolygon, Point, Polygon, Rect, Triangle};
99
100    #[test]
101    // see https://github.com/georust/geo/issues/452
102    fn linestring_contains_point() {
103        let line_string = LineString::from(vec![(0., 0.), (3., 3.)]);
104        let point_on_line = Point::new(1., 1.);
105        assert!(line_string.contains(&point_on_line));
106    }
107    #[test]
108    // V doesn't contain rect because two of its edges intersect with V's exterior boundary
109    fn polygon_does_not_contain_polygon() {
110        let v = Polygon::new(
111            vec![
112                (150., 350.),
113                (100., 350.),
114                (210., 160.),
115                (290., 350.),
116                (250., 350.),
117                (200., 250.),
118                (150., 350.),
119            ]
120            .into(),
121            vec![],
122        );
123        let rect = Polygon::new(
124            vec![
125                (250., 310.),
126                (150., 310.),
127                (150., 280.),
128                (250., 280.),
129                (250., 310.),
130            ]
131            .into(),
132            vec![],
133        );
134        assert!(!v.contains(&rect));
135    }
136    #[test]
137    // V contains rect because all its vertices are contained, and none of its edges intersect with V's boundaries
138    fn polygon_contains_polygon() {
139        let v = Polygon::new(
140            vec![
141                (150., 350.),
142                (100., 350.),
143                (210., 160.),
144                (290., 350.),
145                (250., 350.),
146                (200., 250.),
147                (150., 350.),
148            ]
149            .into(),
150            vec![],
151        );
152        let rect = Polygon::new(
153            vec![
154                (185., 237.),
155                (220., 237.),
156                (220., 220.),
157                (185., 220.),
158                (185., 237.),
159            ]
160            .into(),
161            vec![],
162        );
163        assert!(v.contains(&rect));
164    }
165    #[test]
166    // LineString is fully contained
167    fn linestring_fully_contained_in_polygon() {
168        let poly = Polygon::new(
169            LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
170            vec![],
171        );
172        let ls = LineString::from(vec![(3.0, 0.5), (3.0, 3.5)]);
173        assert!(poly.contains(&ls));
174    }
175    /// Tests: Point in LineString
176    #[test]
177    fn empty_linestring_test() {
178        let linestring = LineString::new(Vec::new());
179        assert!(!linestring.contains(&Point::new(2., 1.)));
180    }
181    #[test]
182    fn linestring_point_is_vertex_test() {
183        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.)]);
184        // Note: the end points of a linestring are not
185        // considered to be "contained"
186        assert!(linestring.contains(&Point::new(2., 0.)));
187        assert!(!linestring.contains(&Point::new(0., 0.)));
188        assert!(!linestring.contains(&Point::new(2., 2.)));
189    }
190    #[test]
191    fn linestring_test() {
192        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.)]);
193        assert!(linestring.contains(&Point::new(1., 0.)));
194    }
195    /// Tests: Point in Polygon
196    #[test]
197    fn empty_polygon_test() {
198        let linestring = LineString::new(Vec::new());
199        let poly = Polygon::new(linestring, Vec::new());
200        assert!(!poly.contains(&Point::new(2., 1.)));
201    }
202    #[test]
203    fn polygon_with_one_point_test() {
204        let linestring = LineString::from(vec![(2., 1.)]);
205        let poly = Polygon::new(linestring, Vec::new());
206        assert!(!poly.contains(&Point::new(3., 1.)));
207    }
208    #[test]
209    fn polygon_with_one_point_is_vertex_test() {
210        let linestring = LineString::from(vec![(2., 1.)]);
211        let poly = Polygon::new(linestring, Vec::new());
212        assert!(!poly.contains(&Point::new(2., 1.)));
213    }
214    #[test]
215    fn polygon_with_point_on_boundary_test() {
216        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
217        let poly = Polygon::new(linestring, Vec::new());
218        assert!(!poly.contains(&Point::new(1., 0.)));
219        assert!(!poly.contains(&Point::new(2., 1.)));
220        assert!(!poly.contains(&Point::new(1., 2.)));
221        assert!(!poly.contains(&Point::new(0., 1.)));
222    }
223    #[test]
224    fn point_in_polygon_test() {
225        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
226        let poly = Polygon::new(linestring, Vec::new());
227        assert!(poly.contains(&Point::new(1., 1.)));
228    }
229    #[test]
230    fn point_in_polygon_with_ray_passing_through_a_vertex_test() {
231        let linestring = LineString::from(vec![(1., 0.), (0., 1.), (-1., 0.), (0., -1.)]);
232        let poly = Polygon::new(linestring, Vec::new());
233        assert!(poly.contains(&Point::new(0., 0.)));
234    }
235    #[test]
236    fn point_in_polygon_with_ray_passing_through_a_vertex_and_not_crossing() {
237        let linestring = LineString::from(vec![
238            (0., 0.),
239            (2., 0.),
240            (3., 1.),
241            (4., 0.),
242            (4., 2.),
243            (0., 2.),
244            (0., 0.),
245        ]);
246        let poly = Polygon::new(linestring, Vec::new());
247        assert!(poly.contains(&Point::new(1., 1.)));
248    }
249    #[test]
250    fn point_out_polygon_test() {
251        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
252        let poly = Polygon::new(linestring, Vec::new());
253        assert!(!poly.contains(&Point::new(2.1, 1.)));
254        assert!(!poly.contains(&Point::new(1., 2.1)));
255        assert!(!poly.contains(&Point::new(2.1, 2.1)));
256    }
257    #[test]
258    fn point_polygon_with_inner_test() {
259        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
260        let inner_linestring = LineString::from(vec![
261            [0.5, 0.5],
262            [1.5, 0.5],
263            [1.5, 1.5],
264            [0.0, 1.5],
265            [0.0, 0.0],
266        ]);
267        let poly = Polygon::new(linestring, vec![inner_linestring]);
268        assert!(!poly.contains(&Point::new(0.25, 0.25)));
269        assert!(!poly.contains(&Point::new(1., 1.)));
270        assert!(!poly.contains(&Point::new(1.5, 1.5)));
271        assert!(!poly.contains(&Point::new(1.5, 1.)));
272    }
273
274    /// Tests: Point in MultiPolygon
275    #[test]
276    fn empty_multipolygon_test() {
277        let multipoly = MultiPolygon::new(Vec::new());
278        assert!(!multipoly.contains(&Point::new(2., 1.)));
279    }
280    #[test]
281    fn empty_multipolygon_two_polygons_test() {
282        let poly1 = Polygon::new(
283            LineString::from(vec![(0., 0.), (1., 0.), (1., 1.), (0., 1.), (0., 0.)]),
284            Vec::new(),
285        );
286        let poly2 = Polygon::new(
287            LineString::from(vec![(2., 0.), (3., 0.), (3., 1.), (2., 1.), (2., 0.)]),
288            Vec::new(),
289        );
290        let multipoly = MultiPolygon::new(vec![poly1, poly2]);
291        assert!(multipoly.contains(&Point::new(0.5, 0.5)));
292        assert!(multipoly.contains(&Point::new(2.5, 0.5)));
293        assert!(!multipoly.contains(&Point::new(1.5, 0.5)));
294    }
295    #[test]
296    fn empty_multipolygon_two_polygons_and_inner_test() {
297        let poly1 = Polygon::new(
298            LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
299            vec![LineString::from(vec![
300                (1., 1.),
301                (4., 1.),
302                (4., 4.),
303                (1., 1.),
304            ])],
305        );
306        let poly2 = Polygon::new(
307            LineString::from(vec![(9., 0.), (14., 0.), (14., 4.), (9., 4.), (9., 0.)]),
308            Vec::new(),
309        );
310
311        let multipoly = MultiPolygon::new(vec![poly1, poly2]);
312        assert!(multipoly.contains(&Point::new(3., 5.)));
313        assert!(multipoly.contains(&Point::new(12., 2.)));
314        assert!(!multipoly.contains(&Point::new(3., 2.)));
315        assert!(!multipoly.contains(&Point::new(7., 2.)));
316    }
317    /// Tests: LineString in Polygon
318    #[test]
319    fn linestring_in_polygon_with_linestring_is_boundary_test() {
320        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
321        let poly = Polygon::new(linestring.clone(), Vec::new());
322        assert!(!poly.contains(&linestring));
323        assert!(!poly.contains(&LineString::from(vec![(0., 0.), (2., 0.)])));
324        assert!(!poly.contains(&LineString::from(vec![(2., 0.), (2., 2.)])));
325        assert!(!poly.contains(&LineString::from(vec![(0., 2.), (0., 0.)])));
326    }
327    #[test]
328    fn linestring_outside_polygon_test() {
329        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
330        let poly = Polygon::new(linestring, Vec::new());
331        assert!(!poly.contains(&LineString::from(vec![(1., 1.), (3., 0.)])));
332        assert!(!poly.contains(&LineString::from(vec![(3., 0.), (5., 2.)])));
333    }
334    #[test]
335    fn linestring_in_inner_polygon_test() {
336        let poly = Polygon::new(
337            LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
338            vec![LineString::from(vec![
339                (1., 1.),
340                (4., 1.),
341                (4., 4.),
342                (1., 4.),
343                (1., 1.),
344            ])],
345        );
346        assert!(!poly.contains(&LineString::from(vec![(2., 2.), (3., 3.)])));
347        assert!(!poly.contains(&LineString::from(vec![(2., 2.), (2., 5.)])));
348        assert!(!poly.contains(&LineString::from(vec![(3., 0.5), (3., 5.)])));
349    }
350    #[test]
351    fn bounding_rect_in_inner_bounding_rect_test() {
352        let bounding_rect_xl =
353            Rect::new(coord! { x: -100., y: -200. }, coord! { x: 100., y: 200. });
354        let bounding_rect_sm = Rect::new(coord! { x: -10., y: -20. }, coord! { x: 10., y: 20. });
355        assert!(bounding_rect_xl.contains(&bounding_rect_sm));
356        assert!(!bounding_rect_sm.contains(&bounding_rect_xl));
357    }
358    #[test]
359    fn point_in_line_test() {
360        let c = |x, y| coord! { x: x, y: y };
361        let p0 = c(2., 4.);
362        // vertical line
363        let line1 = Line::new(c(2., 0.), c(2., 5.));
364        // point on line, but outside line segment
365        let line2 = Line::new(c(0., 6.), c(1.5, 4.5));
366        // point on line
367        let line3 = Line::new(c(0., 6.), c(3., 3.));
368        assert!(line1.contains(&Point::from(p0)));
369        assert!(!line2.contains(&Point::from(p0)));
370        assert!(line3.contains(&Point::from(p0)));
371    }
372    #[test]
373    fn line_in_line_test() {
374        let c = |x, y| coord! { x: x, y: y };
375        let line0 = Line::new(c(0., 1.), c(3., 4.));
376        // first point on line0, second not
377        let line1 = Line::new(c(1., 2.), c(2., 2.));
378        // co-linear, but extends past the end of line0
379        let line2 = Line::new(c(1., 2.), c(4., 5.));
380        // contained in line0
381        let line3 = Line::new(c(1., 2.), c(3., 4.));
382        assert!(!line0.contains(&line1));
383        assert!(!line0.contains(&line2));
384        assert!(line0.contains(&line3));
385    }
386    #[test]
387    fn linestring_in_line_test() {
388        let line = Line::from([(0, 10), (30, 40)]);
389        // linestring0 in line
390        let linestring0 = LineString::from(vec![(1, 11), (10, 20), (15, 25)]);
391        // linestring1 starts and ends in line, but wanders in the middle
392        let linestring1 = LineString::from(vec![(1, 11), (20, 20), (15, 25)]);
393        // linestring2 is co-linear, but extends beyond line
394        let linestring2 = LineString::from(vec![(1, 11), (10, 20), (40, 50)]);
395        // no part of linestring3 is contained in line
396        let linestring3 = LineString::from(vec![(11, 11), (20, 20), (25, 25)]);
397        // a linestring with singleton interior on the boundary of the line
398        let linestring4 = LineString::from(vec![(0, 10), (0, 10), (0, 10)]);
399        // a linestring with singleton interior that is contained in the line
400        let linestring5 = LineString::from(vec![(1, 11), (1, 11), (1, 11)]);
401        assert!(line.contains(&linestring0));
402        assert!(!line.contains(&linestring1));
403        assert!(!line.contains(&linestring2));
404        assert!(!line.contains(&linestring3));
405        assert!(!line.contains(&linestring4));
406        assert!(line.contains(&linestring5));
407    }
408    #[test]
409    fn line_in_polygon_test() {
410        let c = |x, y| coord! { x: x, y: y };
411        let line = Line::new(c(0.0, 10.0), c(30.0, 40.0));
412        let linestring0 = line_string![
413            c(-10.0, 0.0),
414            c(50.0, 0.0),
415            c(50.0, 50.0),
416            c(0.0, 50.0),
417            c(-10.0, 0.0)
418        ];
419        let poly0 = Polygon::new(linestring0, Vec::new());
420        let linestring1 = line_string![
421            c(0.0, 0.0),
422            c(0.0, 20.0),
423            c(20.0, 20.0),
424            c(20.0, 0.0),
425            c(0.0, 0.0)
426        ];
427        let poly1 = Polygon::new(linestring1, Vec::new());
428        assert!(poly0.contains(&line));
429        assert!(!poly1.contains(&line));
430    }
431    #[test]
432    fn line_in_polygon_edgecases_test() {
433        // Some DE-9IM edge cases for checking line is
434        // inside polygon The end points of the line can be
435        // on the boundary of the polygon.
436        let c = |x, y| coord! { x: x, y: y };
437        // A non-convex polygon
438        let linestring0 = line_string![
439            c(0.0, 0.0),
440            c(1.0, 1.0),
441            c(1.0, -1.0),
442            c(-1.0, -1.0),
443            c(-1.0, 1.0)
444        ];
445        let poly = Polygon::new(linestring0, Vec::new());
446
447        assert!(poly.contains(&Line::new(c(0.0, 0.0), c(1.0, -1.0))));
448        assert!(poly.contains(&Line::new(c(-1.0, 1.0), c(1.0, -1.0))));
449        assert!(!poly.contains(&Line::new(c(-1.0, 1.0), c(1.0, 1.0))));
450    }
451    #[test]
452    fn line_in_linestring_edgecases() {
453        let c = |x, y| coord! { x: x, y: y };
454        use crate::line_string;
455        let mut ls = line_string![c(0, 0), c(1, 0), c(0, 1), c(-1, 0)];
456        assert!(!ls.contains(&Line::from([(0, 0), (0, 0)])));
457        ls.close();
458        assert!(ls.contains(&Line::from([(0, 0), (0, 0)])));
459        assert!(ls.contains(&Line::from([(-1, 0), (1, 0)])));
460    }
461    #[test]
462    fn line_in_linestring_test() {
463        let line0 = Line::from([(1., 1.), (2., 2.)]);
464        // line0 is completely contained in the second segment
465        let linestring0 = LineString::from(vec![(0., 0.5), (0.5, 0.5), (3., 3.)]);
466        // line0 is contained in the last three segments
467        let linestring1 = LineString::from(vec![
468            (0., 0.5),
469            (0.5, 0.5),
470            (1.2, 1.2),
471            (1.5, 1.5),
472            (3., 3.),
473        ]);
474        // line0 endpoints are contained in the linestring, but the fourth point is off the line
475        let linestring2 = LineString::from(vec![
476            (0., 0.5),
477            (0.5, 0.5),
478            (1.2, 1.2),
479            (1.5, 0.),
480            (2., 2.),
481            (3., 3.),
482        ]);
483        assert!(linestring0.contains(&line0));
484        assert!(linestring1.contains(&line0));
485        assert!(!linestring2.contains(&line0));
486    }
487
488    #[test]
489    fn integer_bounding_rects() {
490        let p: Point<i32> = Point::new(10, 20);
491        let bounding_rect: Rect<i32> = Rect::new(coord! { x: 0, y: 0 }, coord! { x: 100, y: 100 });
492        assert!(bounding_rect.contains(&p));
493        assert!(!bounding_rect.contains(&Point::new(-10, -10)));
494
495        let smaller_bounding_rect: Rect<i32> =
496            Rect::new(coord! { x: 10, y: 10 }, coord! { x: 20, y: 20 });
497        assert!(bounding_rect.contains(&smaller_bounding_rect));
498    }
499
500    #[test]
501    fn triangle_not_contains_point_on_edge() {
502        let t = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
503        let p = Point::new(1.0, 0.0);
504        assert!(!t.contains(&p));
505    }
506
507    #[test]
508    fn triangle_not_contains_point_on_vertex() {
509        let t = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
510        let p = Point::new(2.0, 0.0);
511        assert!(!t.contains(&p));
512    }
513
514    #[test]
515    fn triangle_contains_point_inside() {
516        let t = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
517        let p = Point::new(1.0, 0.5);
518        assert!(t.contains(&p));
519    }
520
521    #[test]
522    fn triangle_not_contains_point_above() {
523        let t = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
524        let p = Point::new(1.0, 1.5);
525        assert!(!t.contains(&p));
526    }
527
528    #[test]
529    fn triangle_not_contains_point_below() {
530        let t = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
531        let p = Point::new(-1.0, 0.5);
532        assert!(!t.contains(&p));
533    }
534
535    #[test]
536    fn triangle_contains_neg_point() {
537        let t = Triangle::from([(0.0, 0.0), (-2.0, 0.0), (-2.0, -2.0)]);
538        let p = Point::new(-1.0, -0.5);
539        assert!(t.contains(&p));
540    }
541
542    #[test]
543    // https://github.com/georust/geo/issues/473
544    fn triangle_contains_collinear_points() {
545        let origin: Coord = (0., 0.).into();
546        let tri = Triangle::new(origin, origin, origin);
547        let pt: Point = (0., 1.23456).into();
548        assert!(!tri.contains(&pt));
549        let pt: Point = (0., 0.).into();
550        assert!(!tri.contains(&pt));
551        let origin: Coord = (0., 0.).into();
552        let tri = Triangle::new((1., 1.).into(), origin, origin);
553        let pt: Point = (1., 1.).into();
554        assert!(!tri.contains(&pt));
555        let pt: Point = (0.5, 0.5).into();
556        assert!(!tri.contains(&pt));
557    }
558}
geo/algorithm/contains/mod.rs

geo/algorithm/contains/
mod.rs
