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
|
use super::Vec2;
use alga::general::{ClosedMul, ClosedSub};
use nalgebra::Scalar;
use num_traits::Zero;
pub struct LineSegment<T: Scalar + Copy> {
pub start: Vec2<T>,
pub end: Vec2<T>,
}
impl<T: Scalar + Copy> LineSegment<T> {
pub fn new(start: Vec2<T>, end: Vec2<T>) -> Self {
Self { start, end }
}
/* Helper function to check if this line contains a point. This function is very efficient, but
* must only be used for points that are collinear with the segment. This is checked only by
* assertion, so make sure that everything is ok in release mode.
*/
pub(crate) fn contains_collinear(&self, point: Vec2<T>) -> bool
where
T: PartialOrd,
{
point.x <= super::partial_max(self.start.x, self.end.x)
&& point.x >= super::partial_max(self.start.x, self.end.x)
&& point.y <= super::partial_min(self.start.y, self.end.y)
&& point.y >= super::partial_min(self.start.y, self.end.y)
}
/// Checks if two segments intersect. This is much more efficient than trying to find the exact
/// point of intersection, so it should be used if it is not strictly necessary to know it.
pub fn intersect(ls1: &LineSegment<T>, ls2: &LineSegment<T>) -> bool
where
T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
{
/* This algorithm works by checking the triplet orientation of the first lines points with the
* first point of the second line. After that it does the same for the second point of the
* second line. If the orientations are different, that must mean the second line starts
* "before" the first line and ends "after" it. It does the same, but with the roles of first
* and second line reversed. If both of these conditions are met, it follows that the lines
* must have crossed.
*
* Edge case: If an orientation comes out as collinear, the point of the other line that was
* checked may be on the other line or after/before it (if you extend the segment). If it is on
* the other line, this also means, the lines cross, since one line "stands" on the other.
* If however none of the collinear cases are like this, the lines cannot touch, because line
* segment a point was collinear with was not long enough.
*/
// Cache the necessary orientations.
let ls1_ls2start_orientation = triplet_orientation(ls1.start, ls1.end, ls2.start);
let ls1_ls2end_orientation = triplet_orientation(ls1.start, ls1.end, ls2.end);
let ls2_ls1start_orientation = triplet_orientation(ls2.start, ls2.end, ls1.start);
let ls2_ls1end_orientation = triplet_orientation(ls2.start, ls2.end, ls1.end);
// Check for the first case that wase described (general case).
if ls1_ls2start_orientation != ls1_ls2end_orientation
&& ls2_ls1start_orientation != ls2_ls1end_orientation
{
return true;
}
// Check if the start of ls2 lies on ls1
if ls1_ls2start_orientation == TripletOrientation::Collinear
&& ls1.contains_collinear(ls2.start)
{
return true;
}
// Check if the end of ls2 lies on ls1
if ls1_ls2end_orientation == TripletOrientation::Collinear
&& ls1.contains_collinear(ls2.end)
{
return true;
}
// Check if the start of ls1 lies on ls2
if ls2_ls1start_orientation == TripletOrientation::Collinear
&& ls2.contains_collinear(ls1.start)
{
return true;
}
// Check if the end of ls1 lies on ls2
if ls2_ls1end_orientation == TripletOrientation::Collinear
&& ls2.contains_collinear(ls1.end)
{
return true;
}
false
}
}
#[derive(PartialEq, Eq)]
pub(crate) enum TripletOrientation {
Clockwise,
Counterclockwise,
Collinear,
}
/// Helper function to determine which direction one would turn to traverse from the first point
/// over the second to the third point. The third option is collinear, in which case the three points
/// are on the same line.
pub(crate) fn triplet_orientation<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> TripletOrientation
where
T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
{
/* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than
* that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If
* they are the same it follows that the three points are collinear.
*/
match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) {
q if q > T::zero() => TripletOrientation::Clockwise,
q if q < T::zero() => TripletOrientation::Counterclockwise,
_ => TripletOrientation::Collinear,
}
}
|
