aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/math/line_segment.rs116
-rw-r--r--src/math/mod.rs31
-rw-r--r--src/math/polygon.rs112
3 files changed, 257 insertions, 2 deletions
diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs
new file mode 100644
index 0000000..d7bcdb1
--- /dev/null
+++ b/src/math/line_segment.rs
@@ -0,0 +1,116 @@
+use super::Vec2;
+use alga::general::{ClosedMul, ClosedSub};
+use nalgebra::Scalar;
+use num_traits::Zero;
+
+pub struct LineSegment<T: Scalar + Copy> {
+ pub start: Vec2<T>,
+ pub end: Vec2<T>,
+}
+
+impl<T: Scalar + Copy> LineSegment<T> {
+ pub fn new(start: Vec2<T>, end: Vec2<T>) -> Self {
+ Self { start, end }
+ }
+
+ /* Helper function to check if this line contains a point. This function is very efficient, but
+ * must only be used for points that are collinear with the segment. This is checked only by
+ * assertion, so make sure that everything is ok in release mode.
+ */
+ pub(crate) fn contains_collinear(&self, point: Vec2<T>) -> bool
+ where
+ T: PartialOrd,
+ {
+ point.x <= super::partial_max(self.start.x, self.end.x)
+ && point.x >= super::partial_max(self.start.x, self.end.x)
+ && point.y <= super::partial_min(self.start.y, self.end.y)
+ && point.y >= super::partial_min(self.start.y, self.end.y)
+ }
+
+ /// Checks if two segments intersect. This is much more efficient than trying to find the exact
+ /// point of intersection, so it should be used if it is not strictly necessary to know it.
+ pub fn intersect(ls1: &LineSegment<T>, ls2: &LineSegment<T>) -> bool
+ where
+ T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
+ {
+ /* This algorithm works by checking the triplet orientation of the first lines points with the
+ * first point of the second line. After that it does the same for the second point of the
+ * second line. If the orientations are different, that must mean the second line starts
+ * "before" the first line and ends "after" it. It does the same, but with the roles of first
+ * and second line reversed. If both of these conditions are met, it follows that the lines
+ * must have crossed.
+ *
+ * Edge case: If an orientation comes out as collinear, the point of the other line that was
+ * checked may be on the other line or after/before it (if you extend the segment). If it is on
+ * the other line, this also means, the lines cross, since one line "stands" on the other.
+ * If however none of the collinear cases are like this, the lines cannot touch, because line
+ * segment a point was collinear with was not long enough.
+ */
+
+ // 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);
+
+ // Check for the first case that wase described (general case).
+ if ls1_ls2start_orientation != ls1_ls2end_orientation
+ && ls2_ls1start_orientation != ls2_ls1end_orientation
+ {
+ return true;
+ }
+
+ // Check if the start of ls2 lies on ls1
+ if ls1_ls2start_orientation == TripletOrientation::Collinear
+ && ls1.contains_collinear(ls2.start)
+ {
+ return true;
+ }
+ // Check if the end of ls2 lies on ls1
+ if ls1_ls2end_orientation == TripletOrientation::Collinear
+ && ls1.contains_collinear(ls2.end)
+ {
+ return true;
+ }
+
+ // Check if the start of ls1 lies on ls2
+ if ls2_ls1start_orientation == TripletOrientation::Collinear
+ && ls2.contains_collinear(ls1.start)
+ {
+ return true;
+ }
+ // Check if the end of ls1 lies on ls2
+ if ls2_ls1end_orientation == TripletOrientation::Collinear
+ && ls2.contains_collinear(ls1.end)
+ {
+ 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::Clockwise,
+ q if q < T::zero() => TripletOrientation::Counterclockwise,
+ _ => TripletOrientation::Collinear,
+ }
+}
diff --git a/src/math/mod.rs b/src/math/mod.rs
index 07d518e..bfc2ab4 100644
--- a/src/math/mod.rs
+++ b/src/math/mod.rs
@@ -1,9 +1,15 @@
+pub mod line_segment;
+pub mod polygon;
pub mod rect;
-pub use self::rect::*;
-
pub mod vec2;
+
+pub use self::line_segment::*;
+pub use self::polygon::*;
+pub use self::rect::*;
pub use self::vec2::*;
+use std::cmp::Ordering;
+
/// Round a floating point number to the nearest step given by the step argument. For instance, if
/// the step is 0.5, then all numbers from 0.0 to 0.24999... will be 0., while all numbers from
/// 0.25 to 0.74999... will be 0.5 and so on.
@@ -21,3 +27,24 @@ pub fn round(num: f32, step: f32) -> f32 {
upper_bound
}
}
+
+/// Works like `std::cmp::max`, however also allows partial comparisons. It is specifically
+/// designed so functions that should be able to use f32 and f64 work, eventhough these do not
+/// implement Ord. The downside of this function however is, that its behaviour is undefined when
+/// `f32::NaN` for instance were to be passed.
+fn partial_max<T>(a: T, b: T) -> T
+where
+ T: PartialOrd,
+{
+ match a.partial_cmp(&b) {
+ Some(Ordering::Greater) => a,
+ _ => b,
+ }
+}
+/// Like `partial_max`, but for minimum values. Comes with the same downside, too.
+fn partial_min<T>(a: T, b: T) -> T
+where
+ T: PartialOrd,
+{
+ partial_max(b, a)
+}
diff --git a/src/math/polygon.rs b/src/math/polygon.rs
new file mode 100644
index 0000000..e70cd2c
--- /dev/null
+++ b/src/math/polygon.rs
@@ -0,0 +1,112 @@
+use super::{LineSegment, TripletOrientation, Vec2};
+use alga::general::{ClosedMul, ClosedSub};
+use nalgebra::Scalar;
+use num_traits::Zero;
+
+pub struct Polygon<T: Scalar + Copy> {
+ pub corners: Vec<Vec2<T>>,
+}
+
+impl<T: Scalar + Copy> Polygon<T> {
+ pub fn new(corners: Vec<Vec2<T>>) -> Self {
+ Self { corners }
+ }
+
+ /// Check whether a point is inside a polygon or not. If a point lies on an edge, it also
+ /// counts as inside the polygon.
+ pub fn contains(&self, point: Vec2<T>) -> bool
+ where
+ T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
+ {
+ // Must be at least a triangle to contain anything
+ if self.corners.len() < 3 {
+ return false;
+ }
+
+ /* What's happening here:
+ *
+ * This algorithm creates a horizontal line for the point that should be checked. It goes
+ * to infinity (since infinite lines are not possible, it just goes to the maximum x value
+ * of all corner points). Then, the times the line crosses a polygon edge is counted. If
+ * the times it hit a polygon edge is uneven, it must have been inside, otherwise outside.
+ *
+ * There is an edge case however (pun not intended); When the line from the point is collinear
+ * to a polygon edge. it might hit this edge once and no other (it's at the top y or bottom y
+ * of the polygon), but may still not be inside the polygon. In this case, it's checked
+ * whether the point is in between the corner points of this polygon edge or not. If it is
+ * in between, it is still inside the polygon, otherwise outside.
+ */
+
+ // Get the maximum x for the horizontal lines for "Infinity".
+ let mut max_x = self.corners[0].x;
+ for corner in self.corners.iter().skip(1) {
+ max_x = super::partial_max(corner.x, max_x);
+ }
+ println!("Max x is {:?}", max_x);
+ // The horizontally "infinite" point of the test point.
+ let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y));
+
+ // Check for intersection for all the polygon edges.
+ let mut num_intersects = 0;
+ for i in 0..self.corners.len() {
+ // Wrap around for the edge that returns to the start.
+ let j = (i + 1) % self.corners.len();
+ let current_edge = LineSegment::new(self.corners[i], self.corners[j]);
+
+ if LineSegment::intersect(&current_edge, &line_to_infinity) {
+ /* Check for the edge case, where the point might lie right on an edge of the
+ * polygon.
+ */
+ if super::triplet_orientation(current_edge.start, current_edge.end, point)
+ == TripletOrientation::Collinear
+ {
+ // The point is right on an edge
+ if current_edge.contains_collinear(point) {
+ return true;
+ }
+ } else {
+ num_intersects += 1;
+ }
+ }
+ }
+
+ num_intersects % 2 == 1
+ }
+
+ /// Join this polygon with another, ensuring the area of the two stays the same, minus the
+ /// overlap.
+ ///
+ /// # Panics
+ /// If the two polygons do not intersect, it is impossible to unite them into a single polygon,
+ /// in which case this function is bound to fail.
+ // TODO: Create a function that only tries to join the polygons.
+ pub fn unite(&mut self, mut _other: Polygon<T>) {
+ unimplemented!()
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+
+ #[test]
+ fn polygon_contains() {
+ let polygon = Polygon::new(vec![
+ Vec2::new(0., 0.),
+ Vec2::new(-1., 1.),
+ Vec2::new(0., 2.),
+ Vec2::new(1., 3.),
+ Vec2::new(3., 1.5),
+ Vec2::new(2., 0.),
+ Vec2::new(1., 1.),
+ ]);
+
+ assert!(!polygon.contains(Vec2::new(1., -2.)));
+ assert!(!polygon.contains(Vec2::new(-1., 0.5)));
+ assert!(polygon.contains(Vec2::new(0., 0.5)));
+ assert!(polygon.contains(Vec2::new(0.5, 1.)));
+ assert!(polygon.contains(Vec2::new(0.5, 1.5)));
+ assert!(!polygon.contains(Vec2::new(-2., 1.9)));
+ assert!(!polygon.contains(Vec2::new(0., 3.)));
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.1) at 2025-12-06 08:41:35 +0000