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
117impl Transformable for Edge {
118    fn transform(&mut self, t: &Transformation) -> &mut Self {
119        let Edge { start, end } = self;
120        start.transform(t);
121        end.transform(t);
122
123        self
124    }
125}
126
127impl TransformableFrom for Edge {
128    fn transform_from(&mut self, reference: &Self, t: &Transformation) -> &mut Self {
129        let Edge { start, end } = self;
130        start.transform_from(&reference.start, t);
131        end.transform_from(&reference.end, t);
132
133        self
134    }
135}
136
137impl DistanceTo<Point> for Edge {
138    #[inline(always)]
139    fn distance_to(&self, point: &Point) -> f32 {
140        f32::sqrt(self.sq_distance_to(point))
141    }
142
143    #[inline(always)]
144    fn sq_distance_to(&self, point: &Point) -> f32 {
145        let Point(x, y) = point;
146        let Point(xx, yy) = self.closest_point_on_edge(point);
147
148        let (dx, dy) = (x - xx, y - yy);
149        dx.powi(2) + dy.powi(2)
150    }
151}
152
153impl CollidesWith<Edge> for Edge {
154    #[inline(always)]
155    fn collides_with(&self, other: &Edge) -> bool {
156        match edge_intersection(self, other, false) {
157            Intersection::No => false,
158            Intersection::Yes(_) => true,
159        }
160    }
161}
162
163impl CollidesWith<Rect> for Edge {
164    #[inline(always)]
165    fn collides_with(&self, other: &Rect) -> bool {
166        other.collides_with(self)
167    }
168}
169
170#[inline(always)]
171fn edge_intersection(e1: &Edge, e2: &Edge, calc_loc: bool) -> Intersection {
172    let Point(x1, y1) = e1.start;
173    let Point(x2, y2) = e1.end;
174    let Point(x3, y3) = e2.start;
175    let Point(x4, y4) = e2.end;
176
177    // Early exit if bounding boxes do not overlap
178    {
179        let x_min_e1 = x1.min(x2);
180        let x_max_e1 = x1.max(x2);
181        let y_min_e1 = y1.min(y2);
182        let y_max_e1 = y1.max(y2);
183
184        let x_min_e2 = x3.min(x4);
185        let x_max_e2 = x3.max(x4);
186        let y_min_e2 = y3.min(y4);
187        let y_max_e2 = y3.max(y4);
188
189        let x_axis_no_overlap = x_min_e1.max(x_min_e2) > x_max_e1.min(x_max_e2);
190        let y_axis_no_overlap = y_min_e1.max(y_min_e2) > y_max_e1.min(y_max_e2);
191
192        if x_axis_no_overlap || y_axis_no_overlap {
193            return Intersection::No;
194        }
195    }
196
197    //based on: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
198    let t_nom = (x2 - x4) * (y4 - y3) - (y2 - y4) * (x4 - x3);
199    let t_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
200    let u_nom = (x2 - x4) * (y2 - y1) - (y2 - y4) * (x2 - x1);
201    let u_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
202
203    if t_denom == 0.0 || u_denom == 0.0 {
204        //parallel edges
205        return Intersection::No;
206    }
207
208    let t = t_nom / t_denom;
209    let u = u_nom / u_denom;
210    if (0.0..=1.0).contains(&t) && (0.0..=1.0).contains(&u) {
211        //intersection point is within the bounds of both edges
212        let loc = match calc_loc {
213            false => None,
214            true => Some(Point(x2 + t * (x1 - x2), y2 + t * (y1 - y2))),
215        };
216        return Intersection::Yes(loc);
217    }
218    Intersection::No
219}
220
221enum Intersection {
222    Yes(Option<Point>),
223    No,
224}
jagua_rs/geometry/primitives/edge.rs

jagua_rs/geometry/primitives/
edge.rs
