geo/algorithm/
minimum_rotated_rect.rs

1use num_traits::Float;
2
3use crate::{
4    algorithm::{centroid::Centroid, rotate::Rotate, BoundingRect, CoordsIter},
5    Area, ConvexHull, CoordFloat, GeoFloat, GeoNum, LinesIter, Polygon,
6};
7/// Return the minimum bounding rectangle(MBR) of geometry
8/// reference: <https://en.wikipedia.org/wiki/Minimum_bounding_box>
9/// minimum rotated rect is the rectangle that can enclose all points given
10/// and have smallest area of all enclosing rectangles
11/// the rect can be any-oriented, not only axis-aligned.
12///
13/// # Examples
14///
15/// ```
16/// use geo_types::{line_string, polygon, LineString, Polygon};
17/// use geo::MinimumRotatedRect;
18/// let poly: Polygon<f64> = polygon![(x: 3.3, y: 30.4), (x: 1.7, y: 24.6), (x: 13.4, y: 25.1), (x: 14.4, y: 31.0),(x:3.3,y:30.4)];
19/// let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
20/// assert_eq!(
21///     mbr.exterior(),
22///     &LineString::from(vec![
23///         (1.7000000000000006, 24.6),
24///         (1.4501458363715918, 30.446587428904767),
25///         (14.4, 31.0),
26///         (14.649854163628408, 25.153412571095235),
27///         (1.7000000000000006, 24.6),
28///     ])
29/// );
30/// ```
31pub trait MinimumRotatedRect<'a, T> {
32    type Scalar: GeoNum;
33    fn minimum_rotated_rect(&'a self) -> Option<Polygon<Self::Scalar>>;
34}
35
36impl<'a, T, G> MinimumRotatedRect<'a, T> for G
37where
38    T: CoordFloat + GeoFloat + GeoNum,
39    G: CoordsIter<'a, Scalar = T>,
40{
41    type Scalar = T;
42
43    fn minimum_rotated_rect(&'a self) -> Option<Polygon<Self::Scalar>> {
44        let convex_poly = ConvexHull::convex_hull(self);
45        let mut min_area: T = Float::max_value();
46        let mut min_angle: T = T::zero();
47        let mut rect_poly: Option<Polygon<T>> = None;
48        let rotate_point = convex_poly.centroid();
49        for line in convex_poly.exterior().lines_iter() {
50            let (ci, cii) = line.points();
51            let angle = (cii.y() - ci.y()).atan2(cii.x() - ci.x()).to_degrees();
52            let rotated_poly = Rotate::rotate_around_point(&convex_poly, -angle, rotate_point?);
53            let tmp_poly = rotated_poly.bounding_rect()?.to_polygon();
54            let area = tmp_poly.unsigned_area();
55            if area < min_area {
56                min_area = area;
57                min_angle = angle;
58                rect_poly = Some(tmp_poly);
59            }
60        }
61        Some(rect_poly?.rotate_around_point(min_angle, rotate_point?))
62    }
63}
64
65#[cfg(test)]
66mod test {
67    use geo_types::{line_string, polygon, LineString, Polygon};
68
69    use crate::MinimumRotatedRect;
70
71    #[test]
72    fn returns_polygon_mbr() {
73        let poly: Polygon<f64> = polygon![(x: 3.3, y: 30.4), (x: 1.7, y: 24.6), (x: 13.4, y: 25.1), (x: 14.4, y: 31.0),(x:3.3,y:30.4)];
74        let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
75        assert_eq!(
76            mbr.exterior(),
77            &LineString::from(vec![
78                (1.7000000000000006, 24.6),
79                (1.4501458363715918, 30.446587428904767),
80                (14.4, 31.0),
81                (14.649854163628408, 25.153412571095235),
82                (1.7000000000000006, 24.6),
83            ])
84        );
85    }
86    #[test]
87    fn returns_linestring_mbr() {
88        let poly: LineString<f64> = line_string![(x: 3.3, y: 30.4), (x: 1.7, y: 24.6), (x: 13.4, y: 25.1), (x: 14.4, y: 31.0)];
89        let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
90        assert_eq!(
91            mbr.exterior(),
92            &LineString::from(vec![
93                (1.7000000000000006, 24.6),
94                (1.4501458363715918, 30.446587428904767),
95                (14.4, 31.0),
96                (14.649854163628408, 25.153412571095235),
97                (1.7000000000000006, 24.6),
98            ])
99        );
100    }
101}
geo/algorithm/minimum_rotated_rect.rs

geo/algorithm/
minimum_rotated_rect.rs
