Merge branch 'main' into rstar_0_10

MultisampledNight · Mar 1, 2023 · 50eab35 · 50eab35
2 parents 1db773c + f6093ed
commit 50eab35
Show file tree

Hide file tree

Showing 7 changed files with 501 additions and 402 deletions.
diff --git a/geo-bool-ops-benches/benches/boolean_ops.rs b/geo-bool-ops-benches/benches/boolean_ops.rs
@@ -40,30 +40,22 @@ fn run_complex<T: Measurement>(c: &mut Criterion<T>) {
         });
 
         group.sample_size(10);
-        group.bench_with_input(BenchmarkId::new("bops::union", steps), &(), |b, _| {
-            b.iter_batched(
-                polys.sampler(),
-                |&(ref poly, ref poly2, _, _)| poly.intersection(poly2),
-                BatchSize::SmallInput,
-            );
-        });
-
         group.bench_with_input(
             BenchmarkId::new("bops::intersection", steps),
             &(),
             |b, _| {
                 b.iter_batched(
                     polys.sampler(),
-                    |&(ref poly, ref poly2, _, _)| poly.union(poly2),
+                    |&(ref poly, ref poly2, _, _)| poly.intersection(poly2),
                     BatchSize::SmallInput,
                 );
             },
         );
 
-        group.bench_with_input(BenchmarkId::new("rgbops::union", steps), &(), |b, _| {
+        group.bench_with_input(BenchmarkId::new("bops::union", steps), &(), |b, _| {
             b.iter_batched(
                 polys.sampler(),
-                |&(_, _, ref poly, ref poly2)| poly.intersection(poly2),
+                |&(ref poly, ref poly2, _, _)| poly.union(poly2),
                 BatchSize::SmallInput,
             );
         });
@@ -74,12 +66,20 @@ fn run_complex<T: Measurement>(c: &mut Criterion<T>) {
             |b, _| {
                 b.iter_batched(
                     polys.sampler(),
-                    |&(_, _, ref poly, ref poly2)| poly.union(poly2),
+                    |&(_, _, ref poly, ref poly2)| OtherBooleanOp::intersection(poly, poly2),
                     BatchSize::SmallInput,
                 );
             },
         );
 
+        group.bench_with_input(BenchmarkId::new("rgbops::union", steps), &(), |b, _| {
+            b.iter_batched(
+                polys.sampler(),
+                |&(_, _, ref poly, ref poly2)| OtherBooleanOp::union(poly, poly2),
+                BatchSize::SmallInput,
+            );
+        });
+
         group.bench_with_input(BenchmarkId::new("geo::relate", steps), &(), |b, _| {
             b.iter_batched(
                 polys.sampler(),

diff --git a/geo/CHANGES.md b/geo/CHANGES.md
diff --git a/geo/src/algorithm/minimum_rotated_rect.rs b/geo/src/algorithm/minimum_rotated_rect.rs
@@ -0,0 +1,101 @@
+use num_traits::Float;
+
+use crate::{
+    algorithm::{centroid::Centroid, rotate::Rotate, BoundingRect, CoordsIter},
+    Area, ConvexHull, CoordFloat, GeoFloat, GeoNum, LinesIter, Polygon,
+};
+/// Return the minimum bounding rectangle(MBR) of geometry
+/// reference: https://en.wikipedia.org/wiki/Minimum_bounding_box
+/// minimum rotated rect is the rectangle that can enclose all points given
+/// and have smallest area of all enclosing rectangles
+/// the rect can be any-oriented, not only axis-aligned.
+///
+/// # Examples
+///
+/// ```
+/// use geo_types::{line_string, polygon, LineString, Polygon};
+/// use geo::MinimumRotatedRect;
+/// 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)];
+/// let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
+/// assert_eq!(
+///     mbr.exterior(),
+///     &LineString::from(vec![
+///         (1.7000000000000006, 24.6),
+///         (1.4501458363715918, 30.446587428904767),
+///         (14.4, 31.0),
+///         (14.649854163628408, 25.153412571095235),
+///         (1.7000000000000006, 24.6),
+///     ])
+/// );
+/// ```
+pub trait MinimumRotatedRect<'a, T> {
+    type Scalar: GeoNum;
+    fn minimum_rotated_rect(&'a self) -> Option<Polygon<Self::Scalar>>;
+}
+
+impl<'a, T, G> MinimumRotatedRect<'a, T> for G
+where
+    T: CoordFloat + GeoFloat + GeoNum,
+    G: CoordsIter<'a, Scalar = T>,
+{
+    type Scalar = T;
+
+    fn minimum_rotated_rect(&'a self) -> Option<Polygon<Self::Scalar>> {
+        let convex_poly = ConvexHull::convex_hull(self);
+        let mut min_area: T = Float::max_value();
+        let mut min_angle: T = T::zero();
+        let mut rect_poly: Option<Polygon<T>> = None;
+        let rotate_point = convex_poly.centroid();
+        for line in convex_poly.exterior().lines_iter() {
+            let (ci, cii) = line.points();
+            let angle = (cii.y() - ci.y()).atan2(cii.x() - ci.x()).to_degrees();
+            let rotated_poly = Rotate::rotate_around_point(&convex_poly, -angle, rotate_point?);
+            let tmp_poly = rotated_poly.bounding_rect()?.to_polygon();
+            let area = tmp_poly.unsigned_area();
+            if area < min_area {
+                min_area = area;
+                min_angle = angle;
+                rect_poly = Some(tmp_poly);
+            }
+        }
+        Some(rect_poly?.rotate_around_point(min_angle, rotate_point?))
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use geo_types::{line_string, polygon, LineString, Polygon};
+
+    use crate::MinimumRotatedRect;
+
+    #[test]
+    fn returns_polygon_mbr() {
+        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)];
+        let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
+        assert_eq!(
+            mbr.exterior(),
+            &LineString::from(vec![
+                (1.7000000000000006, 24.6),
+                (1.4501458363715918, 30.446587428904767),
+                (14.4, 31.0),
+                (14.649854163628408, 25.153412571095235),
+                (1.7000000000000006, 24.6),
+            ])
+        );
+    }
+    #[test]
+    fn returns_linestring_mbr() {
+        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)];
+        let mbr = MinimumRotatedRect::minimum_rotated_rect(&poly).unwrap();
+        assert_eq!(
+            mbr.exterior(),
+            &LineString::from(vec![
+                (1.7000000000000006, 24.6),
+                (1.4501458363715918, 30.446587428904767),
+                (14.4, 31.0),
+                (14.649854163628408, 25.153412571095235),
+                (1.7000000000000006, 24.6),
+            ])
+        );
+    }
+}
diff --git a/geo/src/algorithm/mod.rs b/geo/src/algorithm/mod.rs
@@ -18,6 +18,10 @@ pub use bool_ops::{BooleanOps, OpType};
 pub mod bounding_rect;
 pub use bounding_rect::BoundingRect;
 
+/// Calculate the minimum rotated rectangle of a `Geometry`.
+pub mod minimum_rotated_rect;
+pub use minimum_rotated_rect::MinimumRotatedRect;
+
 /// Calculate the centroid of a `Geometry`.
 pub mod centroid;
 pub use centroid::Centroid;

diff --git a/geo/src/lib.rs b/geo/src/lib.rs
@@ -116,6 +116,8 @@
 //!
 //! - **[`BoundingRect`](BoundingRect)**: Calculate the axis-aligned
 //!   bounding rectangle of a geometry
+//! - **[`MinimumRotatedRect`](MinimumRotatedRect)**: Calculate the
+//!   minimum bounding box of a geometry
 //! - **[`ConcaveHull`](ConcaveHull)**: Calculate the concave hull of a
 //!   geometry
 //! - **[`ConvexHull`](ConvexHull)**: Calculate the convex hull of a

diff --git a/jts-test-runner/src/lib.rs b/jts-test-runner/src/lib.rs
@@ -52,7 +52,7 @@ mod tests {
     // several of the ConvexHull tests are currently failing
     fn test_all_general() {
         init_logging();
-        let mut runner = TestRunner::new().with_overlay_precision_floating();
+        let mut runner = TestRunner::new();
         runner.run().expect("test cases failed");
 
         if !runner.failures().is_empty() {
@@ -96,9 +96,7 @@ mod tests {
     #[test]
     fn test_boolean_ops() {
         init_logging();
-        let mut runner = TestRunner::new()
-            .matching_filename_glob("*Overlay*.xml")
-            .with_overlay_precision_floating();
+        let mut runner = TestRunner::new().matching_filename_glob("*Overlay*.xml");
         runner.run().expect("test cases failed");
 
         // sanity check that *something* was run

diff --git a/jts-test-runner/src/runner.rs b/jts-test-runner/src/runner.rs
@@ -17,7 +17,6 @@ const VALIDATE_TEST_XML: Dir = include_dir!("$CARGO_MANIFEST_DIR/resources/testx
 pub struct TestRunner {
     filename_filter: Option<String>,
     desc_filter: Option<String>,
-    check_overlay_precision: bool,
     cases: Option<Vec<TestCase>>,
     failures: Vec<TestFailure>,
     unsupported: Vec<TestCase>,
@@ -71,11 +70,6 @@ impl TestRunner {
         self
     }
 
-    pub fn with_overlay_precision_floating(mut self) -> Self {
-        self.check_overlay_precision = true;
-        self
-    }
-
     pub fn prepare_cases(&mut self) -> Result<()> {
         self.cases = Some(self.parse_cases()?);
         Ok(())
@@ -407,7 +401,6 @@ impl TestRunner {
                     match test.operation_input.into_operation(&case) {
                         Ok(operation) => {
                             if matches!(operation, Operation::BooleanOp { .. })
-                                && self.check_overlay_precision
                                 && run.precision_model.is_some()
                                 && &run.precision_model.as_ref().unwrap().ty != "FLOATING"
                             {