path: root/src/math/triangle.rs

//! Triangles. Nothing more, nothing less.

use super::{LineSegment, Vec2};
use alga::general::{ClosedMul, ClosedSub};
use nalgebra::{RealField, Scalar};
use num_traits::Zero;

/// Represents a triangle
#[derive(Debug)]
pub struct Triangle<T: Scalar + Copy> {
    /// The three corners of the triangle. Internally, it is made sure that the corners are always
    /// ordered in a counterclockwise manner, to make operations like contains simpler.
    corners: [Vec2<T>; 3],
}

impl<T: Scalar + Copy> Triangle<T> {
    /// Create a new Triangle as defined by its three corner points
    pub fn new(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> Self
    where
        T: ClosedSub + ClosedMul + PartialOrd + Zero,
    {
        // Make sure the three points are in counterclockwise order.
        match triplet_orientation(a, b, c) {
            TripletOrientation::Counterclockwise => Self { corners: [a, b, c] },
            TripletOrientation::Clockwise => Self { corners: [a, c, b] },
            TripletOrientation::Collinear => {
                warn!(
                    "Creating triangle without any area: [{:?}, {:?}, {:?}]",
                    a, b, c
                );
                Self { corners: [a, b, c] }
            }
        }
    }

    /// Get the corners immutably
    pub fn corners(&self) -> &[Vec2<T>; 3] {
        &self.corners
    }

    /// Create a new Triangle from a three-point slice, instead of the three points one after
    /// another.
    pub fn from_slice(corners: [Vec2<T>; 3]) -> Self
    where
        T: ClosedSub + ClosedMul + PartialOrd + Zero,
    {
        Self::new(corners[0], corners[1], corners[2])
    }

    /// Check if the triangle contains a given point. If the point is right on an edge, it still
    /// counts as inside it.
    pub fn contains_point(&self, point: Vec2<T>) -> bool
    where
        T: ClosedSub + ClosedMul + PartialOrd + Zero,
    {
        // Since the points are ordered counterclockwise, check if the point is to the left of all
        // edges (or on an edge) from one point to the next. When the point is to the left of all
        // edges, it must be inside the triangle.
        for i in 0..3 {
            if triplet_orientation(self.corners[i], self.corners[(i + 1) % 3], point)
                == TripletOrientation::Clockwise
            {
                return false;
            }
        }

        true
    }
}

/// Convert a three-point-slice into a triangle
impl<T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero> From<[Vec2<T>; 3]>
    for Triangle<T>
{
    fn from(corners: [Vec2<T>; 3]) -> Self {
        Self::new(corners[0], corners[1], corners[2])
    }
}
/// Convert a triangle into a three-point-slice. The corners are in counterclockwise order.
impl<T: Scalar + Copy> Into<[Vec2<T>; 3]> for Triangle<T> {
    fn into(self) -> [Vec2<T>; 3] {
        self.corners
    }
}

impl<T: Scalar + Copy + PartialEq> PartialEq for Triangle<T> {
    fn eq(&self, other: &Self) -> bool {
        // The indexes of the elements are not important, so try all shifting options.
        for shift in 0..=2 {
            if self
                .corners
                .iter()
                .enumerate()
                .find(|(i, &c)| c != other.corners[(i + shift) % 3])
                .is_none()
            {
                return true;
            }
        }

        false
    }
}

#[derive(PartialEq, Eq)]
pub(crate) enum TripletOrientation {
    Clockwise,
    Counterclockwise,
    Collinear,
}

/// Helper function to determine which direction one would turn to traverse from the first point
/// over the second to the third point. The third option is collinear, in which case the three points
/// are on the same line.
pub(crate) fn triplet_orientation<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> TripletOrientation
where
    T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
{
    /* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than
     * that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If
     * they are the same it follows that the three points are collinear.
     */
    match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) {
        q if q > T::zero() => TripletOrientation::Counterclockwise,
        q if q < T::zero() => TripletOrientation::Clockwise,
        _ => TripletOrientation::Collinear,
    }
}

