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    pub fn relation_to(&self, other: Rect) -> GeoRelation {
47        if !self.collides_with(&other) {
48            return GeoRelation::Disjoint;
49        }
50        if self.x_min <= other.x_min
51            && self.y_min <= other.y_min
52            && self.x_max >= other.x_max
53            && self.y_max >= other.y_max
54        {
55            return GeoRelation::Surrounding;
56        }
57        if self.x_min >= other.x_min
58            && self.y_min >= other.y_min
59            && self.x_max <= other.x_max
60            && self.y_max <= other.y_max
61        {
62            return GeoRelation::Enclosed;
63        }
64        GeoRelation::Intersecting
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    #[inline(always)]
70    pub fn almost_relation_to(&self, other: Rect) -> GeoRelation {
71        if !self.almost_collides_with(&other) {
72            return GeoRelation::Disjoint;
73        }
74        if FPA::from(self.x_min) <= FPA::from(other.x_min)
75            && FPA::from(self.y_min) <= FPA::from(other.y_min)
76            && FPA::from(self.x_max) >= FPA::from(other.x_max)
77            && FPA::from(self.y_max) >= FPA::from(other.y_max)
78        {
79            return GeoRelation::Surrounding;
80        }
81        if FPA::from(self.x_min) >= FPA::from(other.x_min)
82            && FPA::from(self.y_min) >= FPA::from(other.y_min)
83            && FPA::from(self.x_max) <= FPA::from(other.x_max)
84            && FPA::from(self.y_max) <= FPA::from(other.y_max)
85        {
86            return GeoRelation::Enclosed;
87        }
88        GeoRelation::Intersecting
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 sides that make up `self`, in the same order as [Rect::quadrants].
164    pub fn sides(&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
186    /// Returns the four edges that make up `self`, in the same order as [Rect::quadrants].
187    pub fn edges(&self) -> [Edge; 4] {
188        let c = self.corners();
189        [
190            Edge {
191                start: c[0],
192                end: c[1],
193            },
194            Edge {
195                start: c[1],
196                end: c[2],
197            },
198            Edge {
199                start: c[2],
200                end: c[3],
201            },
202            Edge {
203                start: c[3],
204                end: c[0],
205            },
206        ]
207    }
208    pub fn width(&self) -> f32 {
209        self.x_max - self.x_min
210    }
211
212    pub fn height(&self) -> f32 {
213        self.y_max - self.y_min
214    }
215
216    /// Returns the largest rectangle that is contained in both `a` and `b`.
217    pub fn intersection(a: Rect, b: Rect) -> Option<Rect> {
218        let x_min = f32::max(a.x_min, b.x_min);
219        let y_min = f32::max(a.y_min, b.y_min);
220        let x_max = f32::min(a.x_max, b.x_max);
221        let y_max = f32::min(a.y_max, b.y_max);
222        if x_min < x_max && y_min < y_max {
223            Some(Rect {
224                x_min,
225                y_min,
226                x_max,
227                y_max,
228            })
229        } else {
230            None
231        }
232    }
233
234    /// Returns the smallest rectangle that contains both `a` and `b`.
235    pub fn bounding_rect(a: Rect, b: Rect) -> Rect {
236        let x_min = f32::min(a.x_min, b.x_min);
237        let y_min = f32::min(a.y_min, b.y_min);
238        let x_max = f32::max(a.x_max, b.x_max);
239        let y_max = f32::max(a.y_max, b.y_max);
240        Rect {
241            x_min,
242            y_min,
243            x_max,
244            y_max,
245        }
246    }
247
248    pub fn centroid(&self) -> Point {
249        Point(
250            (self.x_min + self.x_max) / 2.0,
251            (self.y_min + self.y_max) / 2.0,
252        )
253    }
254
255    pub fn area(&self) -> f32 {
256        (self.x_max - self.x_min) * (self.y_max - self.y_min)
257    }
258
259    pub fn diameter(&self) -> f32 {
260        let dx = self.x_max - self.x_min;
261        let dy = self.y_max - self.y_min;
262        (dx.powi(2) + dy.powi(2)).sqrt()
263    }
264}
265
266impl CollidesWith<Rect> for Rect {
267    #[inline(always)]
268    fn collides_with(&self, other: &Rect) -> bool {
269        f32::max(self.x_min, other.x_min) <= f32::min(self.x_max, other.x_max)
270            && f32::max(self.y_min, other.y_min) <= f32::min(self.y_max, other.y_max)
271    }
272}
273
274impl AlmostCollidesWith<Rect> for Rect {
275    #[inline(always)]
276    fn almost_collides_with(&self, other: &Rect) -> bool {
277        FPA(f32::max(self.x_min, other.x_min)) <= FPA(f32::min(self.x_max, other.x_max))
278            && FPA(f32::max(self.y_min, other.y_min)) <= FPA(f32::min(self.y_max, other.y_max))
279    }
280}
281
282impl CollidesWith<Point> for Rect {
283    #[inline(always)]
284    fn collides_with(&self, point: &Point) -> bool {
285        let Point(x, y) = *point;
286        x >= self.x_min && x <= self.x_max && y >= self.y_min && y <= self.y_max
287    }
288}
289
290impl AlmostCollidesWith<Point> for Rect {
291    #[inline(always)]
292    fn almost_collides_with(&self, point: &Point) -> bool {
293        let (x, y) = (*point).into();
294        FPA(x) >= FPA(self.x_min)
295            && FPA(x) <= FPA(self.x_max)
296            && FPA(y) >= FPA(self.y_min)
297            && FPA(y) <= FPA(self.y_max)
298    }
299}
300
301impl CollidesWith<Edge> for Rect {
302    #[inline(always)]
303    fn collides_with(&self, edge: &Edge) -> bool {
304        //inspired by: https://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d
305
306        let e_x_min = edge.x_min();
307        let e_x_max = edge.x_max();
308        let e_y_min = edge.y_min();
309        let e_y_max = edge.y_max();
310
311        let x_no_overlap = e_x_min.max(self.x_min) > e_x_max.min(self.x_max);
312        let y_no_overlap = e_y_min.max(self.y_min) > e_y_max.min(self.y_max);
313
314        if x_no_overlap || y_no_overlap {
315            return false; // Bounding boxes do not overlap
316        }
317
318        //If either end point of the line is inside the rectangle
319        if self.collides_with(&edge.start) || self.collides_with(&edge.end) {
320            return true;
321        }
322
323        //Determine which side of the edge each corner of the rectangle is on
324        let Point(s_x, s_y) = edge.start;
325        let Point(e_x, e_y) = edge.end;
326        let edge_dx = e_x - s_x;
327        let edge_dy = e_y - s_y;
328
329        // Function to determine which side of the edge a point is on.
330        // This is the 2D cross-product.
331        let side = |p_x, p_y| (p_x - s_x) * edge_dy - (p_y - s_y) * edge_dx;
332
333        let corners = self.corners();
334        let mut last_side = side(corners[3].x(), corners[3].y());
335
336        for i in 0..4 {
337            let current_side = side(corners[i].x(), corners[i].y());
338            // If signs differ, the edge may cross the rectangle side
339            if current_side * last_side <= 0.0 {
340                // The edge connects the previous corner (i-1, wrapping around) and the current corner i.
341                let prev_corner_idx = if i == 0 { 3 } else { i - 1 };
342                let rect_edge = Edge {
343                    start: corners[prev_corner_idx],
344                    end: corners[i],
345                };
346                if edge.collides_with(&rect_edge) {
347                    return true;
348                }
349            }
350            last_side = current_side;
351        }
352
353        false
354    }
355}
356
357impl DistanceTo<Point> for Rect {
358    #[inline(always)]
359    fn distance_to(&self, point: &Point) -> f32 {
360        self.sq_distance_to(point).sqrt()
361    }
362
363    #[inline(always)]
364    fn sq_distance_to(&self, point: &Point) -> f32 {
365        let Point(x, y) = *point;
366        let mut distance: f32 = 0.0;
367        if x < self.x_min {
368            distance += (x - self.x_min).powi(2);
369        } else if x > self.x_max {
370            distance += (x - self.x_max).powi(2);
371        }
372        if y < self.y_min {
373            distance += (y - self.y_min).powi(2);
374        } else if y > self.y_max {
375            distance += (y - self.y_max).powi(2);
376        }
377        distance.abs()
378    }
379}
380
381impl SeparationDistance<Point> for Rect {
382    #[inline(always)]
383    fn separation_distance(&self, point: &Point) -> (GeoPosition, f32) {
384        let (position, sq_distance) = self.sq_separation_distance(point);
385        (position, sq_distance.sqrt())
386    }
387
388    #[inline(always)]
389    fn sq_separation_distance(&self, point: &Point) -> (GeoPosition, f32) {
390        match self.collides_with(point) {
391            false => (GeoPosition::Exterior, self.sq_distance_to(point)),
392            true => {
393                let Point(x, y) = *point;
394                let min_distance = [
395                    (x - self.x_min).abs(),
396                    (x - self.x_max).abs(),
397                    (y - self.y_min).abs(),
398                    (y - self.y_max).abs(),
399                ]
400                .into_iter()
401                .min_by_key(|&d| OrderedFloat(d))
402                .unwrap();
403                (GeoPosition::Interior, min_distance.powi(2))
404            }
405        }
406    }
407}
jagua_rs/geometry/primitives/rect.rs

jagua_rs/geometry/primitives/
rect.rs
