fj_core/algorithms/intersect/
ray_segment.rs

1//! Intersection between a ray and a line segment in 2D
2
3use fj_math::Segment;
4
5use super::{HorizontalRayToTheRight, Intersect};
6
7impl Intersect for (&HorizontalRayToTheRight<2>, &Segment<2>) {
8    type Intersection = RaySegmentIntersection;
9
10    fn intersect(self) -> Option<Self::Intersection> {
11        let (ray, segment) = self;
12
13        let [a, b] = segment.points();
14        let [lower, upper] = if a.v <= b.v { [a, b] } else { [b, a] };
15        let [left, right] = if a.u <= b.u { [a, b] } else { [b, a] };
16
17        if ray.origin.v > upper.v {
18            // ray is above segment
19            return None;
20        }
21        if ray.origin.v < lower.v {
22            // ray is below segment
23            return None;
24        }
25
26        if ray.origin.v == lower.v && lower.v == upper.v {
27            // ray and segment are parallel and at same height
28
29            if ray.origin.u > right.u {
30                return None;
31            }
32
33            if ray.origin.u == a.u {
34                return Some(RaySegmentIntersection::RayStartsOnOnFirstVertex);
35            }
36            if ray.origin.u == b.u {
37                return Some(RaySegmentIntersection::RayStartsOnSecondVertex);
38            }
39            if ray.origin.u > left.u && ray.origin.u < right.u {
40                return Some(RaySegmentIntersection::RayStartsOnSegment);
41            }
42
43            return Some(RaySegmentIntersection::RayHitsSegmentAndAreParallel);
44        }
45
46        let pa = robust::Coord {
47            x: lower.u,
48            y: lower.v,
49        };
50        let pb = robust::Coord {
51            x: upper.u,
52            y: upper.v,
53        };
54        let pc = robust::Coord {
55            x: ray.origin.u,
56            y: ray.origin.v,
57        };
58
59        let orient2d = robust::orient2d(pa, pb, pc);
60
61        if orient2d == 0. {
62            // ray starts on the line
63
64            if ray.origin.v == a.v {
65                return Some(RaySegmentIntersection::RayStartsOnOnFirstVertex);
66            }
67            if ray.origin.v == b.v {
68                return Some(RaySegmentIntersection::RayStartsOnSecondVertex);
69            }
70
71            return Some(RaySegmentIntersection::RayStartsOnSegment);
72        }
73
74        if orient2d > 0. {
75            // ray starts left of the line
76
77            if ray.origin.v == upper.v {
78                return Some(RaySegmentIntersection::RayHitsUpperVertex);
79            }
80            if ray.origin.v == lower.v {
81                return Some(RaySegmentIntersection::RayHitsLowerVertex);
82            }
83
84            return Some(RaySegmentIntersection::RayHitsSegment);
85        }
86
87        None
88    }
89}
90
91/// An intersection between a ray and a line segment
92#[derive(Clone, Copy, Debug, Eq, PartialEq)]
93pub enum RaySegmentIntersection {
94    /// The ray hit the segment itself
95    RayHitsSegment,
96
97    /// The ray hit the lower vertex of the segment
98    RayHitsLowerVertex,
99
100    /// The ray hit the upper vertex of the segment
101    RayHitsUpperVertex,
102
103    /// The ray hit the whole segment, as it is parallel to the ray
104    RayHitsSegmentAndAreParallel,
105
106    /// The ray starts on the segment
107    RayStartsOnSegment,
108
109    /// The ray starts on the first vertex of the segment
110    RayStartsOnOnFirstVertex,
111
112    /// The ray starts on the second vertex of the segment
113    RayStartsOnSecondVertex,
114}
115
116#[cfg(test)]
117mod tests {
118    use fj_math::Segment;
119
120    use crate::algorithms::intersect::Intersect;
121
122    use super::{HorizontalRayToTheRight, RaySegmentIntersection};
123
124    #[test]
125    fn ray_is_left_of_segment() {
126        let ray = HorizontalRayToTheRight::from([0., 2.]);
127
128        let below = Segment::from([[1., 0.], [1., 1.]]);
129        let above = Segment::from([[1., 3.], [1., 4.]]);
130        let same_level = Segment::from([[1., 1.], [1., 3.]]);
131
132        assert!((&ray, &below).intersect().is_none());
133        assert!((&ray, &above).intersect().is_none());
134        assert!(matches!(
135            (&ray, &same_level).intersect(),
136            Some(RaySegmentIntersection::RayHitsSegment)
137        ));
138    }
139
140    #[test]
141    fn ray_is_right_of_segment() {
142        let ray = HorizontalRayToTheRight::from([1., 2.]);
143
144        let same_level = Segment::from([[0., 1.], [0., 3.]]);
145        assert!((&ray, &same_level).intersect().is_none());
146    }
147
148    #[test]
149    fn ray_overlaps_with_segment_along_x_axis() {
150        let ray = HorizontalRayToTheRight::from([1., 1.]);
151
152        let no_hit = Segment::from([[0., 0.], [2., 3.]]);
153
154        let hit_segment = Segment::from([[0., 0.], [3., 2.]]);
155        let hit_upper = Segment::from([[0., 0.], [2., 1.]]);
156        let hit_lower = Segment::from([[0., 2.], [2., 1.]]);
157
158        assert!((&ray, &no_hit).intersect().is_none());
159        assert!(matches!(
160            (&ray, &hit_segment).intersect(),
161            Some(RaySegmentIntersection::RayHitsSegment)
162        ));
163        assert!(matches!(
164            (&ray, &hit_upper).intersect(),
165            Some(RaySegmentIntersection::RayHitsUpperVertex),
166        ));
167        assert!(matches!(
168            (&ray, &hit_lower).intersect(),
169            Some(RaySegmentIntersection::RayHitsLowerVertex),
170        ));
171    }
172
173    #[test]
174    fn ray_starts_on_segment() {
175        let ray = HorizontalRayToTheRight::from([1., 1.]);
176
177        let hit_segment = Segment::from([[0., 0.], [2., 2.]]);
178        let hit_upper = Segment::from([[0., 0.], [1., 1.]]);
179        let hit_lower = Segment::from([[1., 1.], [2., 2.]]);
180
181        assert!(matches!(
182            (&ray, &hit_segment).intersect(),
183            Some(RaySegmentIntersection::RayStartsOnSegment)
184        ));
185        assert!(matches!(
186            (&ray, &hit_upper).intersect(),
187            Some(RaySegmentIntersection::RayStartsOnSecondVertex),
188        ));
189        assert!(matches!(
190            (&ray, &hit_lower).intersect(),
191            Some(RaySegmentIntersection::RayStartsOnOnFirstVertex),
192        ));
193    }
194
195    #[test]
196    fn ray_and_segment_are_parallel_and_on_same_level() {
197        let ray = HorizontalRayToTheRight::from([2., 0.]);
198
199        let left = Segment::from([[0., 0.], [1., 0.]]);
200        let right = Segment::from([[3., 0.], [4., 0.]]);
201
202        assert!((&ray, &left).intersect().is_none());
203        assert!(matches!(
204            (&ray, &right).intersect(),
205            Some(RaySegmentIntersection::RayHitsSegmentAndAreParallel)
206        ));
207    }
208
209    #[test]
210    fn ray_starts_on_parallel_segment() {
211        let ray = HorizontalRayToTheRight::from([2., 0.]);
212
213        let left = Segment::from([[0., 0.], [2., 0.]]);
214        let overlapping = Segment::from([[1., 0.], [3., 0.]]);
215        let right = Segment::from([[2., 0.], [4., 0.]]);
216
217        assert!(matches!(
218            (&ray, &left).intersect(),
219            Some(RaySegmentIntersection::RayStartsOnSecondVertex)
220        ));
221        assert!(matches!(
222            (&ray, &overlapping).intersect(),
223            Some(RaySegmentIntersection::RayStartsOnSegment),
224        ));
225        assert!(matches!(
226            (&ray, &right).intersect(),
227            Some(RaySegmentIntersection::RayStartsOnOnFirstVertex),
228        ));
229    }
230}
fj_core/algorithms/intersect/ray_segment.rs

fj_core/algorithms/intersect/
ray_segment.rs
