add a is2DClosed test

qgis · Jun 21, 2021 · 0ab96b6 · 0ab96b6
1 parent 16bc56f
commit 0ab96b6
Show file tree

Hide file tree

Showing 7 changed files with 155 additions and 3 deletions.
diff --git a/python/core/auto_generated/geometry/qgscurve.sip.in b/python/core/auto_generated/geometry/qgscurve.sip.in
@@ -60,6 +60,19 @@ Returns the end point of the curve.
     virtual bool isClosed() const /HoldGIL/;
 %Docstring
 Returns ``True`` if the curve is closed.
+
+.. seealso:: :py:func:`is2DClosed`
+%End
+
+    virtual bool is2DClosed() const /HoldGIL/;
+%Docstring
+Returns true if the curve is closed.
+
+Unlike isClosed. It looks only for XY coordinates.
+
+.. seealso:: :py:func:`isClosed`
+
+.. versionadded:: 3.20
 %End
 
     virtual bool isRing() const /HoldGIL/;

diff --git a/python/core/auto_generated/geometry/qgslinestring.sip.in b/python/core/auto_generated/geometry/qgslinestring.sip.in
@@ -420,6 +420,12 @@ segment in the line.
 
     virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
 
+    virtual bool isClosed() const /HoldGIL/;
+
+    virtual bool is2DClosed() const /HoldGIL/;
+
+    virtual bool boundingBoxIntersects( const QgsRectangle &rectangle ) const /HoldGIL/;
+
 
     QVector< QgsVertexId > collectDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false ) const;
 %Docstring

diff --git a/src/core/geometry/qgscurve.cpp b/src/core/geometry/qgscurve.cpp
@@ -37,7 +37,7 @@ bool QgsCurve::operator!=( const QgsAbstractGeometry &other ) const
   return !operator==( other );
 }
 
-bool QgsCurve::isClosed() const
+bool QgsCurve::is2DClosed() const
 {
   if ( numPoints() == 0 )
     return false;
@@ -46,10 +46,18 @@ bool QgsCurve::isClosed() const
   QgsPoint start = startPoint();
   QgsPoint end = endPoint();
 
-  bool closed = qgsDoubleNear( start.x(), end.x() ) &&
-                qgsDoubleNear( start.y(), end.y() );
+  return qgsDoubleNear( start.x(), end.x() ) &&
+         qgsDoubleNear( start.y(), end.y() );
+}
+bool QgsCurve::isClosed() const
+{
+  bool closed = is2DClosed();
   if ( is3D() && closed )
+  {
+    QgsPoint start = startPoint();
+    QgsPoint end = endPoint();
     closed &= qgsDoubleNear( start.z(), end.z() ) || ( std::isnan( start.z() ) && std::isnan( end.z() ) );
+  }
   return closed;
 }
 

diff --git a/src/core/geometry/qgscurve.h b/src/core/geometry/qgscurve.h
@@ -66,9 +66,22 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry
 
     /**
      * Returns TRUE if the curve is closed.
+     *
+     * \see is2DClosed()
      */
     virtual bool isClosed() const SIP_HOLDGIL;
 
+    /**
+     * Returns true if the curve is closed.
+     *
+     * Unlike isClosed. It looks only for XY coordinates.
+     *
+     * \see isClosed()
+     *
+     * \since QGIS 3.20
+     */
+    virtual bool is2DClosed() const SIP_HOLDGIL;
+
     /**
      * Returns TRUE if the curve is a ring.
      */

diff --git a/src/core/geometry/qgslinestring.cpp b/src/core/geometry/qgslinestring.cpp
@@ -363,6 +363,102 @@ bool QgsLineString::removeDuplicateNodes( double epsilon, bool useZValues )
   return result;
 }
 
