kurbo/

triangle.rs

// Copyright 2024 the Kurbo Authors
// SPDX-License-Identifier: Apache-2.0 OR MIT

//! Triangle shape
use crate::{Circle, PathEl, Point, Rect, Shape, Vec2};

use core::cmp::*;
use core::f64::consts::FRAC_PI_4;
use core::ops::{Add, Sub};

#[cfg(not(feature = "std"))]
use crate::common::FloatFuncs;

/// Triangle
//     A
//     *
//    / \
//   /   \
//  *-----*
//  B     C
#[derive(Clone, Copy, PartialEq, Debug)]
#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Triangle {
    /// vertex a.
    pub a: Point,
    /// vertex b.
    pub b: Point,
    /// vertex c.
    pub c: Point,
}

impl Triangle {
    /// The empty [`Triangle`] at the origin.
    pub const ZERO: Self = Self::from_coords((0., 0.), (0., 0.), (0., 0.));

    /// Equilateral [`Triangle`] with the x-axis unit vector as its base.
    pub const EQUILATERAL: Self = Self::from_coords(
        (
            1.0 / 2.0,
            1.732050807568877293527446341505872367_f64 / 2.0, /* (sqrt 3)/2 */
        ),
        (0.0, 0.0),
        (1.0, 0.0),
    );

    /// A new [`Triangle`] from three vertices ([`Point`]s).
    #[inline(always)]
    pub fn new(a: impl Into<Point>, b: impl Into<Point>, c: impl Into<Point>) -> Self {
        Self {
            a: a.into(),
            b: b.into(),
            c: c.into(),
        }
    }

    /// A new [`Triangle`] from three float vertex coordinates.
    ///
    /// Works as a constant [`Triangle::new`].
    #[inline(always)]
    pub const fn from_coords(a: (f64, f64), b: (f64, f64), c: (f64, f64)) -> Self {
        Self {
            a: Point::new(a.0, a.1),
            b: Point::new(b.0, b.1),
            c: Point::new(c.0, c.1),
        }
    }

    /// The centroid of the [`Triangle`].
    #[inline]
    pub fn centroid(&self) -> Point {
        (1.0 / 3.0 * (self.a.to_vec2() + self.b.to_vec2() + self.c.to_vec2())).to_point()
    }

    /// The offset of each vertex from the centroid.
    #[inline]
    pub fn offsets(&self) -> [Vec2; 3] {
        let centroid = self.centroid().to_vec2();

        [
            (self.a.to_vec2() - centroid),
            (self.b.to_vec2() - centroid),
            (self.c.to_vec2() - centroid),
        ]
    }

    /// The area of the [`Triangle`].
    #[inline]
    pub fn area(&self) -> f64 {
        0.5 * (self.b - self.a).cross(self.c - self.a)
    }

    /// Whether this [`Triangle`] has zero area.
    #[doc(alias = "is_empty")]
    #[inline]
    pub fn is_zero_area(&self) -> bool {
        self.area() == 0.0
    }

    /// The inscribed circle of [`Triangle`].
    ///
    /// This is defined as the greatest [`Circle`] that lies within the [`Triangle`].
    #[doc(alias = "incircle")]
    #[inline]
    pub fn inscribed_circle(&self) -> Circle {
        let ab = self.a.distance(self.b);
        let bc = self.b.distance(self.c);
        let ac = self.a.distance(self.c);

        // [`Vec2::div`] also multiplies by the reciprocal of the argument, but as this reciprocal
        // is reused below to calculate the radius, there's explicitly only one division needed.
        let perimeter_recip = 1. / (ab + bc + ac);
        let incenter = (self.a.to_vec2() * bc + self.b.to_vec2() * ac + self.c.to_vec2() * ab)
            * perimeter_recip;

        Circle::new(incenter.to_point(), 2.0 * self.area() * perimeter_recip)
    }

