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

jagua_rs/geometry/primitives/
rect.rs
