1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

use fj_math::{Aabb, Line, Point, Scalar, Segment, Vector};

/// An intersection between a [`Line`] and a [`Segment`]
#[derive(Debug, Eq, PartialEq)]
pub enum LineSegmentIntersection {
    /// Line and segment intersect at a point
    Point {
        /// The intersection point, given as a coordinate on the line
        point_on_line: Point<1>,
    },

    /// Line and segment are coincident
    Coincident {
        /// The end points of the segment, given as coordinates on the line
        points_on_line: [Point<1>; 2],
    },
}

impl LineSegmentIntersection {
    /// Determine the intersection between a [`Line`] and a [`Segment`]
    pub fn compute(line: &Line<2>, segment: &Segment<2>) -> Option<Self> {
        // Algorithm adapted from Real-Time Collision Detection by Christer
        // Ericson. See section 5.1.9.1, 2D Segment Intersection.

        let [a, b] = segment.points();

        // Find vector that is orthogonal to `segment`.
        let n = {
            let ab = b - a;
            Vector::from([ab.v, ab.u])
        };

        let n_dot_origin = n.dot(&(b - line.origin()));
        let n_dot_direction = n.dot(&line.direction());

        if n_dot_direction == Scalar::ZERO {
            // `line` and `segment` are parallel

            if n_dot_origin == Scalar::ZERO {
                // `line` and `segment` are not just parallel, but coincident!
                return Some(Self::Coincident {
                    points_on_line: segment
                        .points()
                        .map(|point| line.point_to_line_coords(point)),
                });
            }

            return None;
        }

        // Now we ruled out the special cases. Compute where `line` hits the
        // line defined by `segment`'s points.
        let t = n_dot_origin / n_dot_direction;

        let point_is_on_segment = Aabb::<2>::from_points(segment.points())
            .contains(line.point_from_line_coords([t]));
        if !point_is_on_segment {
            return None;
        }

        Some(Self::Point {
            point_on_line: Point::from([t]),
        })
    }
}

#[cfg(test)]
mod tests {
    use fj_math::{Line, Point, Scalar, Segment, Vector};

    use super::LineSegmentIntersection;

    #[test]
    fn compute_one_hit() {
        let line =
            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());

        assert_eq!(
            LineSegmentIntersection::compute(
                &line,
                &Segment::from_points([[1., -1.], [1., 1.]]),
            ),
            Some(LineSegmentIntersection::Point {
                point_on_line: Point::from([Scalar::ONE])
            }),
        );
    }

    #[test]
    fn compute_coincident() {
        let line =
            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());

        assert_eq!(
            LineSegmentIntersection::compute(
                &line,
                &Segment::from_points([[1., 0.], [2., 0.]]),
            ),
            Some(LineSegmentIntersection::Coincident {
                points_on_line: [Point::from([1.]), Point::from([2.])],
            }),
        );
    }

    #[test]
    fn compute_no_hit_above() {
        let line =
            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());

        assert_eq!(
            LineSegmentIntersection::compute(
                &line,
                &Segment::from_points([[1., 1.], [1., 2.]]),
            ),
            None,
        );
    }

    #[test]
    fn compute_no_hit_below() {
        let line =
            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());

        assert_eq!(
            LineSegmentIntersection::compute(
                &line,
                &Segment::from_points([[1., -2.], [1., -1.]]),
            ),
            None,
        );
    }

    #[test]
    fn compute_no_hit_parallel() {
        let line =
            Line::from_origin_and_direction(Point::origin(), Vector::unit_u());

        assert_eq!(
            LineSegmentIntersection::compute(
                &line,
                &Segment::from_points([[-1., 1.], [1., 1.]]),
            ),
            None,
        );
    }
}