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
147
148
149
150
151
152
153
154
|
use super::{Rect, Vec2};
use alga::general::{ClosedDiv, ClosedMul, ClosedSub};
use nalgebra::{RealField, Scalar};
use num_traits::Zero;
#[derive(Debug)]
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
}
pub fn intersection(line_a: &LineSegment<T>, line_b: &LineSegment<T>) -> Option<Vec2<T>>
where
T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField,
{
// Calculate the differences of each line value from starting point to end point
// coordinate.
let dax = line_a.end.x - line_a.start.x;
let dbx = line_b.end.x - line_b.start.x;
let day = line_a.end.y - line_a.start.y;
let dby = line_b.end.y - line_b.start.y;
// Calculate determinant to see, if the lines are parallel or not
// TODO: Collinearity check?
let d = (dax * dby) - (day * dbx);
if d == T::zero() {
None
} else {
let ad = (line_a.start.x * line_a.end.y) - (line_a.start.y * line_a.end.x);
let bd = (line_b.start.x * line_b.end.y) - (line_b.start.y * line_b.end.x);
let out = Vec2::new(((ad * dbx) - (dax * bd)) / d, ((ad * dby) - (day * bd)) / d);
/* Since the line intersection, not the line segment intersection is calculated, a
* bounding check is necessary, to see if the intersection still lies inside both of
* the segments. We know it's on the lines, so checking with the lines bounding box is
* faster than checking where on the line exactly it would be.
*/
if Rect::bounding_rect(line_a.start, line_a.end).contains(out)
&& Rect::bounding_rect(line_b.start, line_b.end).contains(out)
{
Some(out)
} else {
None
}
}
}
}
#[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,
}
}
|
