jagua_rs/geometry/primitives/
edge.rs

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

jagua_rs/geometry/primitives/
edge.rs
