geo/algorithm/contains/
line_string.rs

1use super::{Contains, impl_contains_from_relate, impl_contains_geometry_for};
2use crate::algorithm::kernels::Kernel;
3use crate::dimensions::Dimensions;
4use crate::geometry::*;
5use crate::{CoordNum, GeoFloat, GeoNum, HasDimensions, Intersects, Orientation};
6
7// ┌────────────────────────────────┐
8// │ Implementations for LineString │
9// └────────────────────────────────┘
10
11impl<T> Contains<Coord<T>> for LineString<T>
12where
13    T: GeoNum,
14{
15    fn contains(&self, coord: &Coord<T>) -> bool {
16        if self.0.is_empty() {
17            return false;
18        }
19
20        if coord == &self.0[0] || coord == self.0.last().unwrap() {
21            return self.is_closed();
22        }
23
24        // since it is already known that coord != linestring start or end
25        // it is sufficient to check if the coord intersects any line,
26        self.lines().any(|ln| ln.intersects(coord))
27    }
28}
29
30impl<T> Contains<Point<T>> for LineString<T>
31where
32    T: GeoNum,
33{
34    fn contains(&self, p: &Point<T>) -> bool {
35        self.contains(&p.0)
36    }
37}
38
39impl<T> Contains<Line<T>> for LineString<T>
40where
41    T: GeoNum,
42{
43    fn contains(&self, line: &Line<T>) -> bool {
44        if line.start == line.end {
45            return self.contains(&line.start);
46        }
47
48        let is_vertical = line.start.x == line.end.x;
49
50        // pre-order the line so that we can use the faster overlap check
51        let line = if (is_vertical && line.start.y > line.end.y)
52            || (!is_vertical && line.start.x > line.end.x)
53        {
54            Line::new(line.end, line.start)
55        } else {
56            *line
57        };
58
59        let candidates: Vec<(T, T)> = if is_vertical {
60            self.lines()
61                .filter(|segment| overlap::y_overlap(&line, segment))
62                .filter(|segment| is_collinear(&line, segment))
63                .map(|segment| {
64                    if segment.start.y < segment.end.y {
65                        (segment.start.y, segment.end.y)
66                    } else {
67                        (segment.end.y, segment.start.y)
68                    }
69                })
70                .collect()
71        } else {
72            self.lines()
73                .filter(|segment| overlap::x_overlap(&line, segment))
74                .filter(|segment| is_collinear(&line, segment))
75                .map(|segment| {
76                    if segment.start.x < segment.end.x {
77                        (segment.start.x, segment.end.x)
78                    } else {
79                        (segment.end.x, segment.start.x)
80                    }
81                })
82                .collect()
83        };
84
85        let mut changed = true;
86
87        // use y value instead if x values are identical
88        let (mut line_start, mut line_end) = if is_vertical {
89            (line.start.y, line.end.y)
90        } else {
91            (line.start.x, line.end.x)
92        };
93
94        // interval-based overlap checks
95        while changed {
96            changed = false;
97            for (c_start, c_end) in candidates.iter() {
98                // if no overlap, skip
99                if *c_end <= line_start || line_end <= *c_start {
100                }
101                // if candidate covers line, return true
102                else if *c_start <= line_start && line_end <= *c_end {
103                    return true;
104                } else if *c_start <= line_start {
105                    // trim start
106                    changed = true;
107                    line_start = *c_end;
108                } else if line_end <= *c_end {
109                    // trim end
110                    changed = true;
111                    line_end = *c_start;
112                }
113            }
114        }
115
116        false
117    }
118}
119
120impl<T> Contains<LineString<T>> for LineString<T>
121where
122    T: GeoNum,
123{
124    fn contains(&self, rhs: &LineString<T>) -> bool {
125        if self.is_empty() || rhs.is_empty() {
126            return false;
127        }
128
129        // handle degenerate linestring case
130        if rhs.dimensions() == Dimensions::ZeroDimensional {
131            return self.contains(&rhs.0[0]);
132        }
133
134        // filter out zero-length segments
135        // it is known from != Dimensions::ZeroDimensional && !self.is_empty()
136        // that there must be at least one segment with non-zero length
137        rhs.lines()
138            .filter(|l| l.start != l.end)
139            .all(|l| self.contains(&l))
140    }
141}
142
143impl_contains_from_relate!(LineString<T>, [Polygon<T>, MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>, Rect<T>, Triangle<T>]);
144impl_contains_geometry_for!(LineString<T>);
145
146// ┌─────────────────────────────────────┐
147// │ Implementations for MultiLineString │
148// └─────────────────────────────────────┘
149
150impl_contains_from_relate!(MultiLineString<T>, [Line<T>, LineString<T>, Polygon<T>, MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>, Rect<T>, Triangle<T>]);
151impl_contains_geometry_for!(MultiLineString<T>);
152
153impl<T> Contains<Coord<T>> for MultiLineString<T>
154where
155    T: CoordNum,
156    LineString<T>: Contains<Coord<T>>,
157{
158    fn contains(&self, coord: &Coord<T>) -> bool {
159        self.iter().any(|ls| ls.contains(coord))
160    }
161}
162
163impl<T> Contains<Point<T>> for MultiLineString<T>
164where
165    T: CoordNum,
166    LineString<T>: Contains<Point<T>>,
167{
168    fn contains(&self, rhs: &Point<T>) -> bool {
169        self.iter().any(|ls| ls.contains(rhs))
170    }
171}
172
173#[inline]
174fn is_collinear<T>(l1: &Line<T>, l2: &Line<T>) -> bool
175where
176    T: GeoNum,
177{
178    T::Ker::orient2d(l1.start, l1.end, l2.start) == Orientation::Collinear
179        && T::Ker::orient2d(l1.start, l1.end, l2.end) == Orientation::Collinear
180}
181
182/// Suppose we have 2 pairs (p1,p2) and (q1,q2) where p1 < p2 and q1 < q2
183///
184/// It is sufficient to show that each lower bound is smaller than the others' upper bound for the ranges to overlap  
185mod overlap {
186    use super::*;
187
188    #[inline]
189    /// Since l1 is ordered, we can execute overlap check in 3 comparisons.  
190    /// We use exclusive bounds because we only want to keep segments which can trim the line
191    pub(super) fn x_overlap<T: GeoNum>(ordered_l1: &Line<T>, l2: &Line<T>) -> bool {
192        debug_assert!(ordered_l1.start.x <= ordered_l1.end.x);
193
194        let (p1, p2) = (ordered_l1.start.x, ordered_l1.end.x);
195        let (q1, q2) = if l2.start.x < l2.end.x {
196            (l2.start.x, l2.end.x)
197        } else {
198            (l2.end.x, l2.start.x)
199        };
200
201        p1 < q2 && q1 < p2
202    }
203
204    #[inline]
205    /// Since l1 is ordered, we can execute overlap check in 3 comparisons.  
206    /// We use exclusive bounds because we only want to keep segments which can trim the line
207    pub(super) fn y_overlap<T: GeoNum>(ordered_l1: &Line<T>, l2: &Line<T>) -> bool {
208        debug_assert!(ordered_l1.start.y <= ordered_l1.end.y);
209
210        let (p1, p2) = (ordered_l1.start.y, ordered_l1.end.y);
211        let (q1, q2) = if l2.start.y < l2.end.y {
212            (l2.start.y, l2.end.y)
213        } else {
214            (l2.end.y, l2.start.y)
215        };
216
217        p1 < q2 && q1 < p2
218    }
219}
220
221#[cfg(test)]
222mod test {
223    use crate::{Contains, Relate};
224    use crate::{Convert, wkt};
225    use crate::{Line, LineString, Validation};
226
227    #[test]
228    fn linestring_component_with_zero_length() {
229        let ls: LineString<f64> = wkt! {LINESTRING(0 0, 2 2)}.convert();
230
231        // these are valid geometries
232        let ls_start: LineString<f64> = wkt! {LINESTRING(0 0, 0 0,0 0, 1 1)}.convert();
233        let ls_end: LineString<f64> = wkt! {LINESTRING(0 0, 1 1,1 1,1 1)}.convert();
234        assert!(ls_start.is_valid());
235        assert!(ls_end.is_valid());
236
237        // these are invalid geometries but we handle degenerate geometries as points
238        let degen_start: LineString<f64> = wkt! {LINESTRING(0 0, 0 0)}.convert();
239        let degen_end: LineString<f64> = wkt! {LINESTRING(2 2, 2 2)}.convert();
240        assert!(!degen_start.is_valid());
241        assert!(!degen_end.is_valid());
242
243        assert!(ls.relate(&ls_start).is_contains());
244        assert!(ls.contains(&ls_start));
245        assert!(ls.relate(&ls_end).is_contains());
246        assert!(ls.contains(&ls_end));
247
248        assert!(!ls.contains(&degen_start));
249        assert!(!ls.relate(&degen_start).is_contains());
250        assert!(!ls.contains(&degen_end));
251        assert!(!ls.relate(&degen_end).is_contains());
252    }
253
254    #[test]
255    fn triangles() {
256        let ln: Line<f64> = wkt! {LINE(0 0, 10 0)}.convert();
257        let ls: LineString<f64> = wkt! {LINESTRING(0 0, 1 1, 2 0, 4 0, 5 1, 6 0, 8 0, 9 1,10 0, 8 0, 7 -1, 6 0, 4 0, 3 -1, 2 0 , 0 0 )}.convert();
258
259        // ln and ls are valid
260        assert!(ln.is_valid());
261        assert!(ls.is_valid());
262
263        assert_eq!(
264            ls.relate(&ln).is_contains(), // true
265            ls.contains(&ln)              // true
266        );
267    }
268
269    #[test]
270    fn test_start_end() {
271        let ls: LineString<f64> = wkt! {LINESTRING(0 0,0 1, 1 1)}.convert();
272        let ln_start: Line<f64> = wkt! {LINE(0 0, 0 0)}.convert();
273        let ln_end: Line<f64> = wkt! {LINE(1 1, 1 1)}.convert();
274
275        assert!(!ls.contains(&ln_start));
276        assert!(!ls.contains(&ln_end));
277    }
278
279    #[test]
280    fn test_vertical() {
281        let ls1: LineString<f64> = wkt! {LINESTRING(0 0,0 5,0 10)}.convert();
282        let ls2: LineString<f64> = wkt! {LINESTRING(0 10,0 5, 0 0)}.convert();
283
284        let ln: Line<f64> = wkt! {LINE(0 0, 0 9)}.convert();
285
286        assert!(ls1.contains(&ln));
287        assert!(ls2.contains(&ln));
288    }
289}
geo/algorithm/contains/line_string.rs

geo/algorithm/contains/
line_string.rs
