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

jagua_rs/geometry/primitives/
edge.rs
