jagua_rs/geometry/primitives/
rect.rs

1use crate::geometry::geo_enums::{GeoPosition, GeoRelation};
2use crate::geometry::geo_traits::{
3    AlmostCollidesWith, CollidesWith, DistanceTo, SeparationDistance,
4};
5use crate::geometry::primitives::Edge;
6use crate::geometry::primitives::Point;
7use crate::util::FPA;
8use anyhow::Result;
9use anyhow::ensure;
10use ordered_float::OrderedFloat;
11use std::cmp::Ordering;
12
13///Axis-aligned rectangle
14#[derive(Clone, Debug, PartialEq, Copy)]
15pub struct Rect {
16    pub x_min: f32,
17    pub y_min: f32,
18    pub x_max: f32,
19    pub y_max: f32,
20}
21
22impl Rect {
23    pub fn try_new(x_min: f32, y_min: f32, x_max: f32, y_max: f32) -> Result<Self> {
24        ensure!(
25            x_min < x_max && y_min < y_max,
26            "invalid rectangle, x_min: {x_min}, x_max: {x_max}, y_min: {y_min}, y_max: {y_max}"
27        );
28        Ok(Rect {
29            x_min,
30            y_min,
31            x_max,
32            y_max,
33        })
34    }
35
36    pub fn from_diagonal_corners(c1: Point, c2: Point) -> Result<Self> {
37        let x_min = f32::min(c1.x(), c2.x());
38        let y_min = f32::min(c1.y(), c2.y());
39        let x_max = f32::max(c1.x(), c2.x());
40        let y_max = f32::max(c1.y(), c2.y());
41        Rect::try_new(x_min, y_min, x_max, y_max)
42    }
43
44    /// Returns the geometric relation between `self` and another [`Rect`].
45    pub fn relation_to(&self, other: Rect) -> GeoRelation {
46        if self.collides_with(&other) {
47            if self.x_min <= other.x_min
48                && self.y_min <= other.y_min
49                && self.x_max >= other.x_max
50                && self.y_max >= other.y_max
51            {
52                GeoRelation::Surrounding
53            } else if self.x_min >= other.x_min
54                && self.y_min >= other.y_min
55                && self.x_max <= other.x_max
56                && self.y_max <= other.y_max
57            {
58                GeoRelation::Enclosed
59            } else {
60                GeoRelation::Intersecting
61            }
62        } else {
63            GeoRelation::Disjoint
64        }
65    }
66
67    /// Returns the [`GeoRelation`] between `self` and another [`Rect`], with a tolerance for floating point precision.
68    /// In edge cases, this method will lean towards `Surrounding` and `Enclosed` instead of `Intersecting`.
69    pub fn almost_relation_to(&self, other: Rect) -> GeoRelation {
70        if self.almost_collides_with(&other) {
71            if FPA::from(self.x_min) <= FPA::from(other.x_min)
72                && FPA::from(self.y_min) <= FPA::from(other.y_min)
73                && FPA::from(self.x_max) >= FPA::from(other.x_max)
74                && FPA::from(self.y_max) >= FPA::from(other.y_max)
75            {
76                GeoRelation::Surrounding
77            } else if FPA::from(self.x_min) >= FPA::from(other.x_min)
78                && FPA::from(self.y_min) >= FPA::from(other.y_min)
79                && FPA::from(self.x_max) <= FPA::from(other.x_max)
80                && FPA::from(self.y_max) <= FPA::from(other.y_max)
81            {
82                GeoRelation::Enclosed
83            } else {
84                GeoRelation::Intersecting
85            }
86        } else {
87            GeoRelation::Disjoint
88        }
89    }
90
91    /// Returns a new rectangle with the same centroid but inflated
92    /// to be the minimum square that contains `self`.
93    pub fn inflate_to_square(&self) -> Rect {
94        let width = self.x_max - self.x_min;
95        let height = self.y_max - self.y_min;
96        let mut dx = 0.0;
97        let mut dy = 0.0;
98        if height < width {
99            dy = (width - height) / 2.0;
100        } else if width < height {
101            dx = (height - width) / 2.0;
102        }
103        Rect {
104            x_min: self.x_min - dx,
105            y_min: self.y_min - dy,
106            x_max: self.x_max + dx,
107            y_max: self.y_max + dy,
108        }
109    }
110
111    /// Returns a new rectangle with the same centroid but scaled by `factor`.
112    pub fn scale(self, factor: f32) -> Self {
113        let dx = (self.x_max - self.x_min) * (factor - 1.0) / 2.0;
114        let dy = (self.y_max - self.y_min) * (factor - 1.0) / 2.0;
115        self.resize_by(dx, dy)
116            .expect("scaling should not lead to invalid rectangle")
117    }
118
119    /// Returns a new rectangle with the same centroid as `self` but expanded by `dx` in both x-directions and by `dy` in both y-directions.
120    /// If the new rectangle is invalid (x_min >= x_max or y_min >= y_max), returns None.
121    pub fn resize_by(mut self, dx: f32, dy: f32) -> Option<Self> {
122        self.x_min -= dx;
123        self.y_min -= dy;
124        self.x_max += dx;
125        self.y_max += dy;
126
127        if self.x_min < self.x_max && self.y_min < self.y_max {
128            Some(self)
129        } else {
130            //resizing would lead to invalid rectangle
131            None
132        }
133    }
134
135    /// For all quadrants, contains indices of the two neighbors of the quadrant at that index.
136    pub const QUADRANT_NEIGHBOR_LAYOUT: [[usize; 2]; 4] = [[1, 3], [0, 2], [1, 3], [0, 2]];
137
138    /// Returns the 4 quadrants of `self`.
139    /// Ordered in the same way as quadrants in a cartesian plane:
140    /// <https://en.wikipedia.org/wiki/Quadrant_(plane_geometry)>
141    pub fn quadrants(&self) -> [Self; 4] {
142        let mid = self.centroid();
143        let corners = self.corners();
144
145        let q1 = Rect::from_diagonal_corners(corners[0], mid).unwrap();
146        let q2 = Rect::from_diagonal_corners(corners[1], mid).unwrap();
147        let q3 = Rect::from_diagonal_corners(corners[2], mid).unwrap();
148        let q4 = Rect::from_diagonal_corners(corners[3], mid).unwrap();
149
150        [q1, q2, q3, q4]
151    }
152
153    /// Returns the four corners of `self`, in the same order as [Rect::quadrants].
154    pub fn corners(&self) -> [Point; 4] {
155        [
156            Point(self.x_max, self.y_max),
157            Point(self.x_min, self.y_max),
158            Point(self.x_min, self.y_min),
159            Point(self.x_max, self.y_min),
160        ]
161    }
162
163    /// Returns the four edges that make up `self`, in the same order as [Rect::quadrants].
164    pub fn edges(&self) -> [Edge; 4] {
165        let c = self.corners();
166        [
167            Edge {
168                start: c[0],
169                end: c[1],
170            },
171            Edge {
172                start: c[1],
173                end: c[2],
174            },
175            Edge {
176                start: c[2],
177                end: c[3],
178            },
179            Edge {
180                start: c[3],
181                end: c[0],
182            },
183        ]
184    }
185    pub fn width(&self) -> f32 {
186        self.x_max - self.x_min
187    }
188
189    pub fn height(&self) -> f32 {
190        self.y_max - self.y_min
191    }
192
193    /// Returns the largest rectangle that is contained in both `a` and `b`.
194    pub fn intersection(a: Rect, b: Rect) -> Option<Rect> {
195        let x_min = f32::max(a.x_min, b.x_min);
196        let y_min = f32::max(a.y_min, b.y_min);
197        let x_max = f32::min(a.x_max, b.x_max);
198        let y_max = f32::min(a.y_max, b.y_max);
199        if x_min < x_max && y_min < y_max {
200            Some(Rect {
201                x_min,
202                y_min,
203                x_max,
204                y_max,
205            })
206        } else {
207            None
208        }
209    }
210
211    /// Returns the smallest rectangle that contains both `a` and `b`.
212    pub fn bounding_rect(a: Rect, b: Rect) -> Rect {
213        let x_min = f32::min(a.x_min, b.x_min);
214        let y_min = f32::min(a.y_min, b.y_min);
215        let x_max = f32::max(a.x_max, b.x_max);
216        let y_max = f32::max(a.y_max, b.y_max);
217        Rect {
218            x_min,
219            y_min,
220            x_max,
221            y_max,
222        }
223    }
224
225    pub fn centroid(&self) -> Point {
226        Point(
227            (self.x_min + self.x_max) / 2.0,
228            (self.y_min + self.y_max) / 2.0,
229        )
230    }
231
232    pub fn area(&self) -> f32 {
233        (self.x_max - self.x_min) * (self.y_max - self.y_min)
234    }
235
236    pub fn diameter(&self) -> f32 {
237        let dx = self.x_max - self.x_min;
238        let dy = self.y_max - self.y_min;
239        (dx.powi(2) + dy.powi(2)).sqrt()
240    }
241}
242
243impl CollidesWith<Rect> for Rect {
244    #[inline(always)]
245    fn collides_with(&self, other: &Rect) -> bool {
246        f32::max(self.x_min, other.x_min) <= f32::min(self.x_max, other.x_max)
247            && f32::max(self.y_min, other.y_min) <= f32::min(self.y_max, other.y_max)
248    }
249}
250
251impl AlmostCollidesWith<Rect> for Rect {
252    #[inline(always)]
253    fn almost_collides_with(&self, other: &Rect) -> bool {
254        FPA(f32::max(self.x_min, other.x_min)) <= FPA(f32::min(self.x_max, other.x_max))
255            && FPA(f32::max(self.y_min, other.y_min)) <= FPA(f32::min(self.y_max, other.y_max))
256    }
257}
258
259impl CollidesWith<Point> for Rect {
260    #[inline(always)]
261    fn collides_with(&self, point: &Point) -> bool {
262        let Point(x, y) = *point;
263        x >= self.x_min && x <= self.x_max && y >= self.y_min && y <= self.y_max
264    }
265}
266
267impl AlmostCollidesWith<Point> for Rect {
268    #[inline(always)]
269    fn almost_collides_with(&self, point: &Point) -> bool {
270        let (x, y) = (*point).into();
271        FPA(x) >= FPA(self.x_min)
272            && FPA(x) <= FPA(self.x_max)
273            && FPA(y) >= FPA(self.y_min)
274            && FPA(y) <= FPA(self.y_max)
275    }
276}
277
278impl CollidesWith<Edge> for Rect {
279    #[inline(always)]
280    fn collides_with(&self, edge: &Edge) -> bool {
281        //inspired by: https://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d
282
283        let x_min = edge.x_min();
284        let x_max = edge.x_max();
285        let y_min = edge.y_min();
286        let y_max = edge.y_max();
287
288        //If both end points of the line are entirely outside the range of the rectangle
289        if x_max < self.x_min || x_min > self.x_max || y_max < self.y_min || y_min > self.y_max {
290            return false;
291        }
292
293        //If either end point of the line is inside the rectangle
294        if self.collides_with(&edge.start) || self.collides_with(&edge.end) {
295            return true;
296        }
297
298        //If all corners of rectangle are on the same side of the edge, no collision is possible
299        const POINT_EDGE_RELATION: fn(Point, &Edge) -> Ordering =
300            |p: Point, edge: &Edge| -> Ordering {
301                let Point(p_x, p_y) = p;
302                let Point(s_x, s_y) = edge.start;
303                let Point(e_x, e_y) = edge.end;
304                // if 0.0, the point is on the line
305                // if > 0.0, the point is "above" of the line
306                // if < 0.0, the point is "below" the line
307                let v = (p_x - s_x) * (e_y - s_y) - (p_y - s_y) * (e_x - s_x);
308                v.partial_cmp(&0.0).unwrap()
309            };
310
311        let all_corners_same_side = self
312            .corners()
313            .map(|corner| POINT_EDGE_RELATION(corner, edge))
314            .windows(2)
315            .all(|w| w[0] == w[1]);
316
317        if all_corners_same_side {
318            return false;
319        }
320
321        //The only possible that remains is that the edge collides with one of the edges of the rectangle
322        self.edges()
323            .iter()
324            .any(|rect_edge| edge.collides_with(rect_edge))
325    }
326}
327
328impl DistanceTo<Point> for Rect {
329    #[inline(always)]
330    fn distance_to(&self, point: &Point) -> f32 {
331        self.sq_distance_to(point).sqrt()
332    }
333
334    #[inline(always)]
335    fn sq_distance_to(&self, point: &Point) -> f32 {
336        let Point(x, y) = *point;
337        let mut distance: f32 = 0.0;
338        if x < self.x_min {
339            distance += (x - self.x_min).powi(2);
340        } else if x > self.x_max {
341            distance += (x - self.x_max).powi(2);
342        }
343        if y < self.y_min {
344            distance += (y - self.y_min).powi(2);
345        } else if y > self.y_max {
346            distance += (y - self.y_max).powi(2);
347        }
348        distance.abs()
349    }
350}
351
352impl SeparationDistance<Point> for Rect {
353    #[inline(always)]
354    fn separation_distance(&self, point: &Point) -> (GeoPosition, f32) {
355        let (position, sq_distance) = self.sq_separation_distance(point);
356        (position, sq_distance.sqrt())
357    }
358
359    #[inline(always)]
360    fn sq_separation_distance(&self, point: &Point) -> (GeoPosition, f32) {
361        match self.collides_with(point) {
362            false => (GeoPosition::Exterior, self.sq_distance_to(point)),
363            true => {
364                let Point(x, y) = *point;
365                let min_distance = [
366                    (x - self.x_min).abs(),
367                    (x - self.x_max).abs(),
368                    (y - self.y_min).abs(),
369                    (y - self.y_max).abs(),
370                ]
371                .into_iter()
372                .min_by_key(|&d| OrderedFloat(d))
373                .unwrap();
374                (GeoPosition::Interior, min_distance.powi(2))
375            }
376        }
377    }
378}
jagua_rs/geometry/primitives/rect.rs

jagua_rs/geometry/primitives/
rect.rs
