|
13908
|
1 |
pub struct Point {
|
|
|
2 |
x: i32,
|
|
|
3 |
y: i32,
|
|
|
4 |
}
|
|
|
5 |
|
|
|
6 |
pub struct Outline {
|
|
|
7 |
points: Vec<Point>,
|
|
|
8 |
}
|
|
|
9 |
|
|
13921
|
10 |
fn check_intersect(
|
|
|
11 |
segment1_start: &Point,
|
|
|
12 |
segment1_end: &Point,
|
|
|
13 |
segment2_start: &Point,
|
|
|
14 |
segment2_end: &Point,
|
|
|
15 |
) -> bool {
|
|
|
16 |
let dm: i32 = (segment2_end.y - segment2_start.y) * (segment1_end.x - segment1_start.x)
|
|
|
17 |
- (segment2_end.x - segment2_start.x) * (segment1_end.y - segment1_start.y);
|
|
13908
|
18 |
|
|
|
19 |
if dm == 0 {
|
|
|
20 |
return false;
|
|
|
21 |
}
|
|
|
22 |
|
|
13921
|
23 |
let c1: i32 = (segment2_end.x - segment2_start.x) * (segment1_start.y - segment2_start.y)
|
|
|
24 |
- (segment2_end.y - segment2_start.y) * (segment1_start.x - segment2_start.x);
|
|
13908
|
25 |
|
|
|
26 |
if dm > 0 {
|
|
|
27 |
if (c1 < 0) || (c1 > dm) {
|
|
|
28 |
return false;
|
|
|
29 |
}
|
|
|
30 |
} else {
|
|
|
31 |
if (c1 > 0) || (c1 < dm) {
|
|
|
32 |
return false;
|
|
|
33 |
}
|
|
|
34 |
}
|
|
|
35 |
|
|
13921
|
36 |
let c2: i32 = (segment1_end.x - segment2_start.x) * (segment1_start.y - segment2_start.y)
|
|
|
37 |
- (segment1_end.y - segment2_start.y) * (segment1_start.x - segment2_start.x);
|
|
13908
|
38 |
|
|
|
39 |
if dm > 0 {
|
|
|
40 |
if (c2 < 0) || (c2 > dm) {
|
|
|
41 |
return false;
|
|
|
42 |
}
|
|
|
43 |
} else {
|
|
|
44 |
if (c2 > 0) || (c2 < dm) {
|
|
|
45 |
return false;
|
|
|
46 |
}
|
|
|
47 |
}
|
|
|
48 |
|
|
|
49 |
true
|
|
|
50 |
}
|
|
|
51 |
|
|
|
52 |
impl Outline {
|
|
|
53 |
fn check_intersects_self_at_index(&self, index: usize) -> bool {
|
|
|
54 |
if index <= 0 || index > self.points.len() {
|
|
|
55 |
return false;
|
|
|
56 |
}
|
|
|
57 |
|
|
|
58 |
for i in 1..=self.points.len() - 3 {
|
|
|
59 |
if i <= index - 1 || i >= index + 2 {
|
|
|
60 |
if i != index - 1 && check_intersect(
|
|
|
61 |
&self.points[index],
|
|
|
62 |
&self.points[index - 1],
|
|
|
63 |
&self.points[i],
|
|
|
64 |
&self.points[i - 1],
|
|
|
65 |
) {
|
|
|
66 |
return true;
|
|
|
67 |
}
|
|
|
68 |
if i != index + 2 && check_intersect(
|
|
|
69 |
&self.points[index],
|
|
|
70 |
&self.points[index + 1],
|
|
|
71 |
&self.points[i],
|
|
|
72 |
&self.points[i - 1],
|
|
|
73 |
) {
|
|
|
74 |
return true;
|
|
|
75 |
}
|
|
|
76 |
}
|
|
|
77 |
}
|
|
|
78 |
|
|
|
79 |
false
|
|
|
80 |
}
|
|
|
81 |
}
|
|
|
82 |
|
|
|
83 |
#[cfg(test)]
|
|
|
84 |
#[test]
|
|
|
85 |
fn intersection() {
|
|
13921
|
86 |
let p1 = Point { x: 0, y: 0 };
|
|
|
87 |
let p2 = Point { x: 0, y: 10 };
|
|
|
88 |
let p3 = Point { x: -5, y: 5 };
|
|
|
89 |
let p4 = Point { x: 5, y: 5 };
|
|
|
90 |
let p5 = Point { x: 5, y: 16 };
|
|
13908
|
91 |
|
|
|
92 |
assert!(check_intersect(&p1, &p2, &p3, &p4));
|
|
|
93 |
assert!(!check_intersect(&p1, &p2, &p3, &p5));
|
|
|
94 |
}
|