    /// The circumscribed circle of [`Triangle`].
    ///
    /// This is defined as the smallest [`Circle`] which intercepts each vertex of the [`Triangle`].
    #[doc(alias = "circumcircle")]
    #[inline]
    pub fn circumscribed_circle(&self) -> Circle {
        let b = self.b - self.a;
        let c = self.c - self.a;
        let b_len2 = b.hypot2();
        let c_len2 = c.hypot2();
        let d_recip = 0.5 / b.cross(c);

        let x = (c.y * b_len2 - b.y * c_len2) * d_recip;
        let y = (b.x * c_len2 - c.x * b_len2) * d_recip;
        let r = (b_len2 * c_len2).sqrt() * (c - b).hypot() * d_recip;

        Circle::new(self.a + Vec2::new(x, y), r)
    }

    /// Expand the triangle by a constant amount (`scalar`) in all directions.
    #[doc(alias = "offset")]
    pub fn inflate(&self, scalar: f64) -> Self {
        let centroid = self.centroid();

        Self::new(
            centroid + (0.0, scalar),
            centroid + scalar * Vec2::from_angle(5.0 * FRAC_PI_4),
            centroid + scalar * Vec2::from_angle(7.0 * FRAC_PI_4),
        )
    }

    /// Is this [`Triangle`] [finite]?
    ///
    /// [finite]: f64::is_finite
    #[inline]
    pub const fn is_finite(&self) -> bool {
        self.a.is_finite() && self.b.is_finite() && self.c.is_finite()
    }

    /// Is this [`Triangle`] [NaN]?
    ///
    /// [NaN]: f64::is_nan
    #[inline]
    pub const fn is_nan(&self) -> bool {
        self.a.is_nan() || self.b.is_nan() || self.c.is_nan()
    }
}

impl From<(Point, Point, Point)> for Triangle {
    fn from(points: (Point, Point, Point)) -> Triangle {
        Triangle::new(points.0, points.1, points.2)
    }
}

impl Add<Vec2> for Triangle {
    type Output = Triangle;

    #[inline]
    fn add(self, v: Vec2) -> Triangle {
        Triangle::new(self.a + v, self.b + v, self.c + v)
    }
}

impl Sub<Vec2> for Triangle {
    type Output = Triangle;

    #[inline]
    fn sub(self, v: Vec2) -> Triangle {
        Triangle::new(self.a - v, self.b - v, self.c - v)
    }
}

#[doc(hidden)]
pub struct TrianglePathIter {
    triangle: Triangle,
    ix: usize,
}

impl Shape for Triangle {
    type PathElementsIter<'iter> = TrianglePathIter;

    fn path_elements(&self, _tolerance: f64) -> TrianglePathIter {
        TrianglePathIter {
            triangle: *self,
            ix: 0,
        }
    }

    #[inline]
    fn area(&self) -> f64 {
        Triangle::area(self)
    }

    #[inline]
    fn perimeter(&self, _accuracy: f64) -> f64 {
        self.a.distance(self.b) + self.b.distance(self.c) + self.c.distance(self.a)
    }

    #[inline]
    fn winding(&self, pt: Point) -> i32 {
        let s0 = (self.b - self.a).cross(pt - self.a).signum();
        let s1 = (self.c - self.b).cross(pt - self.b).signum();
        let s2 = (self.a - self.c).cross(pt - self.c).signum();

        if s0 == s1 && s1 == s2 { s0 as i32 } else { 0 }
    }

    #[inline]
    fn bounding_box(&self) -> Rect {
        Rect::new(
            self.a.x.min(self.b.x.min(self.c.x)),
            self.a.y.min(self.b.y.min(self.c.y)),
            self.a.x.max(self.b.x.max(self.c.x)),
            self.a.y.max(self.b.y.max(self.c.y)),
        )
    }
}

// Note: vertices a, b and c are not guaranteed to be in order as described in the struct comments
//       (i.e. as "vertex a is topmost, vertex b is leftmost, and vertex c is rightmost")
impl Iterator for TrianglePathIter {
    type Item = PathEl;

