Merge georust#994

994: faster intersects check r=frewsxcv a=michaelkirk - [x] I agree to follow the project's [code of conduct](https://github.com/georust/geo/blob/main/CODE_OF_CONDUCT.md). - [x] I added an entry to `CHANGES.md` if knowledge of this change could be valuable to users. --- The code change is only for the Rect intersection check, but other geometry types, like LineString and Polygon, leverage Rect::intersects, so we should see improvements in almost all of our disjoint intersection checks. cargo bench excerpt: MultiPolygon intersects time: [476.96 ms 477.13 ms 477.32 ms] change: [-8.4983% -8.3486% -8.2284%] (p = 0.00 < 0.05) Performance has improved. Rect intersects time: [27.498 µs 27.546 µs 27.598 µs] change: [-57.503% -57.444% -57.389%] (p = 0.00 < 0.05) Performance has improved. Co-authored-by: Michael Kirk <michael.code@endoftheworl.de>
JIOBIKE · Mar 22, 2023 · 539eb64 · 539eb64
2 parents 7f6c3c9 + 8069542
commit 539eb64
Show file tree

Hide file tree

Showing 3 changed files with 56 additions and 10 deletions.
diff --git a/geo/CHANGES.md b/geo/CHANGES.md
@@ -2,6 +2,8 @@
 
 ## Unreleased
 
+- Speed up intersection checks
+  - <https://github.com/georust/geo/pull/993>
 - FIX: Simplify no longer skips simplifying minimally sized Polygons and LineString
   - <https://github.com/georust/geo/pull/996>
 

diff --git a/geo/benches/intersection.rs b/geo/benches/intersection.rs
@@ -7,11 +7,11 @@ use criterion::Criterion;
 use geo::intersects::Intersects;
 use geo::MultiPolygon;
 
-fn criterion_benchmark(c: &mut Criterion) {
+fn multi_polygon_intersection(c: &mut Criterion) {
     let plot_polygons: MultiPolygon = geo_test_fixtures::nl_plots();
     let zone_polygons: MultiPolygon = geo_test_fixtures::nl_zones();
 
-    c.bench_function("intersection", |bencher| {
+    c.bench_function("MultiPolygon intersects", |bencher| {
         bencher.iter(|| {
             let mut intersects = 0;
             let mut non_intersects = 0;
@@ -32,10 +32,44 @@ fn criterion_benchmark(c: &mut Criterion) {
     });
 }
 
+fn rect_intersection(c: &mut Criterion) {
+    use geo::algorithm::BoundingRect;
+    use geo::geometry::Rect;
+    let plot_bbox: Vec<Rect> = geo_test_fixtures::nl_plots()
+        .iter()
+        .map(|plot| plot.bounding_rect().unwrap())
+        .collect();
+    let zone_bbox: Vec<Rect> = geo_test_fixtures::nl_zones()
+        .iter()
+        .map(|plot| plot.bounding_rect().unwrap())
+        .collect();
+
+    c.bench_function("Rect intersects", |bencher| {
+        bencher.iter(|| {
+            let mut intersects = 0;
+            let mut non_intersects = 0;
+
+            for a in &plot_bbox {
+                for b in &zone_bbox {
+                    if criterion::black_box(a.intersects(b)) {
+                        intersects += 1;
+                    } else {
+                        non_intersects += 1;
+                    }
+                }
+            }
+
+            assert_eq!(intersects, 3054);
+            assert_eq!(non_intersects, 25702);
+        });
+    });
+}
+
 criterion_group! {
-    name = benches;
+    name = bench_multi_polygons;
     config = Criterion::default().sample_size(10);
-    targets = criterion_benchmark
+    targets = multi_polygon_intersection
 }
+criterion_group!(bench_rects, rect_intersection);
 
-criterion_main!(benches);
+criterion_main!(bench_multi_polygons, bench_rects);
diff --git a/geo/src/algorithm/intersects/rect.rs b/geo/src/algorithm/intersects/rect.rs
@@ -22,13 +22,23 @@ where
     T: CoordNum,
 {
     fn intersects(&self, other: &Rect<T>) -> bool {
-        let x_overlap = value_in_range(self.min().x, other.min().x, other.max().x)
-            || value_in_range(other.min().x, self.min().x, self.max().x);
+        if self.max().x < other.min().x {
+            return false;
+        }
 
-        let y_overlap = value_in_range(self.min().y, other.min().y, other.max().y)
-            || value_in_range(other.min().y, self.min().y, self.max().y);
+        if self.max().y < other.min().y {
+            return false;
+        }
 
-        x_overlap && y_overlap
+        if self.min().x > other.max().x {
+            return false;
+        }
+
+        if self.min().y > other.max().y {
+            return false;
+        }
+
+        true
     }
 }