Add a bounding box intersection test to QgsGeometry

We only previously had methods for exact intersections - this commit adds a new QgsGeometry.boundingBoxIntersects() method which can be used to test if just the bounding boxes of geometries/rectangles intersect. It's fast, and doesn't care about invalid geometries (unlike the exact intersects checks)
qgis · Feb 20, 2018 · 3ffbd84 · 3ffbd84
1 parent 9471c5d
commit 3ffbd84
Show file tree

Hide file tree

Showing 4 changed files with 125 additions and 6 deletions.
diff --git a/python/core/geometry/qgsgeometry.sip.in b/python/core/geometry/qgsgeometry.sip.in
@@ -755,14 +755,48 @@ were found.
 .. versionadded:: 3.0
 %End
 
-    bool intersects( const QgsRectangle &r ) const;
+    bool intersects( const QgsRectangle &rectangle ) const;
 %Docstring
-Tests for intersection with a rectangle (uses GEOS)
+Returns true if this geometry exactly intersects with a ``rectangle``. This test is exact
+and can be slow for complex geometries.
+
+The GEOS library is used to perform the intersection test. Geometries which are not
+valid may return incorrect results.
+
+.. seealso:: :py:func:`boundingBoxIntersects`
 %End
 
     bool intersects( const QgsGeometry &geometry ) const;
 %Docstring
-Tests for intersection with a geometry (uses GEOS)
+Returns true if this geometry exactly intersects with another ``geometry``. This test is exact
+and can be slow for complex geometries.
+
+The GEOS library is used to perform the intersection test. Geometries which are not
+valid may return incorrect results.
+
+.. seealso:: :py:func:`boundingBoxIntersects`
+%End
+
+    bool boundingBoxIntersects( const QgsRectangle &rectangle ) const;
+%Docstring
+Returns true if the bounding box of this geometry intersects with a ``rectangle``. Since this
+test only considers the bounding box of the geometry, is is very fast to calculate and handles invalid
+geometries.
+
+.. seealso:: :py:func:`intersects`
+
+.. versionadded:: 3.0
+%End
+
+    bool boundingBoxIntersects( const QgsGeometry &geometry ) const;
+%Docstring
+Returns true if the bounding box of this geometry intersects with the bounding box of another ``geometry``. Since this
+test only considers the bounding box of the geometries, is is very fast to calculate and handles invalid
+geometries.
+
+.. seealso:: :py:func:`intersects`
+
+.. versionadded:: 3.0
 %End
 
     bool contains( const QgsPointXY *p ) const;

diff --git a/src/core/geometry/qgsgeometry.cpp b/src/core/geometry/qgsgeometry.cpp
@@ -1106,6 +1106,26 @@ bool QgsGeometry::intersects( const QgsGeometry &geometry ) const
   return geos.intersects( geometry.d->geometry.get(), &mLastError );
 }
 
