From d7d90e8b3615db38d1af238ac9c8193c283ca156 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 00:36:32 +0100 Subject: Add triangle struct and triangulation template --- src/math/triangle.rs | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 161 insertions(+) create mode 100644 src/math/triangle.rs (limited to 'src/math/triangle.rs') diff --git a/src/math/triangle.rs b/src/math/triangle.rs new file mode 100644 index 0000000..53c7560 --- /dev/null +++ b/src/math/triangle.rs @@ -0,0 +1,161 @@ +use super::{LineSegment, Vec2}; +use alga::general::{ClosedMul, ClosedSub}; +use nalgebra::{RealField, Scalar}; +use num_traits::Zero; + +/// Represents a triangle +pub struct Triangle { + /// 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; 3], +} + +impl Triangle { + /// Create a new Triangle as defined by its three corner points + pub fn new(a: Vec2, b: Vec2, c: Vec2) -> 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] } + } + } + } + + /// Create a new Triangle from a three-point slice, instead of the three points one after + /// another. + pub fn from_slice(corners: [Vec2; 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) -> 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 + } +} + +#[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(a: Vec2, b: Vec2, c: Vec2) -> 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(a: Vec2, b: Vec2, c: Vec2) -> 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 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 + ); + } +} -- cgit v1.2.3-70-g09d2