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