+bool QgsGeometry::boundingBoxIntersects( const QgsRectangle &rectangle ) const
+{
+  if ( !d->geometry )
+  {
+    return false;
+  }
+
+  return d->geometry->boundingBox().intersects( rectangle );
+}
+
+bool QgsGeometry::boundingBoxIntersects( const QgsGeometry &geometry ) const
+{
+  if ( !d->geometry || geometry.isNull() )
+  {
+    return false;
+  }
+
+  return d->geometry->boundingBox().intersects( geometry.constGet()->boundingBox() );
+}
+
 bool QgsGeometry::contains( const QgsPointXY *p ) const
 {
   if ( !d->geometry || !p )

diff --git a/src/core/geometry/qgsgeometry.h b/src/core/geometry/qgsgeometry.h
@@ -798,12 +798,50 @@ class CORE_EXPORT QgsGeometry
      */
     bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
 
-    //! Tests for intersection with a rectangle (uses GEOS)
-    bool intersects( const QgsRectangle &r ) const;
+    /**
+     * Returns true if this geometry exactly intersects with a \a rectangle. This test is exact
+     * and can be slow for complex geometries.
+     *
+     * The GEOS library is used to perform the intersection test. Geometries which are not
+     * valid may return incorrect results.
+     *
+     * \see boundingBoxIntersects()
+     */
+    bool intersects( const QgsRectangle &rectangle ) const;
 
-    //! Tests for intersection with a geometry (uses GEOS)
+    /**
+     * Returns true if this geometry exactly intersects with another \a geometry. This test is exact
+     * and can be slow for complex geometries.
+     *
+     * The GEOS library is used to perform the intersection test. Geometries which are not
+     * valid may return incorrect results.
+     *
+     * \see boundingBoxIntersects()
+     */
     bool intersects( const QgsGeometry &geometry ) const;
 
+    /**
+     * Returns true if the bounding box of this geometry intersects with a \a rectangle. Since this
+     * test only considers the bounding box of the geometry, is is very fast to calculate and handles invalid
+     * geometries.
+     *
+     * \see intersects()
+     *
+     * \since QGIS 3.0
+     */
+    bool boundingBoxIntersects( const QgsRectangle &rectangle ) const;
+
+    /**
+     * Returns true if the bounding box of this geometry intersects with the bounding box of another \a geometry. Since this
+     * test only considers the bounding box of the geometries, is is very fast to calculate and handles invalid
+     * geometries.
+     *
+     * \see intersects()
+     *
+     * \since QGIS 3.0
+     */
+    bool boundingBoxIntersects( const QgsGeometry &geometry ) const;
+
     //! Tests for containment of a point (uses GEOS)
     bool contains( const QgsPointXY *p ) const;
 

diff --git a/tests/src/python/test_qgsgeometry.py b/tests/src/python/test_qgsgeometry.py
@@ -4286,6 +4286,33 @@ def testHausdorffDensify(self):
             self.assertAlmostEqual(o, exp, 5,
                                    "mismatch for {} to {}, expected:\n{}\nGot:\n{}\n".format(t[0], t[1], exp, o))
 
+    def testBoundingBoxIntersects(self):
+        tests = [
+            ["LINESTRING (0 0, 100 100)", "LINESTRING (90 0, 100 0)", True],
+            ["LINESTRING (0 0, 100 100)", "LINESTRING (101 0, 102 0)", False],
+            ["POINT(20 1)", "LINESTRING( 0 0, 100 100 )", True],
+            ["POINT(20 1)", "POINT(21 1)", False],
+            ["POINT(20 1)", "POINT(20 1)", True]
+        ]
+        for t in tests:
+            g1 = QgsGeometry.fromWkt(t[0])
+            g2 = QgsGeometry.fromWkt(t[1])
+            res = g1.boundingBoxIntersects(g2)
+            self.assertEqual(res, t[2], "mismatch for {} to {}, expected:\n{}\nGot:\n{}\n".format(g1.asWkt(), g2.asWkt(), t[2], res))
+
+    def testBoundingBoxIntersectsRectangle(self):
+        tests = [
+            ["LINESTRING (0 0, 100 100)", QgsRectangle(90, 0, 100, 10), True],
+            ["LINESTRING (0 0, 100 100)", QgsRectangle(101, 0, 102, 10), False],
+            ["POINT(20 1)", QgsRectangle(0, 0, 100, 100), True],
+            ["POINT(20 1)", QgsRectangle(21, 1, 21, 1), False],
+            ["POINT(20 1)", QgsRectangle(20, 1, 20, 1), True]
+        ]
+        for t in tests:
+            g1 = QgsGeometry.fromWkt(t[0])
+            res = g1.boundingBoxIntersects(t[1])
+            self.assertEqual(res, t[2], "mismatch for {} to {}, expected:\n{}\nGot:\n{}\n".format(g1.asWkt(), t[1].toString(), t[2], res))
+
     def renderGeometry(self, geom, use_pen, as_polygon=False, as_painter_path=False):
         image = QImage(200, 200, QImage.Format_RGB32)
         image.fill(QColor(0, 0, 0))