jagua_rs/geometry/primitives/
edge.rs

1use crate::geometry::Transformation;
2use crate::geometry::geo_traits::{CollidesWith, DistanceTo, Transformable, TransformableFrom};
3use crate::geometry::primitives::GeometryError;
4use crate::geometry::primitives::Point;
5use crate::geometry::primitives::Rect;
6use anyhow::Result;
7use anyhow::ensure;
8
9/// Line segment between two [`Point`]s
10#[derive(Clone, Debug, PartialEq, Copy)]
11pub struct Edge {
12    pub start: Point,
13    pub end: Point,
14}
15
16impl Edge {
17    pub fn try_new(start: Point, end: Point) -> Result<Self> {
18        ensure!(start != end, GeometryError::DegenerateEdge(start));
19        Ok(Edge { start, end })
20    }
21
22    #[must_use]
23    pub fn extend_at_front(mut self, d: f32) -> Self {
24        //extend the line at the front by distance d
25        let (dx, dy) = (self.end.0 - self.start.0, self.end.1 - self.start.1);
26        let l = self.length();
27        self.start.0 -= dx * (d / l);
28        self.start.1 -= dy * (d / l);
29        self
30    }
31
32    #[must_use]
33    pub fn extend_at_back(mut self, d: f32) -> Self {
34        //extend the line at the back by distance d
35        let (dx, dy) = (self.end.0 - self.start.0, self.end.1 - self.start.1);
36        let l = self.length();
37        self.end.0 += dx * (d / l);
38        self.end.1 += dy * (d / l);
39        self
40    }
41
42    #[must_use]
43    pub fn scale(mut self, factor: f32) -> Self {
44        let (dx, dy) = (self.end.0 - self.start.0, self.end.1 - self.start.1);
45        self.start.0 -= dx * (factor - 1.0) / 2.0;
46        self.start.1 -= dy * (factor - 1.0) / 2.0;
47        self.end.0 += dx * (factor - 1.0) / 2.0;
48        self.end.1 += dy * (factor - 1.0) / 2.0;
49        self
50    }
51
52    #[must_use]
53    pub fn reverse(mut self) -> Self {
54        std::mem::swap(&mut self.start, &mut self.end);
55        self
56    }
57
58    #[must_use]
59    pub fn collides_at(&self, other: &Edge) -> Option<Point> {
60        match edge_intersection(self, other, true) {
61            Intersection::No => None,
62            Intersection::Yes(point) => Some(
63                point.expect("Intersection::Yes, but returned no point when this was requested"),
64            ),
65        }
66    }
67
68    /// Returns the closest point which lies on the edge to the given point
69    #[must_use]
70    #[allow(clippy::many_single_char_names)]
71    pub fn closest_point_on_edge(&self, point: &Point) -> Point {
72        //from https://stackoverflow.com/a/6853926
73        let Point(x1, y1) = self.start;
74        let Point(x2, y2) = self.end;
75        let Point(x, y) = point;
76
77        let a = x - x1;
78        let b = y - y1;
79        let c = x2 - x1;
80        let d = y2 - y1;
81
82        let dot = a * c + b * d;
83        let len_sq = c * c + d * d;
84        let mut param = -1.0;
85        if len_sq != 0.0 {
86            param = dot / len_sq;
87        }
88        let (xx, yy) = match param {
89            p if p < 0.0 => (x1, y1),              //start is the closest point
90            p if p > 1.0 => (x2, y2),              //end is the closest point
91            _ => (x1 + param * c, y1 + param * d), //closest point is on the edge
92        };
93
94        Point(xx, yy)
95    }
96
97    #[must_use]
98    pub fn x_min(&self) -> f32 {
99        f32::min(self.start.0, self.end.0)
100    }
101
102    #[must_use]
103    pub fn y_min(&self) -> f32 {
104        f32::min(self.start.1, self.end.1)
105    }
106
107    #[must_use]
108    pub fn x_max(&self) -> f32 {
109        f32::max(self.start.0, self.end.0)
110    }
111
112    #[must_use]
113    pub fn y_max(&self) -> f32 {
114        f32::max(self.start.1, self.end.1)
115    }
116
117    #[must_use]
118    pub fn length(&self) -> f32 {
119        self.start.distance_to(&self.end)
120    }
121
122    #[must_use]
123    pub fn centroid(&self) -> Point {
124        Point(
125            f32::midpoint(self.start.0, self.end.0),
126            f32::midpoint(self.start.1, self.end.1),
127        )
128    }
129
130    #[must_use]
131    pub fn bbox(&self) -> Rect {
132        Rect {
133            x_min: self.x_min(),
134            y_min: self.y_min(),
135            x_max: self.x_max(),
136            y_max: self.y_max(),
137        }
138    }
139}
140
141impl Transformable for Edge {
142    fn transform(&mut self, t: &Transformation) -> &mut Self {
143        let Edge { start, end } = self;
144        start.transform(t);
145        end.transform(t);
146
147        self
148    }
149}
150
151impl TransformableFrom for Edge {
152    fn transform_from(&mut self, reference: &Self, t: &Transformation) -> &mut Self {
153        let Edge { start, end } = self;
154        start.transform_from(&reference.start, t);
155        end.transform_from(&reference.end, t);
156
157        self
158    }
159}
160
161impl DistanceTo<Point> for Edge {
162    #[inline(always)]
163    fn distance_to(&self, point: &Point) -> f32 {
164        f32::sqrt(self.sq_distance_to(point))
165    }
166
167    #[inline(always)]
168    fn sq_distance_to(&self, point: &Point) -> f32 {
169        let Point(x, y) = point;
170        let Point(xx, yy) = self.closest_point_on_edge(point);
171
172        let (dx, dy) = (x - xx, y - yy);
173        dx.powi(2) + dy.powi(2)
174    }
175}
176
177impl CollidesWith<Edge> for Edge {
178    #[inline(always)]
179    fn collides_with(&self, other: &Edge) -> bool {
180        match edge_intersection(self, other, false) {
181            Intersection::No => false,
182            Intersection::Yes(_) => true,
183        }
184    }
185}
186
187impl CollidesWith<Rect> for Edge {
188    #[inline(always)]
189    fn collides_with(&self, other: &Rect) -> bool {
190        other.collides_with(self)
191    }
192}
193
194#[inline(always)]
195fn edge_intersection(e1: &Edge, e2: &Edge, calc_loc: bool) -> Intersection {
196    let Point(x1, y1) = e1.start;
197    let Point(x2, y2) = e1.end;
198    let Point(x3, y3) = e2.start;
199    let Point(x4, y4) = e2.end;
200
201    // Early exit if bounding boxes do not overlap
202    {
203        let x_min_e1 = x1.min(x2);
204        let x_max_e1 = x1.max(x2);
205        let y_min_e1 = y1.min(y2);
206        let y_max_e1 = y1.max(y2);
207
208        let x_min_e2 = x3.min(x4);
209        let x_max_e2 = x3.max(x4);
210        let y_min_e2 = y3.min(y4);
211        let y_max_e2 = y3.max(y4);
212
213        let x_axis_no_overlap = x_min_e1.max(x_min_e2) > x_max_e1.min(x_max_e2);
214        let y_axis_no_overlap = y_min_e1.max(y_min_e2) > y_max_e1.min(y_max_e2);
215
216        if x_axis_no_overlap || y_axis_no_overlap {
217            return Intersection::No;
218        }
219    }
220
221    //based on: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
222    let t_nom = (x2 - x4) * (y4 - y3) - (y2 - y4) * (x4 - x3);
223    let t_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
224    let u_nom = (x2 - x4) * (y2 - y1) - (y2 - y4) * (x2 - x1);
225    let u_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
226
227    if t_denom == 0.0 || u_denom == 0.0 {
228        //parallel edges
229        return Intersection::No;
230    }
231
232    let t = t_nom / t_denom;
233    let u = u_nom / u_denom;
234    if (0.0..=1.0).contains(&t) && (0.0..=1.0).contains(&u) {
235        //intersection point is within the bounds of both edges
236        let loc = if calc_loc {
237            Some(Point(x2 + t * (x1 - x2), y2 + t * (y1 - y2)))
238        } else {
239            None
240        };
241        return Intersection::Yes(loc);
242    }
243    Intersection::No
244}
245
246enum Intersection {
247    Yes(Option<Point>),
248    No,
249}
jagua_rs/geometry/primitives/edge.rs

jagua_rs/geometry/primitives/
edge.rs