    fn next(&mut self) -> Option<PathEl> {
        self.ix += 1;
        match self.ix {
            1 => Some(PathEl::MoveTo(self.triangle.a)),
            2 => Some(PathEl::LineTo(self.triangle.b)),
            3 => Some(PathEl::LineTo(self.triangle.c)),
            4 => Some(PathEl::ClosePath),
            _ => None,
        }
    }
}

// TODO: better and more tests
#[cfg(test)]
mod tests {
    use crate::{Point, Triangle, Vec2};

    fn assert_approx_eq(x: f64, y: f64, max_relative_error: f64) {
        assert!(
            (x - y).abs() <= f64::max(x.abs(), y.abs()) * max_relative_error,
            "{x} != {y}"
        );
    }

    fn assert_approx_eq_point(x: Point, y: Point, max_relative_error: f64) {
        assert_approx_eq(x.x, y.x, max_relative_error);
        assert_approx_eq(x.y, y.y, max_relative_error);
    }

    #[test]
    fn centroid() {
        let test = Triangle::from_coords((-90.02, 3.5), (7.2, -9.3), (8.0, 9.1)).centroid();
        let expected = Point::new(-24.94, 1.1);

        assert_approx_eq_point(test, expected, f64::EPSILON * 100.);
    }

    #[test]
    fn offsets() {
        let test = Triangle::from_coords((-20.0, 180.2), (1.2, 0.0), (290.0, 100.0)).offsets();
        let expected = [
            Vec2::new(-110.4, 86.8),
            Vec2::new(-89.2, -93.4),
            Vec2::new(199.6, 6.6),
        ];

        test.iter().zip(expected.iter()).for_each(|(t, e)| {
            assert_approx_eq_point(t.to_point(), e.to_point(), f64::EPSILON * 100.);
        });
    }

    #[test]
    fn area() {
        let test = Triangle::new(
            (12123.423, 2382.7834),
            (7892.729, 238.459),
            (7820.2, 712.23),
        );
        let expected = 1079952.9157407999;

        // initial
        assert_approx_eq(test.area(), -expected, f64::EPSILON * 100.);
        // permutate vertex
        let test = Triangle::new(test.b, test.a, test.c);
        assert_approx_eq(test.area(), expected, f64::EPSILON * 100.);
    }

    #[test]
    fn circumcenter() {
        let test = Triangle::EQUILATERAL.circumscribed_circle().center;
        let expected = Point::new(0.5, 0.28867513459481288);

        assert_approx_eq_point(test, expected, f64::EPSILON * 100.);
    }

    #[test]
    fn inradius() {
        let test = Triangle::EQUILATERAL.inscribed_circle().radius;
        let expected = 0.28867513459481287;

        assert_approx_eq(test, expected, f64::EPSILON * 100.);
    }

    #[test]
    fn circumradius() {
        let test = Triangle::EQUILATERAL;
        let expected = 0.57735026918962576;

        assert_approx_eq(
            test.circumscribed_circle().radius,
            expected,
            f64::EPSILON * 100.,
        );
        // permute vertex
        let test = Triangle::new(test.b, test.a, test.c);
        assert_approx_eq(
            test.circumscribed_circle().radius,
            -expected,
            f64::EPSILON * 100.,
        );
    }

    #[test]
    fn inscribed_circle() {
        let test = Triangle::new((-4., 1.), (-4., -1.), (10., 3.));

        let inscribed = test.inscribed_circle();
        assert_approx_eq_point(
            inscribed.center,
            (-3.0880178529263671, 0.20904207741504303).into(),
            f64::EPSILON * 100.,
        );
        assert_approx_eq(inscribed.radius, 0.91198214707363295, f64::EPSILON * 100.);
    }

    #[test]
    fn circumscribed_circle() {
        let test = Triangle::new((-4., 1.), (-4., -1.), (10., 3.));

        let circumscribed = test.circumscribed_circle();
        assert_approx_eq_point(
            circumscribed.center,
            (3.2857142857142857, 0.).into(),
            f64::EPSILON * 100.,
        );
        assert_approx_eq(
            circumscribed.radius,
            7.3540215292764288,
            f64::EPSILON * 100.,
        );
    }
}