Add triangle struct and triangulation template

1 files changed, 6 insertions, 101 deletions

diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs
index e6ca70f..244b0af 100644
--- a/src/math/line_segment.rs
+++ b/src/math/line_segment.rs
@@ -1,4 +1,4 @@
-use super::{Rect, Vec2};
+use super::{Rect, TripletOrientation, Vec2};
 use alga::general::{ClosedDiv, ClosedMul, ClosedSub};
 use nalgebra::{RealField, Scalar};
 use num_traits::Zero;
@@ -50,10 +50,10 @@ impl<T: Scalar + Copy> LineSegment<T> {
          */
 
         // Cache the necessary orientations.
-        let ls1_ls2start_orientation = triplet_orientation(ls1.start, ls1.end, ls2.start);
-        let ls1_ls2end_orientation = triplet_orientation(ls1.start, ls1.end, ls2.end);
-        let ls2_ls1start_orientation = triplet_orientation(ls2.start, ls2.end, ls1.start);
-        let ls2_ls1end_orientation = triplet_orientation(ls2.start, ls2.end, ls1.end);
+        let ls1_ls2start_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.start);
+        let ls1_ls2end_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.end);
+        let ls2_ls1start_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.start);
+        let ls2_ls1end_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.end);
 
         // Check for the first case that wase described (general case).
         if ls1_ls2start_orientation != ls1_ls2end_orientation
@@ -139,7 +139,7 @@ impl<T: Scalar + Copy> LineSegment<T> {
         assert_eq!(
             split_points
                 .iter()
-                .find(|&p| triplet_orientation(self.start, self.end, *p)
+                .find(|&p| super::triplet_orientation(self.start, self.end, *p)
                     != TripletOrientation::Collinear),
             None
         );
@@ -173,76 +173,9 @@ impl<T: Scalar + Copy> LineSegment<T> {
     }
 }
 
-#[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.
-    let angle = match orientation {
-        TripletOrientation::Counterclockwise => T::pi() + (T::pi() - angle),
-        _ => angle,
-    };
-
-    angle
-}
-
 #[cfg(test)]
 mod test {
     use super::*;
-    use std::f64::consts::PI;
 
     #[test]
     fn contains_collinear() {
@@ -256,32 +189,4 @@ mod test {
         assert!(!segment.contains_collinear(Vec2::new(3., 3.)));
         assert!(!segment.contains_collinear(Vec2::new(-1., 0.)));
     }
-
-    #[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
-        );
-    }
 }