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

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

/// Determine the intersection between a [`Line`] and a [`Segment`]
pub fn line_segment(
    line: &Line<2>,
    segment: &Segment<2>,
) -> Option<LineSegmentIntersection> {
    // 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_origin == Scalar::ZERO && n_dot_direction == Scalar::ZERO {
        // `line` and `segment` are not just parallel, but coincident!
        return Some(LineSegmentIntersection::Coincident);
    }

    if n_dot_direction == Scalar::ZERO {
        // `line` and `segment` are parallel, but not coincident
        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(LineSegmentIntersection::PointOnLine(t))
}

/// An intersection between a [`Line`] and a [`Segment`]
#[derive(Debug, Eq, PartialEq)]
pub enum LineSegmentIntersection {
    /// Line and segment intersect on a point
    ///
    /// Point is given as a coordinate on the line.
    PointOnLine(Scalar),

    /// Line and segment are coincident
    Coincident,
}

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

    use crate::algorithms::intersection::LineSegmentIntersection;

    #[test]
    fn line_segment() {
        let line = Line {
            origin: Point::origin(),
            direction: Vector::unit_u(),
        };

        // regular hit
        assert_eq!(
            super::line_segment(
                &line,
                &Segment::from_points([[1., -1.], [1., 1.]]),
            ),
            Some(LineSegmentIntersection::PointOnLine(Scalar::ONE)),
        );

        // hit, where line and segment are parallel
        assert_eq!(
            super::line_segment(
                &line,
                &Segment::from_points([[1., 0.], [2., 0.]]),
            ),
            Some(LineSegmentIntersection::Coincident),
        );

        // segment above line
        assert_eq!(
            super::line_segment(
                &line,
                &Segment::from_points([[1., 1.], [1., 2.]]),
            ),
            None,
        );

        // segment below line
        assert_eq!(
            super::line_segment(
                &line,
                &Segment::from_points([[1., -2.], [1., -1.]]),
            ),
            None,
        );

        // segment parallel to line
        assert_eq!(
            super::line_segment(
                &line,
                &Segment::from_points([[-1., 1.], [1., 1.]]),
            ),
            None,
        );
    }
}