geo/algorithm/intersects/
line.rs

1use super::{point_in_rect, Intersects};
2use crate::kernels::*;
3use crate::*;
4
5impl<T> Intersects<Coord<T>> for Line<T>
6where
7    T: GeoNum,
8{
9    fn intersects(&self, rhs: &Coord<T>) -> bool {
10        // First we check if the point is collinear with the line.
11        T::Ker::orient2d(self.start, self.end, *rhs) == Orientation::Collinear
12        // In addition, the point must have _both_ coordinates
13        // within the start and end bounds.
14            && point_in_rect(*rhs, self.start, self.end)
15    }
16}
17symmetric_intersects_impl!(Coord<T>, Line<T>);
18symmetric_intersects_impl!(Line<T>, Point<T>);
19
20impl<T> Intersects<Line<T>> for Line<T>
21where
22    T: GeoNum,
23{
24    fn intersects(&self, line: &Line<T>) -> bool {
25        // Special case: self is equiv. to a point.
26        if self.start == self.end {
27            return line.intersects(&self.start);
28        }
29
30        // Precondition: start and end are distinct.
31
32        // Check if orientation of rhs.{start,end} are different
33        // with respect to self.{start,end}.
34        let check_1_1 = T::Ker::orient2d(self.start, self.end, line.start);
35        let check_1_2 = T::Ker::orient2d(self.start, self.end, line.end);
36
37        if check_1_1 != check_1_2 {
38            // Since the checks are different,
39            // rhs.{start,end} are distinct, and rhs is not
40            // collinear with self. Thus, there is exactly
41            // one point on the infinite extensions of rhs,
42            // that is collinear with self.
43
44            // By continuity, this point is not on the
45            // exterior of rhs. Now, check the same with
46            // self, rhs swapped.
47
48            let check_2_1 = T::Ker::orient2d(line.start, line.end, self.start);
49            let check_2_2 = T::Ker::orient2d(line.start, line.end, self.end);
50
51            // By similar argument, there is (exactly) one
52            // point on self, collinear with rhs. Thus,
53            // those two have to be same, and lies (interior
54            // or boundary, but not exterior) on both lines.
55            check_2_1 != check_2_2
56        } else if check_1_1 == Orientation::Collinear {
57            // Special case: collinear line segments.
58
59            // Equivalent to 4 point-line intersection
60            // checks, but removes the calls to the kernel
61            // predicates.
62            point_in_rect(line.start, self.start, self.end)
63                || point_in_rect(line.end, self.start, self.end)
64                || point_in_rect(self.end, line.start, line.end)
65                || point_in_rect(self.end, line.start, line.end)
66        } else {
67            false
68        }
69    }
70}
geo/algorithm/intersects/line.rs

geo/algorithm/intersects/
line.rs
