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>]);
149
150impl<T> Contains<Coord<T>> for MultiPoint<T>
151where
152    T: CoordNum,
153{
154    fn contains(&self, coord: &Coord<T>) -> bool {
155        self.iter().any(|c| &c.0 == coord)
156    }
157}
158
159impl<T> Contains<Point<T>> for MultiPoint<T>
160where
161    T: CoordNum,
162{
163    fn contains(&self, point: &Point<T>) -> bool {
164        self.iter().any(|c| c == point)
165    }
166}
167
168impl<T> Contains<MultiPoint<T>> for MultiPoint<T>
169where
170    T: CoordNum,
171{
172    fn contains(&self, multi_point: &MultiPoint<T>) -> bool {
173        // sort both collections by x then y
174        // then double pointer our way up the sorted arrays
175
176        if self.0.is_empty() {
177            return false;
178        }
179        if multi_point.0.is_empty() {
180            return false;
181        }
182
183        let mut self_order = self.0.clone();
184        self_order.sort_by(cmp_pts);
185
186        let mut other_order = multi_point.0.clone();
187        other_order.sort_by(cmp_pts);
188
189        let mut self_iter = self_order.iter().peekable();
190        let mut other_iter = other_order.iter().peekable();
191
192        loop {
193            // other has been exhausted
194            if other_iter.peek().is_none() {
195                return true;
196            }
197            // self has been exhausted but other has not been exhausted
198            if self_iter.peek().is_none() {
199                return false;
200            }
201
202            match cmp_pts(self_iter.peek().unwrap(), other_iter.peek().unwrap()) {
203                std::cmp::Ordering::Equal => {
204                    // other only ensures that we don't step past duplicate other points
205                    other_iter.next();
206                }
207                std::cmp::Ordering::Less => {
208                    self_iter.next();
209                }
210                std::cmp::Ordering::Greater => {
211                    return false;
212                }
213            }
214        }
215    }
216}
217
218// used for sorting points in multipoint
219fn cmp_pts<T: CoordNum>(a: &Point<T>, b: &Point<T>) -> std::cmp::Ordering {
220    let x_order = a.x().partial_cmp(&b.x());
221    match x_order {
222        Some(std::cmp::Ordering::Equal) => {
223            let y_order = a.y().partial_cmp(&b.y());
224            match y_order {
225                Some(std::cmp::Ordering::Equal) => std::cmp::Ordering::Equal,
226                Some(std::cmp::Ordering::Less) => std::cmp::Ordering::Less,
227                Some(std::cmp::Ordering::Greater) => std::cmp::Ordering::Greater,
228                None => std::cmp::Ordering::Equal,
229            }
230        }
231        Some(std::cmp::Ordering::Less) => std::cmp::Ordering::Less,
232        Some(std::cmp::Ordering::Greater) => std::cmp::Ordering::Greater,
233        None => std::cmp::Ordering::Equal,
234    }
235}
236
237#[cfg(test)]
238mod test {
239    use super::*;
240    use crate::{MultiPoint, Relate, coord, point};
241
242    #[test]
243    /**
244     * tests for empty multipoint
245     * behaviour follows `Relate` Trait
246     */
247    fn test_empty_multipoint_contains_multipoint() {
248        let empty: MultiPoint<f64> = MultiPoint::new(Vec::new());
249        let non_empty: MultiPoint<f64> = MultiPoint::new(vec![point! {x: 0.0, y: 0.0}]);
250
251        // empty multipoint does not contains non-empty multipoint
252        assert!(!empty.contains(&non_empty));
253        assert!(!empty.relate(&non_empty).is_contains());
254
255        // non-empty multipoint does not contain empty multipoint
256        assert!(!non_empty.contains(&empty));
257        assert!(!non_empty.relate(&empty).is_contains());
258
259        // empty multipoint does not contain empty multipoint
260        assert!(!empty.contains(&empty));
261        assert!(!empty.relate(&empty).is_contains());
262    }
263
264    #[test]
265    fn test_multipoint_contains_multipoint() {
266        let pt_a = coord! {x: 0., y: 0.};
267        let pt_b = coord! {x: 10., y: 10.};
268        let pt_c = coord! {x: 20., y: 20.};
269        let pt_d = coord! {x: 30., y: 30.};
270
271        let mp_a = MultiPoint::from(vec![pt_a]);
272        let mp_bc = MultiPoint::from(vec![pt_a, pt_b]);
273        let mp_abc = MultiPoint::from(vec![pt_a, pt_b, pt_c]);
274        let mp_bcd = MultiPoint::from(vec![pt_b, pt_c, pt_d]);
275
276        // multipoint contains itself
277        assert!(mp_a.contains(&mp_a));
278        assert!(mp_bc.contains(&mp_bc));
279        assert!(mp_abc.contains(&mp_abc));
280        assert!(mp_bcd.contains(&mp_bcd));
281
282        // multipoint contains subsets
283        assert!(mp_abc.contains(&mp_a));
284        assert!(mp_abc.contains(&mp_bc));
285
286        // partially overlapping multipoints do not contain each other
287        assert!(!mp_abc.contains(&mp_bcd));
288    }
289}
geo/algorithm/contains/point.rs

geo/algorithm/contains/
point.rs