/// Calculate the angle between three points. Guaranteed to have 0 <= angle < 2Pi. The angle is
/// calculated as the angle between a line from a to b and then from b to c, increasing
/// counterclockwise.
///
/// # Panics
/// If the length from a to b or the length from b to c is zero.
pub(crate) fn triplet_angle<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> T
where
    T: Scalar + Copy + ClosedSub + RealField + Zero,
{
    assert!(a != b);
    assert!(b != c);

    // Handle the extreme 0 and 180 degree cases
    let orientation = triplet_orientation(a, b, c);
    if orientation == TripletOrientation::Collinear {
        if LineSegment::new(a, b).contains_collinear(c)
            || LineSegment::new(b, c).contains_collinear(a)
        {
            return T::zero();
        } else {
            return T::pi();
        }
    }

    // Calculate the vectors out of the points
    let ba = a - b;
    let bc = c - b;

    // Calculate the angle between 0 and Pi.
    let angle = ((ba * bc) / (ba.length() * bc.length())).acos();

    // Make angle into a full circle angle by looking at the orientation of the triplet.
    match orientation {
        TripletOrientation::Counterclockwise => T::pi() + (T::pi() - angle),
        _ => angle,
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use std::f64::consts::PI;

    #[test]
    fn new() {
        let a = Vec2::new(0., 0.);
        let b = Vec2::new(0., 1.);
        let c = Vec2::new(1., 1.);

        // Create with counterclockwise order.
        let triangle = Triangle::new(a, b, c);
        assert_eq!(triangle.corners(), &[a, b, c]);

        // Create with clockwise order.
        let triangle = Triangle::new(a, c, b);
        assert_eq!(triangle.corners(), &[a, b, c]);

        // Create with different starting corner
        let triangle = Triangle::from([b, c, a]);
        assert_eq!(triangle.corners(), &[b, c, a]);

        // Create with collinear corners
        let triangle = Triangle::new(c, c, b);
        assert_eq!(triangle.corners(), &[c, c, b]);
    }

    #[test]
    fn contains_point() {
        let a = Vec2::new(0., 0.);
        let b = Vec2::new(-1., -1.);
        let c = Vec2::new(-2., 0.);

        let triangle = Triangle::new(a, b, c);

        assert!(triangle.contains_point(b));
        assert!(triangle.contains_point(Vec2::new(-0.5, -0.5)));
        assert!(triangle.contains_point(Vec2::new(-1., -0.5)));
        assert!(!triangle.contains_point(Vec2::new(-2., -2.)));
    }

    #[test]
    fn equality() {
        let a = Vec2::new(0., 0.);
        let b = Vec2::new(-1., -1.);
        let c = Vec2::new(-2., 0.);
        let d = Vec2::new(-3., 0.);

        let cmp = Triangle::new(a, b, c);

        assert_eq!(Triangle::new(a, b, c), cmp);
        assert_eq!(Triangle::new(c, b, a), cmp);
        assert_eq!(Triangle::new(b, a, c), cmp);
        assert!(Triangle::new(a, b, d) != cmp);
    }

    #[test]
    fn triplet_angle() {
        assert_eq!(
            super::triplet_angle(Vec2::new(0., 0.), Vec2::new(0., -1.), Vec2::new(-1., -1.)),
            1.5 * PI
        );
        assert_eq!(
            super::triplet_angle(Vec2::new(2., 2.), Vec2::new(0., 0.), Vec2::new(-1., -1.)),
            PI
        );
        assert_eq!(
            super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(6., 2.)),
            0.
        );
        assert_eq!(
            super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(-6., -2.)),
            PI
        );
        assert_eq!(
            super::triplet_angle(Vec2::new(0., 1.), Vec2::new(0., 2.), Vec2::new(-3., 2.)),
            0.5 * PI
        );
        assert_eq!(
            super::triplet_angle(Vec2::new(3., 1.), Vec2::new(2., 2.), Vec2::new(0., 2.)),
            0.75 * PI
        );
    }
}