geo/algorithm/contains/
point.rs

1use super::{Contains, impl_contains_from_relate, impl_contains_geometry_for};
2use crate::algorithm::{CoordsIter, HasDimensions};
3use crate::geometry::*;
4use crate::{CoordNum, GeoFloat};
5
6// ┌────────────────────────────────┐
7// │ Implementations for Point      │
8// └────────────────────────────────┘
9
10impl<T> Contains<Coord<T>> for Point<T>
11where
12    T: CoordNum,
13{
14    fn contains(&self, coord: &Coord<T>) -> bool {
15        &self.0 == coord
16    }
17}
18
19impl<T> Contains<Point<T>> for Point<T>
20where
21    T: CoordNum,
22{
23    fn contains(&self, p: &Point<T>) -> bool {
24        self.contains(&p.0)
25    }
26}
27
28impl<T> Contains<Line<T>> for Point<T>
29where
30    T: CoordNum,
31{
32    fn contains(&self, line: &Line<T>) -> bool {
33        if line.start == line.end {
34            // degenerate line is a point
35            line.start == self.0
36        } else {
37            false
38        }
39    }
40}
41
42impl<T> Contains<LineString<T>> for Point<T>
43where
44    T: CoordNum,
45{
46    fn contains(&self, line_string: &LineString<T>) -> bool {
47        if line_string.is_empty() {
48            return false;
49        }
50        // only a degenerate LineString could be within a point
51        line_string.coords().all(|c| c == &self.0)
52    }
53}
54
55impl<T> Contains<Polygon<T>> for Point<T>
56where
57    T: CoordNum,
58{
59    fn contains(&self, polygon: &Polygon<T>) -> bool {
60        if polygon.is_empty() {
61            return false;
62        }
63        // only a degenerate Polygon could be within a point
64        polygon.coords_iter().all(|coord| coord == self.0)
65    }
66}
67
68impl<T> Contains<MultiPoint<T>> for Point<T>
69where
70    T: CoordNum,
71{
72    fn contains(&self, multi_point: &MultiPoint<T>) -> bool {
73        if multi_point.is_empty() {
74            return false;
75        }
76        multi_point.iter().all(|point| self.contains(point))
77    }
78}
79
80impl<T> Contains<MultiLineString<T>> for Point<T>
81where
82    T: CoordNum,
83{
84    fn contains(&self, multi_line_string: &MultiLineString<T>) -> bool {
85        if multi_line_string.is_empty() {
86            return false;
87        }
88        // only a degenerate MultiLineString could be within a point
89        multi_line_string
90            .iter()
91            .all(|line_string| self.contains(line_string))
92    }
93}
94
95impl<T> Contains<MultiPolygon<T>> for Point<T>
96where
97    T: CoordNum,
98{
99    fn contains(&self, multi_polygon: &MultiPolygon<T>) -> bool {
100        if multi_polygon.is_empty() {
101            return false;
102        }
103        // only a degenerate MultiPolygon could be within a point
104        multi_polygon.iter().all(|polygon| self.contains(polygon))
105    }
106}
107
108impl<T> Contains<GeometryCollection<T>> for Point<T>
109where
110    T: GeoFloat,
111{
112    fn contains(&self, geometry_collection: &GeometryCollection<T>) -> bool {
113        if geometry_collection.is_empty() {
114            return false;
115        }
116        geometry_collection
117            .iter()
118            .all(|geometry| self.contains(geometry))
119    }
120}
121
122impl<T> Contains<Rect<T>> for Point<T>
123where
124    T: CoordNum,
125{
126    fn contains(&self, rect: &Rect<T>) -> bool {
127        // only a degenerate Rect could be within a point
128        rect.min() == rect.max() && rect.min() == self.0
129    }
130}
131
132impl<T> Contains<Triangle<T>> for Point<T>
133where
134    T: CoordNum,
135{
136    fn contains(&self, triangle: &Triangle<T>) -> bool {
137        // only a degenerate Triangle could be within a point
138        triangle.0 == triangle.1 && triangle.0 == triangle.2 && triangle.0 == self.0
139    }
140}
141
142impl_contains_geometry_for!(Point<T>);
143
144// ┌────────────────────────────────┐
145// │ Implementations for MultiPoint │
146// └────────────────────────────────┘
147
148impl_contains_from_relate!(MultiPoint<T>, [Line<T>, LineString<T>, Polygon<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>, Rect<T>, Triangle<T>]);
149impl_contains_geometry_for!(MultiPoint<T>);
150
151impl<T> Contains<Coord<T>> for MultiPoint<T>
152where
153    T: CoordNum,
154{
155    fn contains(&self, coord: &Coord<T>) -> bool {
156        self.iter().any(|c| &c.0 == coord)
157    }
158}
159
160impl<T> Contains<Point<T>> for MultiPoint<T>
161where
162    T: CoordNum,
163{
164    fn contains(&self, point: &Point<T>) -> bool {
165        self.iter().any(|c| c == point)
166    }
167}
168
169impl<T> Contains<MultiPoint<T>> for MultiPoint<T>
170where
171    T: CoordNum,
172{
173    fn contains(&self, multi_point: &MultiPoint<T>) -> bool {
174        // sort both collections by x then y
175        // then double pointer our way up the sorted arrays
176
177        if self.0.is_empty() {
178            return false;
179        }
180        if multi_point.0.is_empty() {
181            return false;
182        }
183
184        let mut self_order = self.0.clone();
185        self_order.sort_by(cmp_pts);
186
187        let mut other_order = multi_point.0.clone();
188        other_order.sort_by(cmp_pts);
189
190        let mut self_iter = self_order.iter().peekable();
191        let mut other_iter = other_order.iter().peekable();
192
193        loop {
194            // other has been exhausted
195            if other_iter.peek().is_none() {
196                return true;
197            }
198            // self has been exhausted but other has not been exhausted
199            if self_iter.peek().is_none() {
200                return false;
201            }
202
203            match cmp_pts(self_iter.peek().unwrap(), other_iter.peek().unwrap()) {
204                std::cmp::Ordering::Equal => {
205                    // other only ensures that we don't step past duplicate other points
206                    other_iter.next();
207                }
208                std::cmp::Ordering::Less => {
209                    self_iter.next();
210                }
211                std::cmp::Ordering::Greater => {
212                    return false;
213                }
214            }
215        }
216    }
217}
218
219// used for sorting points in multipoint
220fn cmp_pts<T: CoordNum>(a: &Point<T>, b: &Point<T>) -> std::cmp::Ordering {
221    let x_order = a.x().partial_cmp(&b.x());
222    match x_order {
223        Some(std::cmp::Ordering::Equal) => {
224            let y_order = a.y().partial_cmp(&b.y());
225            match y_order {
226                Some(std::cmp::Ordering::Equal) => std::cmp::Ordering::Equal,
227                Some(std::cmp::Ordering::Less) => std::cmp::Ordering::Less,
228                Some(std::cmp::Ordering::Greater) => std::cmp::Ordering::Greater,
229                None => std::cmp::Ordering::Equal,
230            }
231        }
232        Some(std::cmp::Ordering::Less) => std::cmp::Ordering::Less,
233        Some(std::cmp::Ordering::Greater) => std::cmp::Ordering::Greater,
234        None => std::cmp::Ordering::Equal,
235    }
236}
237
238#[cfg(test)]
239mod test {
240    use super::*;
241    use crate::{MultiPoint, Relate, coord, point};
242
243    #[test]
244    /**
245     * tests for empty multipoint
246     * behaviour follows `Relate` Trait
247     */
248    fn test_empty_multipoint_contains_multipoint() {
249        let empty: MultiPoint<f64> = MultiPoint::empty();
250        let non_empty: MultiPoint<f64> = MultiPoint::new(vec![point! {x: 0.0, y: 0.0}]);
251
252        // empty multipoint does not contains non-empty multipoint
253        assert!(!empty.contains(&non_empty));
254        assert!(!empty.relate(&non_empty).is_contains());
255
256        // non-empty multipoint does not contain empty multipoint
257        assert!(!non_empty.contains(&empty));
258        assert!(!non_empty.relate(&empty).is_contains());
259
260        // empty multipoint does not contain empty multipoint
261        assert!(!empty.contains(&empty));
262        assert!(!empty.relate(&empty).is_contains());
263    }
264
265    #[test]
266    fn test_multipoint_contains_multipoint() {
267        let pt_a = coord! {x: 0., y: 0.};
268        let pt_b = coord! {x: 10., y: 10.};
269        let pt_c = coord! {x: 20., y: 20.};
270        let pt_d = coord! {x: 30., y: 30.};
271
272        let mp_a = MultiPoint::from(vec![pt_a]);
273        let mp_bc = MultiPoint::from(vec![pt_a, pt_b]);
274        let mp_abc = MultiPoint::from(vec![pt_a, pt_b, pt_c]);
275        let mp_bcd = MultiPoint::from(vec![pt_b, pt_c, pt_d]);
276
277        // multipoint contains itself
278        assert!(mp_a.contains(&mp_a));
279        assert!(mp_bc.contains(&mp_bc));
280        assert!(mp_abc.contains(&mp_abc));
281        assert!(mp_bcd.contains(&mp_bcd));
282
283        // multipoint contains subsets
284        assert!(mp_abc.contains(&mp_a));
285        assert!(mp_abc.contains(&mp_bc));
286
287        // partially overlapping multipoints do not contain each other
288        assert!(!mp_abc.contains(&mp_bcd));
289    }
290}
geo/algorithm/contains/point.rs

geo/algorithm/contains/
point.rs
