Merge branch 'triangulation' into polygon-rooms

1 files changed, 251 insertions, 0 deletions

diff --git a/src/math/triangle.rs b/src/math/triangle.rs
new file mode 100644
index 0000000..35bdcec
--- /dev/null
+++ b/src/math/triangle.rs
@@ -0,0 +1,251 @@
+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
+        );
+    }
+}