From 53d376eaeef991850d35318b147f75c8f103319d Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sun, 27 Dec 2020 21:54:31 +0100 Subject: Change to polygongraph instead of polygon in roomtool The polygon room tool used a convoluted process for determining what the user actually wants to draw. I have changed to the polygon graph instead, which makes the checks easier and restricts the user a bit less. In the process however I found a serious problem with my handling float, so everything needed to change to margin compares (which I of course should have done in the beginning. Guys, take the warning seriously and don't ignore it for ten years like I did. It will come back to haunt you.. apparently) instead of direct equality. --- src/math/line_segment.rs | 46 +++++++++++++++++++++++++++++----------------- 1 file changed, 29 insertions(+), 17 deletions(-) (limited to 'src/math/line_segment.rs') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 204cf0c..738f56a 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -1,8 +1,9 @@ //! A line segment is like a line, but with a start and an end, with the line only being between //! those two. -use super::{Rect, Surface, TripletOrientation, Vec2}; +use super::{ExactSurface, Rect, TripletOrientation, Vec2}; use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; +use float_cmp::ApproxEq; use nalgebra::{RealField, Scalar}; use num_traits::Zero; use serde::{Deserialize, Serialize}; @@ -37,9 +38,9 @@ impl LineSegment { /// 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, ls2: &LineSegment) -> bool + pub fn intersect(ls1: &LineSegment, ls2: &LineSegment, margin: M) -> bool where - T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero, + T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq, { /* 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 @@ -56,10 +57,14 @@ impl LineSegment { */ // Cache the necessary orientations. - 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); + let ls1_ls2start_orientation = + super::triplet_orientation(ls1.start, ls1.end, ls2.start, margin); + let ls1_ls2end_orientation = + super::triplet_orientation(ls1.start, ls1.end, ls2.end, margin); + let ls2_ls1start_orientation = + super::triplet_orientation(ls2.start, ls2.end, ls1.start, margin); + let ls2_ls1end_orientation = + super::triplet_orientation(ls2.start, ls2.end, ls1.end, margin); // Check for the first case that wase described (general case). if ls1_ls2start_orientation != ls1_ls2end_orientation @@ -100,9 +105,14 @@ impl LineSegment { /// Try to find the the point where the two line segments intersect. If they do not intersect, /// `None` is returned. If the lines are parallel and intersect (at least part of a line is on /// a part of the other line), inside that region is returned. - pub fn intersection(line_a: &LineSegment, line_b: &LineSegment) -> Option> + pub fn intersection( + line_a: &LineSegment, + line_b: &LineSegment, + margin: M, + ) -> Option> where - T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField, + T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField + ApproxEq, + M: Copy, { // Calculate the differences of each line value from starting point to end point // coordinate. @@ -115,8 +125,10 @@ impl LineSegment { let d = (dax * dby) - (day * dbx); if d == T::zero() { // The two line segments are parallel, check if one may be on the other. - if super::triplet_orientation(line_a.start, line_a.end, line_b.start) == TripletOrientation::Collinear - && super::triplet_orientation(line_a.start, line_a.end, line_b.end) == TripletOrientation::Collinear + if super::triplet_orientation(line_a.start, line_a.end, line_b.start, margin) + == TripletOrientation::Collinear + && super::triplet_orientation(line_a.start, line_a.end, line_b.end, margin) + == TripletOrientation::Collinear { if line_a.contains_collinear(line_b.start) { Some(line_b.start) @@ -156,16 +168,16 @@ impl LineSegment { /// Find all segments, into which this LineSegment would be splitted, when the points provided /// would cut the segment. The points must be on the line, otherwise this does not make sense. /// Also, no segments of length zero (start point = end point) will be created. - pub fn segments(&self, split_points: &[Vec2]) -> Vec> + pub fn segments(&self, split_points: &[Vec2], margin: M) -> Vec> where - T: ClosedSub + ClosedMul + PartialOrd + Zero, + T: ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq, + M: Copy, { // Make sure all segments are collinear with the segment and actually on it assert_eq!( - split_points - .iter() - .find(|&p| super::triplet_orientation(self.start, self.end, *p) - != TripletOrientation::Collinear), + split_points.iter().find(|&p| super::triplet_orientation( + self.start, self.end, *p, margin + ) != TripletOrientation::Collinear), None ); assert_eq!( -- cgit v1.2.3-70-g09d2