fj_core/algorithms/intersect/
line_segment.rs

1use fj_math::{Aabb, Line, Point, Scalar, Segment, Vector};
2
3/// An intersection between a [`Line`] and a [`Segment`]
4#[derive(Debug, Eq, PartialEq)]
5pub enum LineSegmentIntersection {
6    /// Line and segment intersect at a point
7    Point {
8        /// The intersection point, given as a coordinate on the line
9        point_on_line: Point<1>,
10    },
11
12    /// Line and segment are coincident
13    Coincident {
14        /// The end points of the segment, given as coordinates on the line
15        points_on_line: [Point<1>; 2],
16    },
17}
18
19impl LineSegmentIntersection {
20    /// Determine the intersection between a [`Line`] and a [`Segment`]
21    pub fn compute(line: &Line<2>, segment: &Segment<2>) -> Option<Self> {
22        // Algorithm adapted from Real-Time Collision Detection by Christer
23        // Ericson. See section 5.1.9.1, 2D Segment Intersection.
24
25        let [a, b] = segment.points();
26
27        // Find vector that is orthogonal to `segment`.
28        let n = {
29            let ab = b - a;
30            Vector::from([ab.v, ab.u])
31        };
32
33        let n_dot_origin = n.dot(&(b - line.origin()));
34        let n_dot_direction = n.dot(&line.direction());
35
36        if n_dot_direction == Scalar::ZERO {
37            // `line` and `segment` are parallel
38
39            if n_dot_origin == Scalar::ZERO {
40                // `line` and `segment` are not just parallel, but coincident!
41                return Some(Self::Coincident {
42                    points_on_line: segment
43                        .points()
44                        .map(|point| line.point_to_line_coords(point)),
45                });
46            }
47
48            return None;
49        }
50
51        // Now we ruled out the special cases. Compute where `line` hits the
52        // line defined by `segment`'s points.
53        let t = n_dot_origin / n_dot_direction;
54
55        let point_is_on_segment = Aabb::<2>::from_points(segment.points())
56            .contains(line.point_from_line_coords([t]));
57        if !point_is_on_segment {
58            return None;
59        }
60
61        Some(Self::Point {
62            point_on_line: Point::from([t]),
63        })
64    }
65}
66
67#[cfg(test)]
68mod tests {
69    use fj_math::{Line, Point, Scalar, Segment, Vector};
70
71    use super::LineSegmentIntersection;
72
73    #[test]
74    fn compute_one_hit() {
75        let line =
76            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());
77
78        assert_eq!(
79            LineSegmentIntersection::compute(
80                &line,
81                &Segment::from_points([[1., -1.], [1., 1.]]),
82            ),
83            Some(LineSegmentIntersection::Point {
84                point_on_line: Point::from([Scalar::ONE])
85            }),
86        );
87    }
88
89    #[test]
90    fn compute_coincident() {
91        let line =
92            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());
93
94        assert_eq!(
95            LineSegmentIntersection::compute(
96                &line,
97                &Segment::from_points([[1., 0.], [2., 0.]]),
98            ),
99            Some(LineSegmentIntersection::Coincident {
100                points_on_line: [Point::from([1.]), Point::from([2.])],
101            }),
102        );
103    }
104
105    #[test]
106    fn compute_no_hit_above() {
107        let line =
108            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());
109
110        assert_eq!(
111            LineSegmentIntersection::compute(
112                &line,
113                &Segment::from_points([[1., 1.], [1., 2.]]),
114            ),
115            None,
116        );
117    }
118
119    #[test]
120    fn compute_no_hit_below() {
121        let line =
122            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());
123
124        assert_eq!(
125            LineSegmentIntersection::compute(
126                &line,
127                &Segment::from_points([[1., -2.], [1., -1.]]),
128            ),
129            None,
130        );
131    }
132
133    #[test]
134    fn compute_no_hit_parallel() {
135        let line =
136            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());
137
138        assert_eq!(
139            LineSegmentIntersection::compute(
140                &line,
141                &Segment::from_points([[-1., 1.], [1., 1.]]),
142            ),
143            None,
144        );
145    }
146}
fj_core/algorithms/intersect/line_segment.rs

fj_core/algorithms/intersect/
line_segment.rs
