kurbo/
triangle.rs

1// Copyright 2024 the Kurbo Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Triangle shape
5use crate::{Circle, PathEl, Point, Rect, Shape, Vec2};
6
7use core::cmp::*;
8use core::f64::consts::FRAC_PI_4;
9use core::ops::{Add, Sub};
10
11#[cfg(not(feature = "std"))]
12use crate::common::FloatFuncs;
13
14/// Triangle
15//     A
16//     *
17//    / \
18//   /   \
19//  *-----*
20//  B     C
21#[derive(Clone, Copy, PartialEq, Debug)]
22#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
23#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
24pub struct Triangle {
25    /// vertex a.
26    pub a: Point,
27    /// vertex b.
28    pub b: Point,
29    /// vertex c.
30    pub c: Point,
31}
32
33impl Triangle {
34    /// The empty [`Triangle`] at the origin.
35    pub const ZERO: Self = Self::from_coords((0., 0.), (0., 0.), (0., 0.));
36
37    /// Equilateral [`Triangle`] with the x-axis unit vector as its base.
38    pub const EQUILATERAL: Self = Self::from_coords(
39        (
40            1.0 / 2.0,
41            1.732050807568877293527446341505872367_f64 / 2.0, /* (sqrt 3)/2 */
42        ),
43        (0.0, 0.0),
44        (1.0, 0.0),
45    );
46
47    /// A new [`Triangle`] from three vertices ([`Point`]s).
48    #[inline(always)]
49    pub fn new(a: impl Into<Point>, b: impl Into<Point>, c: impl Into<Point>) -> Self {
50        Self {
51            a: a.into(),
52            b: b.into(),
53            c: c.into(),
54        }
55    }
56
57    /// A new [`Triangle`] from three float vertex coordinates.
58    ///
59    /// Works as a constant [`Triangle::new`].
60    #[inline(always)]
61    pub const fn from_coords(a: (f64, f64), b: (f64, f64), c: (f64, f64)) -> Self {
62        Self {
63            a: Point::new(a.0, a.1),
64            b: Point::new(b.0, b.1),
65            c: Point::new(c.0, c.1),
66        }
67    }
68
69    /// The centroid of the [`Triangle`].
70    #[inline]
71    pub fn centroid(&self) -> Point {
72        (1.0 / 3.0 * (self.a.to_vec2() + self.b.to_vec2() + self.c.to_vec2())).to_point()
73    }
74
75    /// The offset of each vertex from the centroid.
76    #[inline]
77    pub fn offsets(&self) -> [Vec2; 3] {
78        let centroid = self.centroid().to_vec2();
79
80        [
81            (self.a.to_vec2() - centroid),
82            (self.b.to_vec2() - centroid),
83            (self.c.to_vec2() - centroid),
84        ]
85    }
86
87    /// The area of the [`Triangle`].
88    #[inline]
89    pub fn area(&self) -> f64 {
90        0.5 * (self.b - self.a).cross(self.c - self.a)
91    }
92
93    /// Whether this [`Triangle`] has zero area.
94    #[doc(alias = "is_empty")]
95    #[inline]
96    pub fn is_zero_area(&self) -> bool {
97        self.area() == 0.0
98    }
99
100    /// The inscribed circle of [`Triangle`].
101    ///
102    /// This is defined as the greatest [`Circle`] that lies within the [`Triangle`].
103    #[doc(alias = "incircle")]
104    #[inline]
105    pub fn inscribed_circle(&self) -> Circle {
106        let ab = self.a.distance(self.b);
107        let bc = self.b.distance(self.c);
108        let ac = self.a.distance(self.c);
109
110        // [`Vec2::div`] also multiplies by the reciprocal of the argument, but as this reciprocal
111        // is reused below to calculate the radius, there's explicitly only one division needed.
112        let perimeter_recip = 1. / (ab + bc + ac);
113        let incenter = (self.a.to_vec2() * bc + self.b.to_vec2() * ac + self.c.to_vec2() * ab)
114            * perimeter_recip;
115
116        Circle::new(incenter.to_point(), 2.0 * self.area() * perimeter_recip)
117    }
118
119    /// The circumscribed circle of [`Triangle`].
120    ///
121    /// This is defined as the smallest [`Circle`] which intercepts each vertex of the [`Triangle`].
122    #[doc(alias = "circumcircle")]
123    #[inline]
124    pub fn circumscribed_circle(&self) -> Circle {
125        let b = self.b - self.a;
126        let c = self.c - self.a;
127        let b_len2 = b.hypot2();
128        let c_len2 = c.hypot2();
129        let d_recip = 0.5 / b.cross(c);
130
131        let x = (c.y * b_len2 - b.y * c_len2) * d_recip;
132        let y = (b.x * c_len2 - c.x * b_len2) * d_recip;
133        let r = (b_len2 * c_len2).sqrt() * (c - b).hypot() * d_recip;
134
135        Circle::new(self.a + Vec2::new(x, y), r)
136    }
137
138    /// Expand the triangle by a constant amount (`scalar`) in all directions.
139    #[doc(alias = "offset")]
140    pub fn inflate(&self, scalar: f64) -> Self {
141        let centroid = self.centroid();
142
143        Self::new(
144            centroid + (0.0, scalar),
145            centroid + scalar * Vec2::from_angle(5.0 * FRAC_PI_4),
146            centroid + scalar * Vec2::from_angle(7.0 * FRAC_PI_4),
147        )
148    }
149
150    /// Is this [`Triangle`] [finite]?
151    ///
152    /// [finite]: f64::is_finite
153    #[inline]
154    pub fn is_finite(&self) -> bool {
155        self.a.is_finite() && self.b.is_finite() && self.c.is_finite()
156    }
157
158    /// Is this [`Triangle`] [NaN]?
159    ///
160    /// [NaN]: f64::is_nan
161    #[inline]
162    pub fn is_nan(&self) -> bool {
163        self.a.is_nan() || self.b.is_nan() || self.c.is_nan()
164    }
165}
166
167impl From<(Point, Point, Point)> for Triangle {
168    fn from(points: (Point, Point, Point)) -> Triangle {
169        Triangle::new(points.0, points.1, points.2)
170    }
171}
172
173impl Add<Vec2> for Triangle {
174    type Output = Triangle;
175
176    #[inline]
177    fn add(self, v: Vec2) -> Triangle {
178        Triangle::new(self.a + v, self.b + v, self.c + v)
179    }
180}
181
182impl Sub<Vec2> for Triangle {
183    type Output = Triangle;
184
185    #[inline]
186    fn sub(self, v: Vec2) -> Triangle {
187        Triangle::new(self.a - v, self.b - v, self.c - v)
188    }
189}
190
191#[doc(hidden)]
192pub struct TrianglePathIter {
193    triangle: Triangle,
194    ix: usize,
195}
196
197impl Shape for Triangle {
198    type PathElementsIter<'iter> = TrianglePathIter;
199
200    fn path_elements(&self, _tolerance: f64) -> TrianglePathIter {
201        TrianglePathIter {
202            triangle: *self,
203            ix: 0,
204        }
205    }
206
207    #[inline]
208    fn area(&self) -> f64 {
209        Triangle::area(self)
210    }
211
212    #[inline]
213    fn perimeter(&self, _accuracy: f64) -> f64 {
214        self.a.distance(self.b) + self.b.distance(self.c) + self.c.distance(self.a)
215    }
216
217    #[inline]
218    fn winding(&self, pt: Point) -> i32 {
219        let s0 = (self.b - self.a).cross(pt - self.a).signum();
220        let s1 = (self.c - self.b).cross(pt - self.b).signum();
221        let s2 = (self.a - self.c).cross(pt - self.c).signum();
222
223        if s0 == s1 && s1 == s2 {
224            s0 as i32
225        } else {
226            0
227        }
228    }
229
230    #[inline]
231    fn bounding_box(&self) -> Rect {
232        Rect::new(
233            self.a.x.min(self.b.x.min(self.c.x)),
234            self.a.y.min(self.b.y.min(self.c.y)),
235            self.a.x.max(self.b.x.max(self.c.x)),
236            self.a.y.max(self.b.y.max(self.c.y)),
237        )
238    }
239}
240
241// Note: vertices a, b and c are not guaranteed to be in order as described in the struct comments
242//       (i.e. as "vertex a is topmost, vertex b is leftmost, and vertex c is rightmost")
243impl Iterator for TrianglePathIter {
244    type Item = PathEl;
245
246    fn next(&mut self) -> Option<PathEl> {
247        self.ix += 1;
248        match self.ix {
249            1 => Some(PathEl::MoveTo(self.triangle.a)),
250            2 => Some(PathEl::LineTo(self.triangle.b)),
251            3 => Some(PathEl::LineTo(self.triangle.c)),
252            4 => Some(PathEl::ClosePath),
253            _ => None,
254        }
255    }
256}
257
258// TODO: better and more tests
259#[cfg(test)]
260mod tests {
261    use crate::{Point, Triangle, Vec2};
262
263    fn assert_approx_eq(x: f64, y: f64, max_relative_error: f64) {
264        assert!(
265            (x - y).abs() <= f64::max(x.abs(), y.abs()) * max_relative_error,
266            "{x} != {y}"
267        );
268    }
269
270    fn assert_approx_eq_point(x: Point, y: Point, max_relative_error: f64) {
271        assert_approx_eq(x.x, y.x, max_relative_error);
272        assert_approx_eq(x.y, y.y, max_relative_error);
273    }
274
275    #[test]
276    fn centroid() {
277        let test = Triangle::from_coords((-90.02, 3.5), (7.2, -9.3), (8.0, 9.1)).centroid();
278        let expected = Point::new(-24.94, 1.1);
279
280        assert_approx_eq_point(test, expected, f64::EPSILON * 100.);
281    }
282
283    #[test]
284    fn offsets() {
285        let test = Triangle::from_coords((-20.0, 180.2), (1.2, 0.0), (290.0, 100.0)).offsets();
286        let expected = [
287            Vec2::new(-110.4, 86.8),
288            Vec2::new(-89.2, -93.4),
289            Vec2::new(199.6, 6.6),
290        ];
291
292        test.iter().zip(expected.iter()).for_each(|(t, e)| {
293            assert_approx_eq_point(t.to_point(), e.to_point(), f64::EPSILON * 100.);
294        });
295    }
296
297    #[test]
298    fn area() {
299        let test = Triangle::new(
300            (12123.423, 2382.7834),
301            (7892.729, 238.459),
302            (7820.2, 712.23),
303        );
304        let expected = 1079952.9157407999;
305
306        // initial
307        assert_approx_eq(test.area(), -expected, f64::EPSILON * 100.);
308        // permutate vertex
309        let test = Triangle::new(test.b, test.a, test.c);
310        assert_approx_eq(test.area(), expected, f64::EPSILON * 100.);
311    }
312
313    #[test]
314    fn circumcenter() {
315        let test = Triangle::EQUILATERAL.circumscribed_circle().center;
316        let expected = Point::new(0.5, 0.28867513459481288);
317
318        assert_approx_eq_point(test, expected, f64::EPSILON * 100.);
319    }
320
321    #[test]
322    fn inradius() {
323        let test = Triangle::EQUILATERAL.inscribed_circle().radius;
324        let expected = 0.28867513459481287;
325
326        assert_approx_eq(test, expected, f64::EPSILON * 100.);
327    }
328
329    #[test]
330    fn circumradius() {
331        let test = Triangle::EQUILATERAL;
332        let expected = 0.57735026918962576;
333
334        assert_approx_eq(
335            test.circumscribed_circle().radius,
336            expected,
337            f64::EPSILON * 100.,
338        );
339        // permute vertex
340        let test = Triangle::new(test.b, test.a, test.c);
341        assert_approx_eq(
342            test.circumscribed_circle().radius,
343            -expected,
344            f64::EPSILON * 100.,
345        );
346    }
347
348    #[test]
349    fn inscribed_circle() {
350        let test = Triangle::new((-4., 1.), (-4., -1.), (10., 3.));
351
352        let inscribed = test.inscribed_circle();
353        assert_approx_eq_point(
354            inscribed.center,
355            (-3.0880178529263671, 0.20904207741504303).into(),
356            f64::EPSILON * 100.,
357        );
358        assert_approx_eq(inscribed.radius, 0.91198214707363295, f64::EPSILON * 100.);
359    }
360
361    #[test]
362    fn circumscribed_circle() {
363        let test = Triangle::new((-4., 1.), (-4., -1.), (10., 3.));
364
365        let circumscribed = test.circumscribed_circle();
366        assert_approx_eq_point(
367            circumscribed.center,
368            (3.2857142857142857, 0.).into(),
369            f64::EPSILON * 100.,
370        );
371        assert_approx_eq(
372            circumscribed.radius,
373            7.3540215292764288,
374            f64::EPSILON * 100.,
375        );
376    }
377}
kurbo/triangle.rs

kurbo/
triangle.rs
