1use crate::scalar::Scalar;
2use crate::traits::Transformation;
3use crate::LineSegment;
4use crate::{point, Box2D, Point};
5
6/// A 2D triangle defined by three points `a`, `b` and `c`.
7#[derive(Copy, Clone, Debug, PartialEq)]
8#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
9pub struct Triangle<S> {
10 pub a: Point<S>,
11 pub b: Point<S>,
12 pub c: Point<S>,
13}
14
15impl<S: Scalar> Triangle<S> {
16 #[inline]
17 fn get_barycentric_coords_for_point(&self, point: Point<S>) -> (S, S, S) {
18 let v0 = self.b - self.a;
19 let v1 = self.c - self.a;
20 let v2 = point - self.a;
21 let inv = S::ONE / v0.cross(v1);
22 let a = v0.cross(v2) * inv;
23 let b = v2.cross(v1) * inv;
24 let c = S::ONE - a - b;
25
26 (a, b, c)
27 }
28
29 pub fn contains_point(&self, point: Point<S>) -> bool {
30 let coords = self.get_barycentric_coords_for_point(point);
31
32 coords.0 > S::ZERO && coords.1 > S::ZERO && coords.2 > S::ZERO
33 }
34
35 /// Returns a conservative range of x that contains this triangle.
36 #[inline]
37 pub fn bounding_range_x(&self) -> (S, S) {
38 let min_x = self.a.x.min(self.b.x).min(self.c.x);
39 let max_x = self.a.x.max(self.b.x).max(self.c.x);
40
41 (min_x, max_x)
42 }
43
44 /// Returns a conservative range of y that contains this triangle.
45 #[inline]
46 pub fn bounding_range_y(&self) -> (S, S) {
47 let min_y = self.a.y.min(self.b.y).min(self.c.y);
48 let max_y = self.a.y.max(self.b.y).max(self.c.y);
49
50 (min_y, max_y)
51 }
52
53 /// Returns the smallest rectangle that contains this triangle.
54 #[inline]
55 pub fn bounding_box(&self) -> Box2D<S> {
56 let (min_x, max_x) = self.bounding_range_x();
57 let (min_y, max_y) = self.bounding_range_y();
58
59 Box2D {
60 min: point(min_x, min_y),
61 max: point(max_x, max_y),
62 }
63 }
64
65 #[inline]
66 pub fn ab(&self) -> LineSegment<S> {
67 LineSegment {
68 from: self.a,
69 to: self.b,
70 }
71 }
72
73 #[inline]
74 pub fn ba(&self) -> LineSegment<S> {
75 LineSegment {
76 from: self.b,
77 to: self.a,
78 }
79 }
80
81 #[inline]
82 pub fn bc(&self) -> LineSegment<S> {
83 LineSegment {
84 from: self.b,
85 to: self.c,
86 }
87 }
88
89 #[inline]
90 pub fn cb(&self) -> LineSegment<S> {
91 LineSegment {
92 from: self.c,
93 to: self.b,
94 }
95 }
96
97 #[inline]
98 pub fn ca(&self) -> LineSegment<S> {
99 LineSegment {
100 from: self.c,
101 to: self.a,
102 }
103 }
104
105 #[inline]
106 pub fn ac(&self) -> LineSegment<S> {
107 LineSegment {
108 from: self.a,
109 to: self.c,
110 }
111 }
112
113 /// [Not implemented] Applies the transform to this triangle and returns the results.
114 #[inline]
115 pub fn transform<T: Transformation<S>>(&self, transform: &T) -> Self {
116 Triangle {
117 a: transform.transform_point(self.a),
118 b: transform.transform_point(self.b),
119 c: transform.transform_point(self.c),
120 }
121 }
122
123 /// Test for triangle-triangle intersection.
124 pub fn intersects(&self, other: &Self) -> bool {
125 // TODO: This should be optimized.
126 // A bounding rect check should speed this up dramatically.
127 // Inlining and reusing intermediate computation of the intersections
128 // functions below and using SIMD would help too.
129 self.ab().intersects(&other.ab())
130 || self.ab().intersects(&other.bc())
131 || self.ab().intersects(&other.ac())
132 || self.bc().intersects(&other.ab())
133 || self.bc().intersects(&other.bc())
134 || self.bc().intersects(&other.ac())
135 || self.ac().intersects(&other.ab())
136 || self.ac().intersects(&other.bc())
137 || self.ac().intersects(&other.ac())
138 || self.contains_point(other.a)
139 || other.contains_point(self.a)
140 || *self == *other
141 }
142
143 /// Test for triangle-segment intersection.
144 #[inline]
145 pub fn intersects_line_segment(&self, segment: &LineSegment<S>) -> bool {
146 self.ab().intersects(segment)
147 || self.bc().intersects(segment)
148 || self.ac().intersects(segment)
149 || self.contains_point(segment.from)
150 }
151}
152
153#[test]
154fn test_triangle_contains() {
155 assert!(Triangle {
156 a: point(0.0, 0.0),
157 b: point(1.0, 0.0),
158 c: point(0.0, 1.0),
159 }
160 .contains_point(point(0.2, 0.2)));
161 assert!(!Triangle {
162 a: point(0.0, 0.0),
163 b: point(1.0, 0.0),
164 c: point(0.0, 1.0),
165 }
166 .contains_point(point(1.2, 0.2)));
167
168 // Triangle vertex winding should not matter
169 assert!(Triangle {
170 a: point(1.0, 0.0),
171 b: point(0.0, 0.0),
172 c: point(0.0, 1.0),
173 }
174 .contains_point(point(0.2, 0.2)));
175
176 // Point exactly on the edge counts as outside the triangle.
177 assert!(!Triangle {
178 a: point(0.0, 0.0),
179 b: point(1.0, 0.0),
180 c: point(0.0, 1.0),
181 }
182 .contains_point(point(0.0, 0.0)));
183}
184
185#[test]
186fn test_segments() {
187 let t = Triangle {
188 a: point(1.0, 2.0),
189 b: point(3.0, 4.0),
190 c: point(5.0, 6.0),
191 };
192
193 assert_eq!(t.ab(), t.ba().flip());
194 assert_eq!(t.ac(), t.ca().flip());
195 assert_eq!(t.bc(), t.cb().flip());
196}
197
198#[test]
199fn test_triangle_intersections() {
200 let t1 = Triangle {
201 a: point(1.0, 1.0),
202 b: point(6.0, 1.0),
203 c: point(3.0, 6.0),
204 };
205
206 let t2 = Triangle {
207 a: point(2.0, 2.0),
208 b: point(0.0, 3.0),
209 c: point(1.0, 6.0),
210 };
211
212 assert!(t1.intersects(&t2));
213 assert!(t2.intersects(&t1));
214
215 // t3 and t1 have an overlapping edge, they are "touching" but not intersecting.
216 let t3 = Triangle {
217 a: point(6.0, 5.0),
218 b: point(6.0, 1.0),
219 c: point(3.0, 6.0),
220 };
221
222 assert!(!t1.intersects(&t3));
223 assert!(!t3.intersects(&t1));
224
225 // t4 is entirely inside t1.
226 let t4 = Triangle {
227 a: point(2.0, 2.0),
228 b: point(5.0, 2.0),
229 c: point(3.0, 4.0),
230 };
231
232 assert!(t1.intersects(&t4));
233 assert!(t4.intersects(&t1));
234
235 // Triangles intersect themselves.
236 assert!(t1.intersects(&t1));
237 assert!(t2.intersects(&t2));
238 assert!(t3.intersects(&t3));
239 assert!(t4.intersects(&t4));
240}
241
242#[test]
243fn test_segment_intersection() {
244 let tri = Triangle {
245 a: point(1.0, 1.0),
246 b: point(6.0, 1.0),
247 c: point(3.0, 6.0),
248 };
249
250 let l1 = LineSegment {
251 from: point(2.0, 0.0),
252 to: point(3.0, 4.0),
253 };
254
255 assert!(tri.intersects_line_segment(&l1));
256
257 let l2 = LineSegment {
258 from: point(1.0, 3.0),
259 to: point(0.0, 4.0),
260 };
261
262 assert!(!tri.intersects_line_segment(&l2));
263
264 // The segment is entirely inside the triangle.
265 let inside = LineSegment {
266 from: point(2.0, 2.0),
267 to: point(5.0, 2.0),
268 };
269
270 assert!(tri.intersects_line_segment(&inside));
271
272 // A triangle does not intersect its own segments.
273 assert!(!tri.intersects_line_segment(&tri.ab()));
274 assert!(!tri.intersects_line_segment(&tri.bc()));
275 assert!(!tri.intersects_line_segment(&tri.ac()));
276}
277
278#[test]
279fn test_bounding_box() {
280 let t1 = Triangle {
281 a: point(10.0, 20.0),
282 b: point(35.0, 40.0),
283 c: point(50.0, 10.0),
284 };
285 let r1 = Box2D {
286 min: point(10.0, 10.0),
287 max: point(50.0, 40.0),
288 };
289
290 let t2 = Triangle {
291 a: point(5.0, 30.0),
292 b: point(25.0, 10.0),
293 c: point(35.0, 40.0),
294 };
295 let r2 = Box2D {
296 min: point(5.0, 10.0),
297 max: point(35.0, 40.0),
298 };
299
300 let t3 = Triangle {
301 a: point(1.0, 1.0),
302 b: point(2.0, 5.0),
303 c: point(0.0, 4.0),
304 };
305 let r3 = Box2D {
306 min: point(0.0, 1.0),
307 max: point(2.0, 5.0),
308 };
309
310 let cases = std::vec![(t1, r1), (t2, r2), (t3, r3)];
311 for &(tri, r) in &cases {
312 assert_eq!(tri.bounding_box(), r);
313 }
314}
315