graphics_shapes/intersection/
line.rs1use crate::intersection::shared::*;
2use crate::intersection::IntersectsShape;
3use crate::prelude::*;
4use std::cmp::Ordering;
5
6impl IntersectsShape for Line {
7 fn intersects_rect(&self, rect: &Rect) -> bool {
8 line_rect(self, rect)
9 }
10
11 fn intersects_circle(&self, circle: &Circle) -> bool {
12 line_circle(self, circle)
13 }
14
15 fn intersects_line(&self, line: &Line) -> bool {
16 comp_line_line(self, line)
17 }
18
19 fn intersects_triangle(&self, triangle: &Triangle) -> bool {
20 line_triangle(self, triangle)
21 }
22
23 fn intersects_ellipse(&self, ellipse: &Ellipse) -> bool {
24 line_ellipse(self, ellipse)
25 }
26
27 fn intersects_polygon(&self, polygon: &Polygon) -> bool {
28 line_polygon(self, polygon)
29 }
30}
31
32fn direction(p: Coord, q: Coord, r: Coord) -> isize {
33 let value = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
34 match value.cmp(&0) {
35 Ordering::Less => 2,
36 Ordering::Equal => 0,
37 Ordering::Greater => 1,
38 }
39}
40
41fn comp_line_line(lhs: &Line, rhs: &Line) -> bool {
42 if lhs.contains_line(rhs) {
43 return true;
44 }
45
46 let ls = lhs.start();
47 let le = lhs.end();
48 let rs = rhs.start();
49 let re = rhs.end();
50
51 let d1 = direction(ls, le, rs);
52 let d2 = direction(ls, le, re);
53 let d3 = direction(rs, re, ls);
54 let d4 = direction(rs, re, le);
55
56 (d1 != d2 && d3 != d4)
57 || (d1 == 0 && rs.is_between(ls, le))
58 || (d2 == 0 && re.is_between(ls, le))
59 || (d3 == 0 && ls.is_between(rs, re))
60 || (d4 == 0 && le.is_between(rs, re))
61}
62
63#[cfg(test)]
64mod test {
65 mod line_circle {
66 use crate::circle::Circle;
67 use crate::intersection::IntersectsShape;
68 use crate::line::Line;
69
70 #[test]
71 fn line_above() {
72 let line = Line::new((10, 10), (40, 10));
73 let circle = Circle::new((20, 30), 8);
74 assert!(!line.intersects_circle(&circle));
75 }
76
77 #[test]
78 fn line_through_center_horz() {
79 let line = Line::new((50, 133), (194, 133));
80 let circle = Circle::new((123, 135), 15);
81 assert!(line.intersects_circle(&circle));
82 assert!(circle.intersects_line(&line));
83
84 let line = Line::new((57, 134), (201, 134));
85 let circle = Circle::new((123, 135), 15);
86 assert!(line.intersects_circle(&circle));
87 assert!(circle.intersects_line(&line));
88
89 let line = Line::new((194, 133), (50, 133));
90 let circle = Circle::new((123, 135), 15);
91 assert!(line.intersects_circle(&circle));
92 assert!(circle.intersects_line(&line));
93
94 let line = Line::new((201, 134), (57, 134));
95 let circle = Circle::new((123, 135), 15);
96 assert!(line.intersects_circle(&circle));
97 assert!(circle.intersects_line(&line));
98 }
99
100 #[test]
101 fn line_left() {
102 let line = Line::new((90, 115), (110, 135));
103 let circle = Circle::new((129, 136), 15);
104 assert!(!line.intersects_circle(&circle));
105 }
106
107 #[test]
108 fn collinear_ish() {
109 let line = Line::new((76, 73), (96, 93));
110 let circle = Circle::new((119, 114), 15);
111 assert!(!line.intersects_circle(&circle));
112 }
113 }
114
115 mod line_line {
116 use crate::intersection::IntersectsShape;
117 use crate::prelude::Line;
118
119 #[test]
120 fn two_parallel_lines_vert() {
121 let line1 = Line::new((10, 10), (10, 20));
122 let line2 = Line::new((30, 10), (30, 20));
123 assert!(!line1.intersects_line(&line2));
124 assert!(!line2.intersects_line(&line1));
125 }
126
127 #[test]
128 fn two_parallel_lines_horz() {
129 let line1 = Line::new((10, 10), (30, 10));
130 let line2 = Line::new((10, 30), (30, 30));
131 assert!(!line1.intersects_line(&line2));
132 assert!(!line2.intersects_line(&line1));
133 }
134
135 #[test]
136 fn two_lines_plus() {
137 let horz = Line::new((0, 15), (30, 15));
138 let vert = Line::new((15, 0), (15, 30));
139 assert!(vert.intersects_line(&horz));
140 assert!(horz.intersects_line(&vert));
141 }
142
143 #[test]
144 fn two_lines_cross() {
145 let horz = Line::new((0, 0), (30, 30));
146 let vert = Line::new((0, 30), (30, 0));
147 assert!(vert.intersects_line(&horz));
148 assert!(horz.intersects_line(&vert));
149 }
150
151 #[test]
152 fn two_lines_tip() {
153 let line1 = Line::new((0, 0), (30, 0));
154 let line2 = Line::new((30, 0), (30, 30));
155 assert!(line1.intersects_line(&line2));
156 assert!(line2.intersects_line(&line1));
157 }
158
159 #[test]
160 fn two_lines_overlap() {
161 let line1 = Line::new((0, 0), (30, 0));
162 let line2 = Line::new((0, 0), (30, 0));
163 assert!(line1.intersects_line(&line2));
164 assert!(line2.intersects_line(&line1));
165 }
166
167 #[test]
168 fn two_angled_inline_separate() {
169 let line1 = Line::new((109, 104), (129, 124));
170 let line2 = Line::new((134, 129), (159, 149));
171 assert!(!line1.intersects_line(&line2));
172 assert!(!line2.intersects_line(&line1));
173 }
174
175 #[test]
176 fn two_angled_inline_touching() {
177 let line1 = Line::new((82, 72), (102, 92));
178 let line2 = Line::new((96, 86), (116, 106));
179 assert!(line1.intersects_line(&line2));
180 assert!(line2.intersects_line(&line1));
181 let line1 = Line::new((102, 92), (82, 72));
182 let line2 = Line::new((116, 106), (96, 86));
183 assert!(line1.intersects_line(&line2));
184 assert!(line2.intersects_line(&line1));
185 }
186 }
187}