+bool QgsLineString::is2DClosed() const
+{
+  if ( mX.empty() )
+    return false;
+
+  return qgsDoubleNear( mX.first(), mX.last() ) &&
+         qgsDoubleNear( mY.first(), mY.last() );
+}
+
+bool QgsLineString::isClosed() const
+{
+  bool closed = is2DClosed();
+
+  if ( is3D() && closed )
+    closed &= qgsDoubleNear( mZ.first(), mZ.last() ) || ( std::isnan( mZ.first() ) && std::isnan( mZ.last() ) );
+  return closed;
+}
+
+bool QgsLineString::boundingBoxIntersects( const QgsRectangle &rectangle ) const
+{
+  if ( mX.empty() )
+    return false;
+
+  if ( !mBoundingBox.isNull() )
+  {
+    return mBoundingBox.intersects( rectangle );
+  }
+  const int nb = mX.size();
+
+  // We are a little fancy here!
+  if ( nb > 40 )
+  {
+    // if a large number of vertices, take some sample vertices at 1/5th increments through the linestring
+    // and test whether any are inside the rectangle. Maybe we can shortcut a lot of iterations by doing this!
+    // (why 1/5th? it's picked so that it works nicely for polygon rings which are almost rectangles, so the vertex extremities
+    // will fall on approximately these vertex indices)
+    if ( rectangle.contains( mX.at( 0 ), mY.at( 0 ) ) ||
+         rectangle.contains( mX.at( static_cast< int >( nb * 0.2 ) ), mY.at( static_cast< int >( nb * 0.2 ) ) ) ||
+         rectangle.contains( mX.at( static_cast< int >( nb * 0.4 ) ), mY.at( static_cast< int >( nb * 0.4 ) ) ) ||
+         rectangle.contains( mX.at( static_cast< int >( nb * 0.6 ) ), mY.at( static_cast< int >( nb * 0.6 ) ) ) ||
+         rectangle.contains( mX.at( static_cast< int >( nb * 0.8 ) ), mY.at( static_cast< int >( nb * 0.8 ) ) ) ||
+         rectangle.contains( mX.at( nb - 1 ), mY.at( nb - 1 ) ) )
+      return true;
+  }
+
+  // Be even MORE fancy! Given that bounding box calculation is non-free, cached, and we don't
+  // already have it, we start performing the bounding box calculation while we are testing whether
+  // each point falls inside the rectangle. That way if we end up testing the majority of the points
+  // anyway, we can update the cached bounding box with the results we've calculated along the way
+  // and save future calls to calculate the bounding box!
+  double xmin = std::numeric_limits<double>::max();
+  double ymin = std::numeric_limits<double>::max();
+  double xmax = -std::numeric_limits<double>::max();
+  double ymax = -std::numeric_limits<double>::max();
+
+  const double *x = mX.constData();
+  const double *y = mY.constData();
+  bool foundPointInRectangle = false;
+  for ( int i = 0; i < nb; ++i )
+  {
+    const double px = *x++;
+    xmin = std::min( xmin, px );
+    xmax = std::max( xmax, px );
+    const double py = *y++;
+    ymin = std::min( ymin, py );
+    ymax = std::max( ymax, py );
+
+    if ( !foundPointInRectangle && rectangle.contains( px, py ) )
+    {
+      foundPointInRectangle = true;
+
+      // now... we have a choice to make. If we've already looped through the majority of the points
+      // in this linestring then let's just continue to iterate through the remainder so that we can
+      // complete the overall bounding box calculation we've already mostly done. If however we're only
+      // just at the start of iterating the vertices, we shortcut out early and leave the bounding box
+      // uncalculated
+      if ( i < nb * 0.5 )
+        return true;
+    }
+  }
+
+  // at this stage we now know the overall bounding box of the linestring, so let's cache
+  // it so we don't ever have to calculate this again. We've done all the hard work anyway!
+  mBoundingBox = QgsRectangle( xmin, ymin, xmax, ymax, false );
+
+  if ( foundPointInRectangle )
+    return true;
+
+  // NOTE: if none of the points in the line actually fell inside the rectangle, it doesn't
+  // exclude that the OVERALL bounding box of the linestring itself intersects the rectangle!!
+  // So we fall back to the parent class method which compares the overall bounding box against
+  // the rectangle... and this will be very cheap now that we've already calculated and cached
+  // the linestring's bounding box!
+  return QgsCurve::boundingBoxIntersects( rectangle );
+}
+
 QVector< QgsVertexId > QgsLineString::collectDuplicateNodes( double epsilon, bool useZValues ) const
 {
   QVector< QgsVertexId > res;

diff --git a/src/core/geometry/qgslinestring.h b/src/core/geometry/qgslinestring.h
@@ -588,6 +588,9 @@ class CORE_EXPORT QgsLineString: public QgsCurve
     bool isEmpty() const override SIP_HOLDGIL;
     QgsLineString *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const override SIP_FACTORY;
     bool removeDuplicateNodes( double epsilon = 4 * std::numeric_limits<double>::epsilon(), bool useZValues = false ) override;
+    bool isClosed() const override SIP_HOLDGIL;
+    bool is2DClosed() const override SIP_HOLDGIL;
+    bool boundingBoxIntersects( const QgsRectangle &rectangle ) const override SIP_HOLDGIL;
 
     /**
      * Returns a list of any duplicate nodes contained in the geometry, within the specified tolerance.

diff --git a/tests/src/core/testqgsgeometry.cpp b/tests/src/core/testqgsgeometry.cpp
@@ -1694,11 +1694,13 @@ void TestQgsGeometry::circularString()
 
   //isClosed
   QgsCircularString l11;
+  QVERIFY( !l11.is2DClosed() );
   QVERIFY( !l11.isClosed() );
   l11.setPoints( QgsPointSequence() << QgsPoint( 1, 2 )
                  << QgsPoint( 11, 2 )
                  << QgsPoint( 11, 22 )
                  << QgsPoint( 1, 22 ) );
+  QVERIFY( !l11.is2DClosed() );
   QVERIFY( !l11.isClosed() );
   QCOMPARE( l11.numPoints(), 4 );
   QCOMPARE( l11.area(), 0.0 );
@@ -1709,8 +1711,19 @@ void TestQgsGeometry::circularString()
                  << QgsPoint( QgsWkbTypes::PointM, 11, 2, 0, 4 )
                  << QgsPoint( QgsWkbTypes::PointM, 11, 22, 0, 5 )
                  << QgsPoint( QgsWkbTypes::PointM, 1, 2, 0, 6 ) );
+  QVERIFY( l11.is2DClosed() );
   QVERIFY( l11.isClosed() );
 
+  // test with z
+  l11.addZValue( 123.0 );
+  QVERIFY( l11.is2DClosed() );
+  QVERIFY( l11.isClosed() );
+  QgsPoint pEnd = l11.endPoint();
+  pEnd.setZ( 234.0 );
+  l11.moveVertex( QgsVertexId( 0, 0, l11.numPoints() - 1 ), pEnd );
+  QVERIFY( l11.is2DClosed() );
+  QVERIFY( !l11.isClosed() );
+
   //polygonf
   QgsCircularString l13;
   l13.setPoints( QgsPointSequence() << QgsPoint( QgsWkbTypes::PointZM, 1, 2, 3, 4 )