aboutsummaryrefslogtreecommitdiff
path: root/src/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/math')
-rw-r--r--src/math/line_segment.rs107
-rw-r--r--src/math/mod.rs4
-rw-r--r--src/math/triangle.rs161
-rw-r--r--src/math/triangulate.rs12
4 files changed, 183 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
- );
- }
}
diff --git a/src/math/mod.rs b/src/math/mod.rs
index 0b591d7..07bc36b 100644
--- a/src/math/mod.rs
+++ b/src/math/mod.rs
@@ -2,12 +2,16 @@ pub mod line_segment;
pub mod polygon;
pub mod polygon_graph;
pub mod rect;
+pub mod triangle;
+pub mod triangulate;
pub mod vec2;
pub use self::line_segment::*;
pub use self::polygon::*;
pub use self::polygon_graph::*;
pub use self::rect::*;
+pub use self::triangle::*;
+pub use self::triangulate::*;
pub use self::vec2::*;
use std::cmp::Ordering;
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<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] }
+ }
+ }
+ }
+
+ /// 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
+ }
+}
+
+#[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 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
+ );
+ }
+}
diff --git a/src/math/triangulate.rs b/src/math/triangulate.rs
new file mode 100644
index 0000000..8ef92f1
--- /dev/null
+++ b/src/math/triangulate.rs
@@ -0,0 +1,12 @@
+//! Module for turning a polygon into a number of non-overlapping triangles.
+
+use super::{Polygon, Triangle};
+use nalgebra::Scalar;
+
+/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)
+/// to find an explanation of what exactly is happening.
+/// Currently only handles simple polygons, but once the polygon struct supports holes must be
+/// extended to also support those.
+pub fn triangulate<T: Scalar + Copy>(_polygon: &Polygon<T>) -> Vec<Triangle<T>> {
+ unimplemented!()
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.1) at 2025-12-06 10:31:42 +0000