1//! The triangle primitive.
2
3use core::cmp::{max, min, Ordering};
4
5use crate::{
6 geometry::{Dimensions, Point},
7 primitives::{
8 common::{LineJoin, LineSide, LinearEquation, Scanline, StrokeOffset},
9 ContainsPoint, Line, PointsIter, Primitive, Rectangle,
10 },
11 transform::Transform,
12};
13
14mod points;
15mod scanline_intersections;
16mod scanline_iterator;
17mod styled;
18
19pub use points::Points;
20pub use styled::StyledPixelsIterator;
21
22/// Triangle primitive
23///
24/// # Examples
25///
26/// ## Create some triangles with different styles
27///
28/// ```rust
29/// use embedded_graphics::{
30/// pixelcolor::Rgb565, prelude::*, primitives::{Triangle, PrimitiveStyle},
31/// };
32/// # use embedded_graphics::mock_display::MockDisplay;
33/// # let mut display = MockDisplay::default();
34/// # display.set_allow_overdraw(true);
35///
36/// // Triangle with red 1 px wide stroke
37/// Triangle::new(Point::new(40, 20), Point::new(50, 25), Point::new(60, 60))
38/// .into_styled(PrimitiveStyle::with_stroke(Rgb565::RED, 1))
39/// .draw(&mut display)?;
40///
41/// // Triangle with translation applied
42/// Triangle::new(Point::new(40, 20), Point::new(50, 25), Point::new(60, 60))
43/// .translate(Point::new(-10, -20))
44/// .into_styled(PrimitiveStyle::with_stroke(Rgb565::GREEN, 1))
45/// .draw(&mut display)?;
46/// # Ok::<(), core::convert::Infallible>(())
47/// ```
48///
49/// ## Create a triangle from a slice
50///
51/// A triangle can be created from a `&[Point]` slice. If the slice is not exactly 3 elements long,
52/// the [`from_slice`] method will panic.
53///
54/// ```rust
55/// use embedded_graphics::{geometry::Point, primitives::Triangle};
56///
57/// let p1 = Point::new(5, 10);
58/// let p2 = Point::new(15, 25);
59/// let p3 = Point::new(5, 25);
60///
61/// let tri = Triangle::from_slice(&[p1, p2, p3]);
62/// #
63/// # assert_eq!(tri, Triangle::new(p1, p2, p3));
64/// ```
65///
66/// [`from_slice`]: Triangle::from_slice()
67#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Default)]
68#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
69pub struct Triangle {
70 /// The vertices of the triangle.
71 pub vertices: [Point; 3],
72}
73
74impl Primitive for Triangle {}
75
76impl PointsIter for Triangle {
77 type Iter = Points;
78
79 fn points(&self) -> Self::Iter {
80 Points::new(self)
81 }
82}
83
84impl ContainsPoint for Triangle {
85 fn contains(&self, point: Point) -> bool {
86 // Skip expensive calculations below if point is outside the bounding box
87 if !self.bounding_box().contains(point) {
88 return false;
89 }
90
91 let p = point;
92 let [p1, p2, p3] = self.vertices;
93
94 // Check if point is inside triangle using https://stackoverflow.com/a/20861130/383609.
95 // Works for any point ordering.
96 let is_inside = {
97 let s = p1.y * p3.x - p1.x * p3.y + (p3.y - p1.y) * p.x + (p1.x - p3.x) * p.y;
98 let t = p1.x * p2.y - p1.y * p2.x + (p1.y - p2.y) * p.x + (p2.x - p1.x) * p.y;
99
100 if (s < 0) != (t < 0) {
101 false
102 } else {
103 // Determinant
104 let a = self.area_doubled();
105
106 // If determinant is zero, triangle is colinear and can never contain a point.
107 if a == 0 {
108 return false;
109 }
110
111 // This check allows this algorithm to work with clockwise or counterclockwise
112 // triangles.
113 if a < 0 {
114 s <= 0 && s + t >= a
115 } else {
116 s >= 0 && s + t <= a
117 }
118 }
119 };
120
121 // Skip expensive point-on-line check below if point is definitely inside triangle
122 if is_inside {
123 return true;
124 }
125
126 // Sort points into same order as `ScanlineIterator` so this check produces the same results
127 // as a rendered triangle would.
128 let [p1, p2, p3] = self.sorted_yx().vertices;
129
130 // Special case: due to the Bresenham algorithm being used to render triangles, some pixel
131 // centers on a Styled<Triangle> lie outside the mathematical triangle. This check
132 // inefficiently checks to see if the point lies on any of the border edges.
133 Line::new(p1, p2)
134 .points()
135 .chain(Line::new(p1, p3).points())
136 .chain(Line::new(p2, p3).points())
137 .any(|line_point| line_point == p)
138 }
139}
140
141impl Dimensions for Triangle {
142 fn bounding_box(&self) -> Rectangle {
143 let [p1: Point, p2: Point, p3: Point] = self.vertices;
144
145 let x_min: i32 = min(v1:min(p1.x, p2.x), v2:p3.x);
146 let y_min: i32 = min(v1:min(p1.y, p2.y), v2:p3.y);
147
148 let x_max: i32 = max(v1:max(p1.x, p2.x), v2:p3.x);
149 let y_max: i32 = max(v1:max(p1.y, p2.y), v2:p3.y);
150
151 Rectangle::with_corners(corner_1:Point::new(x_min, y_min), corner_2:Point::new(x_max, y_max))
152 }
153}
154
155impl Triangle {
156 /// Create a new triangle with the given vertices.
157 pub const fn new(vertex1: Point, vertex2: Point, vertex3: Point) -> Self {
158 Triangle {
159 vertices: [vertex1, vertex2, vertex3],
160 }
161 }
162
163 /// Creates a new triangle from a [`Point`] slice.
164 ///
165 /// # Panics
166 ///
167 /// This method will panic if the given slice is not exactly 3 items long.
168 ///
169 /// [`Point`]: super::super::geometry::Point
170 pub fn from_slice(vertices: &[Point]) -> Self {
171 match vertices {
172 [p1, p2, p3] => Self::new(*p1, *p2, *p3),
173 vertices => panic!("source slice length ({}) must equal 3", vertices.len()),
174 }
175 }
176
177 /// Return the area of the triangle, doubled.
178 ///
179 /// This method can be used to determine if the triangle is colinear by checking if the returned
180 /// value is equal to zero.
181 pub(in crate::primitives) const fn area_doubled(&self) -> i32 {
182 let [p1, p2, p3] = self.vertices;
183
184 -p2.y * p3.x + p1.y * (p3.x - p2.x) + p1.x * (p2.y - p3.y) + p2.x * p3.y
185 }
186
187 /// Create a new triangle with points sorted in a clockwise direction.
188 pub(in crate::primitives::triangle) fn sorted_clockwise(&self) -> Self {
189 match self.area_doubled().cmp(&0) {
190 // Triangle is wound CCW. Swap two points to make it CW.
191 Ordering::Less => Self::new(self.vertices[1], self.vertices[0], self.vertices[2]),
192 // Triangle is already CW, do nothing.
193 Ordering::Greater => *self,
194 // Triangle is colinear. Sort points so they lie sequentially along the line.
195 Ordering::Equal => self.sorted_yx(),
196 }
197 }
198
199 /// Sort the 3 vertices of the triangle in order of increasing Y value.
200 ///
201 /// If two points have the same Y value, the one with the lesser X value is put before.
202 const fn sorted_yx(&self) -> Self {
203 let [p1, p2, p3] = self.vertices;
204
205 let (y1, y2) = sort_two_yx(p1, p2);
206 let (y1, y3) = sort_two_yx(p3, y1);
207 let (y2, y3) = sort_two_yx(y3, y2);
208
209 Self::new(y1, y2, y3)
210 }
211
212 pub(in crate::primitives::triangle) fn scanline_intersection(
213 &self,
214 scanline_y: i32,
215 ) -> Scanline {
216 let [p1, p2, p3] = self.sorted_yx().vertices;
217
218 let mut scanline = Scanline::new_empty(scanline_y);
219
220 // Triangle is colinear. We can get away with only intersecting the single line.
221 if self.area_doubled() == 0 {
222 scanline.bresenham_intersection(&Line::new(p1, p3));
223
224 return scanline;
225 }
226
227 scanline.bresenham_intersection(&Line::new(p1, p2));
228 scanline.bresenham_intersection(&Line::new(p1, p3));
229 scanline.bresenham_intersection(&Line::new(p2, p3));
230
231 scanline
232 }
233
234 /// Generate a line join for each corner of the triangle.
235 fn joins(&self, stroke_width: u32, stroke_offset: StrokeOffset) -> [LineJoin; 3] {
236 let [p1, p2, p3] = self.vertices;
237
238 [
239 LineJoin::from_points(p3, p1, p2, stroke_width, stroke_offset),
240 LineJoin::from_points(p1, p2, p3, stroke_width, stroke_offset),
241 LineJoin::from_points(p2, p3, p1, stroke_width, stroke_offset),
242 ]
243 }
244
245 /// Compute whether a triangle with thick stroke has a hole in its center or is completely
246 /// filled by stroke.
247 // PERF: This doesn't need to compute the entire join, much like how `thick_stroke_inset`
248 // doesn't
249 pub(in crate::primitives::triangle) fn is_collapsed(
250 &self,
251 stroke_width: u32,
252 stroke_offset: StrokeOffset,
253 ) -> bool {
254 let joins = self.joins(stroke_width, stroke_offset);
255
256 joins.iter().enumerate().any(|(i, join)| {
257 // Quick check: if the join is degenerate, no hole can occur.
258 if join.is_degenerate() {
259 return true;
260 }
261
262 // Compute inner-most points of each join. The triangle is sorted clockwise, so that's
263 // the right-side point. The `first_edge_end` and `second_edge_start` points are always
264 // the same in this case, as this is the "pinched" side of the join, so we'll
265 // arbitrarily pick `first_edge_end`.
266 let inner_point = join.first_edge_end.right;
267
268 // Find opposite edge to the given point.
269 let opposite = {
270 let start = self.vertices[(i + 1) % 3];
271 let end = self.vertices[(i + 2) % 3];
272
273 // Get right side extent (triangle is sorted clockwise, remember)
274 Line::new(start, end).extents(stroke_width, stroke_offset).1
275 };
276
277 // If the inner point is to the left of the opposite side line, the triangle edges self-
278 // intersect, so the triangle is collapsed.
279 LinearEquation::from_line(&opposite).check_side(inner_point, LineSide::Left)
280 })
281 }
282}
283
284impl Transform for Triangle {
285 /// Translate the triangle from its current position to a new position by (x, y) pixels,
286 /// returning a new `Triangle`. For a mutating transform, see `translate_mut`.
287 ///
288 /// ```
289 /// # use embedded_graphics::primitives::Triangle;
290 /// # use embedded_graphics::prelude::*;
291 /// let tri = Triangle::new(Point::new(5, 10), Point::new(15, 20), Point::new(8, 15));
292 /// let moved = tri.translate(Point::new(10, 10));
293 ///
294 /// assert_eq!(
295 /// moved,
296 /// Triangle::new(Point::new(15, 20), Point::new(25, 30), Point::new(18, 25))
297 /// );
298 /// ```
299 fn translate(&self, by: Point) -> Self {
300 let mut triangle = *self;
301 triangle.translate_mut(by);
302 triangle
303 }
304
305 /// Translate the triangle from its current position to a new position by (x, y) pixels.
306 ///
307 /// ```
308 /// # use embedded_graphics::primitives::Triangle;
309 /// # use embedded_graphics::prelude::*;
310 /// let mut tri = Triangle::new(Point::new(5, 10), Point::new(15, 20), Point::new(10, 15));
311 /// tri.translate_mut(Point::new(10, 10));
312 ///
313 /// assert_eq!(
314 /// tri,
315 /// Triangle::new(Point::new(15, 20), Point::new(25, 30), Point::new(20, 25))
316 /// )
317 /// ```
318 fn translate_mut(&mut self, by: Point) -> &mut Self {
319 self.vertices.iter_mut().for_each(|v| *v += by);
320
321 self
322 }
323}
324
325const fn sort_two_yx(p1: Point, p2: Point) -> (Point, Point) {
326 // If p1.y is less than p2.y, return it first. Otherwise, if they have the same Y coordinate,
327 // the first point becomes the one with the lesser X coordinate.
328 if p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x) {
329 (p1, p2)
330 } else {
331 (p2, p1)
332 }
333}
334
335#[cfg(test)]
336mod tests {
337 use super::*;
338 use crate::{geometry::Size, mock_display::MockDisplay, pixelcolor::BinaryColor};
339
340 #[test]
341 fn dimensions() {
342 let tri = Triangle::new(Point::new(5, 10), Point::new(15, 25), Point::new(5, 25));
343 let moved = tri.translate(Point::new(-10, -11));
344
345 assert_eq!(tri.bounding_box().size, Size::new(11, 16));
346
347 assert_eq!(
348 moved,
349 Triangle::new(Point::new(-5, -1), Point::new(5, 14), Point::new(-5, 14))
350 );
351 assert_eq!(moved.bounding_box().size, Size::new(11, 16));
352 }
353
354 #[test]
355 fn it_can_be_translated() {
356 let tri = Triangle::new(Point::new(5, 10), Point::new(15, 20), Point::new(10, 15));
357 let moved = tri.translate(Point::new(5, 10));
358
359 assert_eq!(
360 moved,
361 Triangle::new(Point::new(10, 20), Point::new(20, 30), Point::new(15, 25))
362 );
363 }
364
365 #[test]
366 fn contains() {
367 let triangles = [
368 Triangle::new(Point::new(0, 0), Point::new(63, 10), Point::new(15, 63)),
369 Triangle::new(Point::new(5, 0), Point::new(30, 63), Point::new(63, 0)),
370 Triangle::new(Point::new(0, 0), Point::new(0, 63), Point::new(63, 30)),
371 Triangle::new(Point::new(22, 0), Point::new(0, 63), Point::new(63, 63)),
372 Triangle::new(Point::new(0, 22), Point::new(63, 0), Point::new(63, 63)),
373 ];
374
375 for triangle in triangles.iter() {
376 let expected = MockDisplay::from_points(triangle.points(), BinaryColor::On);
377
378 for point in Rectangle::new(Point::new(-5, -5), Size::new(70, 70)).points() {
379 let should_contain =
380 expected.bounding_box().contains(point) && expected.get_pixel(point).is_some();
381
382 assert_eq!(
383 triangle.contains(point),
384 should_contain,
385 "{:?}, {:?}",
386 point,
387 triangle
388 );
389 }
390 }
391 }
392
393 #[test]
394 fn colinear_never_contains() {
395 let triangles = [
396 Triangle::new(Point::new(5, 10), Point::new(15, 20), Point::new(10, 15)),
397 Triangle::new(Point::new(2, 2), Point::new(2, 4), Point::new(2, 4)),
398 Triangle::new(Point::new(2, 2), Point::new(4, 2), Point::new(4, 2)),
399 ];
400
401 for triangle in triangles.iter() {
402 for point in Rectangle::new(Point::new(-5, -5), Size::new(70, 70)).points() {
403 assert_eq!(triangle.contains(point), false);
404 }
405 }
406 }
407
408 #[test]
409 #[should_panic(expected = "source slice length (2) must equal 3")]
410 fn slice_panic_too_short() {
411 let points = [Point::zero(), Point::zero()];
412
413 Triangle::from_slice(&points);
414 }
415
416 #[test]
417 #[should_panic(expected = "source slice length (4) must equal 3")]
418 fn slice_panic_too_long() {
419 let points = [Point::zero(), Point::zero(), Point::zero(), Point::zero()];
420
421 Triangle::from_slice(&points);
422 }
423
424 #[test]
425 fn slice_just_right() {
426 let points = [
427 Point::new_equal(1),
428 Point::new_equal(2),
429 Point::new_equal(3),
430 ];
431
432 assert_eq!(
433 Triangle::from_slice(&points),
434 Triangle::new(
435 Point::new_equal(1),
436 Point::new_equal(2),
437 Point::new_equal(3)
438 )
439 );
440 }
441
442 #[test]
443 fn check_collapsed() {
444 let triangle = Triangle::new(Point::new(10, 10), Point::new(30, 20), Point::new(20, 25));
445
446 assert_eq!(triangle.is_collapsed(20, StrokeOffset::None), true);
447 }
448}
449