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, calculate_location: bool) -> Intersection {
172    if f32::max(e1.x_min(), e2.x_min()) > f32::min(e1.x_max(), e2.x_max())
173        || f32::max(e1.y_min(), e2.y_min()) > f32::min(e1.y_max(), e2.y_max())
174    {
175        //bounding boxes do not overlap
176        return Intersection::No;
177    }
178
179    //based on: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
180    let Point(x1, y1) = e1.start;
181    let Point(x2, y2) = e1.end;
182    let Point(x3, y3) = e2.start;
183    let Point(x4, y4) = e2.end;
184
185    let t_nom = (x2 - x4) * (y4 - y3) - (y2 - y4) * (x4 - x3);
186    let t_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
187    let u_nom = (x2 - x4) * (y2 - y1) - (y2 - y4) * (x2 - x1);
188    let u_denom = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
189
190    if t_denom == 0.0 || u_denom == 0.0 {
191        //parallel edges
192        Intersection::No
193    } else {
194        let t = t_nom / t_denom;
195        let u = u_nom / u_denom;
196        if (0.0..=1.0).contains(&t) && (0.0..=1.0).contains(&u) {
197            if calculate_location {
198                let x = x2 + t * (x1 - x2);
199                let y = y2 + t * (y1 - y2);
200                Intersection::Yes(Some(Point(x, y)))
201            } else {
202                Intersection::Yes(None)
203            }
204        } else {
205            Intersection::No
206        }
207    }
208}
209
210enum Intersection {
211    Yes(Option<Point>),
212    No,
213}