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/line_segment.rs | 107 +++-------------------------------------------- 1 file changed, 6 insertions(+), 101 deletions(-) (limited to 'src/math/line_segment.rs') 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 LineSegment { */ // 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 LineSegment { 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 LineSegment { } } -#[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 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 - ); - } } -- cgit v1.2.3-70-g09d2 From abf55d8d46fc7d5cfccc9f778da6fca10b33d0cd Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 20:55:47 +0100 Subject: Move containment of points/ lines into trait --- src/gui/tool_sidebar.rs | 4 +- src/math/line_segment.rs | 6 +-- src/math/mod.rs | 10 +++++ src/math/polygon/mod.rs | 53 ++++++++++++---------- src/math/rect.rs | 112 +++++++++++++++++++++++----------------------- src/tool/deletion_tool.rs | 6 +-- 6 files changed, 105 insertions(+), 86 deletions(-) (limited to 'src/math/line_segment.rs') diff --git a/src/gui/tool_sidebar.rs b/src/gui/tool_sidebar.rs index 46b53ea..7674c47 100644 --- a/src/gui/tool_sidebar.rs +++ b/src/gui/tool_sidebar.rs @@ -1,4 +1,4 @@ -use crate::math::{Rect, Vec2}; +use crate::math::{Rect, Surface, Vec2}; use crate::tool::ToolType; use crate::Editor; use raylib::core::texture::Texture2D; @@ -28,7 +28,7 @@ impl ToolSidebar { /// Check if the mouse is currently being captured by this GUI-element. In that case, /// everything else that might want to access the mouse will be blocked. pub fn mouse_captured(screen_height: u16, mouse_pos: Vec2) -> bool { - Self::panel_rect(screen_height).contains(mouse_pos) + Self::panel_rect(screen_height).contains_point(&mouse_pos) } pub fn draw(&self, screen_height: u16, rld: &mut impl RaylibDrawGui, editor: &mut Editor) { diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 244b0af..94f58b2 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -1,4 +1,4 @@ -use super::{Rect, TripletOrientation, Vec2}; +use super::{Rect, Surface, TripletOrientation, Vec2}; use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; use nalgebra::{RealField, Scalar}; use num_traits::Zero; @@ -118,8 +118,8 @@ impl LineSegment { * the segments. We know it's on the lines, so checking with the lines bounding box is * faster than checking where on the line exactly it would be. */ - if Rect::bounding_rect(line_a.start, line_a.end).contains(out) - && Rect::bounding_rect(line_b.start, line_b.end).contains(out) + if Rect::bounding_rect(line_a.start, line_a.end).contains_point(&out) + && Rect::bounding_rect(line_b.start, line_b.end).contains_point(&out) { Some(out) } else { diff --git a/src/math/mod.rs b/src/math/mod.rs index e72a7a4..6f83c98 100644 --- a/src/math/mod.rs +++ b/src/math/mod.rs @@ -10,8 +10,18 @@ pub use self::rect::*; pub use self::triangle::*; pub use self::vec2::*; +use nalgebra::Scalar; use std::cmp::Ordering; +/// Trait that describes an area in the vector space on the field of T +pub trait Surface { + /// Checks if a point lies on this surface. + fn contains_point(&self, point: &Vec2) -> bool; + + /// Checks if a line segment is entirely contained by this surface. + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool; +} + /// 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. diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index 4530857..d351ec7 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -6,7 +6,7 @@ pub mod triangulate; pub use polygon_graph::*; pub use triangulate::*; -use super::Vec2; +use super::{LineSegment, Surface, Vec2}; use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; use num_traits::Zero; use std::ops::Neg; @@ -24,10 +24,27 @@ impl Polygon { /// 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_point(&self, p: Vec2) -> bool + + /// Join this polygon with another, ensuring the area of the two stays the same, but the + /// overlap is not doubled, but instead joined into one. + /// Returns the Polygons themselves, if there is no overlap + pub fn unite(self, other: Polygon) -> Vec> where - T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, + T: RealField, { + let mut graph = PolygonGraph::from_polygon(&self); + graph.add_all(&other); + + // TODO: Make bounding box support multiple polygons + vec![graph.bounding_polygon()] + } +} + +impl< + T: Scalar + Copy + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd + Zero, + > Surface for Polygon +{ + fn contains_point(&self, p: &Vec2) -> bool { let n = self.corners.len(); let a = self.corners[n - 1]; @@ -102,18 +119,8 @@ impl Polygon { (depth & 1) == 1 } - /// Join this polygon with another, ensuring the area of the two stays the same, but the - /// overlap is not doubled, but instead joined into one. - /// Returns the Polygons themselves, if there is no overlap - pub fn unite(self, other: Polygon) -> Vec> - where - T: RealField, - { - let mut graph = PolygonGraph::from_polygon(&self); - graph.add_all(&other); - - // TODO: Make bounding box support multiple polygons - vec![graph.bounding_polygon()] + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool { + unimplemented!() } } @@ -133,14 +140,14 @@ mod test { Vec2::new(1., 1.), ]); - assert!(!polygon.contains_point(Vec2::new(1., -2.))); - assert!(!polygon.contains_point(Vec2::new(-1., 0.5))); - assert!(polygon.contains_point(Vec2::new(0., 0.5))); - assert!(polygon.contains_point(Vec2::new(0.5, 1.))); - assert!(polygon.contains_point(Vec2::new(0.5, 1.5))); - assert!(!polygon.contains_point(Vec2::new(-2., 1.9))); - assert!(!polygon.contains_point(Vec2::new(0., 3.))); - assert!(polygon.contains_point(Vec2::new(1., 3.))); + assert!(!polygon.contains_point(&Vec2::new(1., -2.))); + assert!(!polygon.contains_point(&Vec2::new(-1., 0.5))); + assert!(polygon.contains_point(&Vec2::new(0., 0.5))); + assert!(polygon.contains_point(&Vec2::new(0.5, 1.))); + assert!(polygon.contains_point(&Vec2::new(0.5, 1.5))); + assert!(!polygon.contains_point(&Vec2::new(-2., 1.9))); + assert!(!polygon.contains_point(&Vec2::new(0., 3.))); + assert!(polygon.contains_point(&Vec2::new(1., 3.))); } #[test] diff --git a/src/math/rect.rs b/src/math/rect.rs index 6988b2c..876e728 100644 --- a/src/math/rect.rs +++ b/src/math/rect.rs @@ -1,6 +1,6 @@ -use super::Vec2; +use super::{LineSegment, Surface, Vec2}; //use alga::general::{Additive, Identity}; -use nalgebra::{RealField, Scalar}; +use nalgebra::{ClosedAdd, RealField, Scalar}; use num_traits::identities::Zero; use serde::{Deserialize, Serialize}; use std::ops::{Add, AddAssign, Sub}; @@ -18,48 +18,6 @@ pub struct Rect { pub h: T, } -// This is sad, but also sadly necessary :/ -impl + Scalar + Copy> Into for Rect { - fn into(self) -> raylib::ffi::Rectangle { - raylib::ffi::Rectangle { - x: self.x.into(), - y: self.y.into(), - width: self.w.into(), - height: self.h.into(), - } - } -} -impl + Scalar + Copy> From for Rect { - fn from(r: raylib::ffi::Rectangle) -> Self { - Self { - x: T::from(r.x), - y: T::from(r.y), - w: T::from(r.width), - h: T::from(r.height), - } - } -} -impl + Scalar + Copy> Into for Rect { - fn into(self) -> raylib::math::Rectangle { - raylib::math::Rectangle { - x: self.x.into(), - y: self.y.into(), - width: self.w.into(), - height: self.h.into(), - } - } -} -impl + Scalar + Copy> From for Rect { - fn from(r: raylib::math::Rectangle) -> Self { - Self { - x: T::from(r.x), - y: T::from(r.y), - w: T::from(r.width), - h: T::from(r.height), - } - } -} - impl Rect { pub fn new(x: T, y: T, w: T, h: T) -> Self { Self { x, y, w, h } @@ -105,17 +63,6 @@ impl Rect { || this.y + this.h < other.y) } - /// Check if the point is inside this Rect and return true if so. - pub fn contains(&self, point: Vec2) -> bool - where - T: PartialOrd + Add, - { - point.x >= self.x - && point.x <= self.x + self.w - && point.y >= self.y - && point.y <= self.y + self.h - } - /// Returns true if the entire rect is contained inside this rectangle. pub fn contains_rect(&self, rect: Rect) -> bool where @@ -181,6 +128,61 @@ impl Rect { } } +impl Surface for Rect { + fn contains_point(&self, point: &Vec2) -> bool { + point.x >= self.x + && point.x <= self.x + self.w + && point.y >= self.y + && point.y <= self.y + self.h + } + + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool { + self.contains_point(&line_segment.start) && self.contains_point(&line_segment.end) + } +} + +// This is sad, but also sadly necessary :/ +impl + Scalar + Copy> Into for Rect { + fn into(self) -> raylib::ffi::Rectangle { + raylib::ffi::Rectangle { + x: self.x.into(), + y: self.y.into(), + width: self.w.into(), + height: self.h.into(), + } + } +} +impl + Scalar + Copy> From for Rect { + fn from(r: raylib::ffi::Rectangle) -> Self { + Self { + x: T::from(r.x), + y: T::from(r.y), + w: T::from(r.width), + h: T::from(r.height), + } + } +} +impl + Scalar + Copy> Into for Rect { + fn into(self) -> raylib::math::Rectangle { + raylib::math::Rectangle { + x: self.x.into(), + y: self.y.into(), + width: self.w.into(), + height: self.h.into(), + } + } +} +impl + Scalar + Copy> From for Rect { + fn from(r: raylib::math::Rectangle) -> Self { + Self { + x: T::from(r.x), + y: T::from(r.y), + w: T::from(r.width), + h: T::from(r.height), + } + } +} + #[cfg(test)] mod test { use super::*; diff --git a/src/tool/deletion_tool.rs b/src/tool/deletion_tool.rs index c313574..5031f5d 100644 --- a/src/tool/deletion_tool.rs +++ b/src/tool/deletion_tool.rs @@ -2,7 +2,7 @@ use super::Tool; use crate::button::Button; use crate::config::{DeletionToolKeybindings, ToolKeybindings}; use crate::map_data::MapData; -use crate::math::{Rect, Vec2}; +use crate::math::{Rect, Surface, Vec2}; use crate::transform::Transform; use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle}; use raylib::ffi::Color; @@ -28,10 +28,10 @@ impl DeletionTool { .retain(|&room| !rect.contains_rect(room)); map_data .walls_mut() - .retain(|&(pos1, pos2)| !rect.contains(pos1) || !rect.contains(pos2)); + .retain(|&(pos1, pos2)| !rect.contains_point(&pos1) || !rect.contains_point(&pos2)); map_data .icons_mut() - .retain(|icon| !rect.contains(icon.position)); + .retain(|icon| !rect.contains_point(&icon.position)); } } -- cgit v1.2.3-70-g09d2