Extract logic from QgsLineString::removeDuplicateNodes to a highly op…

…timised check for duplicate nodes QgsLineString::hasDuplicateNodes
qgis · Oct 16, 2020 · 73b0e68 · 73b0e68
1 parent 850ac4c
commit 73b0e68
Show file tree

Hide file tree

Showing 3 changed files with 55 additions and 0 deletions.
diff --git a/python/core/auto_generated/geometry/qgslinestring.sip.in b/python/core/auto_generated/geometry/qgslinestring.sip.in
@@ -420,6 +420,16 @@ segment in the line.
 
     virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
 
+
+    bool hasDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false ) const;
+%Docstring
+Returns ``True`` if the linestring contains duplicate nodes within the specified tolerance.
+
+If ``useZValues`` is ``True`` then z values will also be considered when testing for duplicates.
+
+.. versionadded:: 3.16
+%End
+
     virtual QPolygonF asQPolygonF() const;
 
 

diff --git a/src/core/geometry/qgslinestring.cpp b/src/core/geometry/qgslinestring.cpp
@@ -363,6 +363,41 @@ bool QgsLineString::removeDuplicateNodes( double epsilon, bool useZValues )
   return result;
 }
 
+bool QgsLineString::hasDuplicateNodes( double epsilon, bool useZValues ) const
+{
+  if ( mX.count() <= 1 )
+    return false;
+
+  const double *x = mX.constData();
+  const double *y = mY.constData();
+  bool hasZ = is3D();
+  bool useZ = hasZ && useZValues;
+  const double *z = useZ ? mZ.constData() : nullptr;
+
+  double prevX = *x++;
+  double prevY = *y++;
+  double prevZ = z ? *z++ : 0;
+  for ( int i = 1; i < mX.count(); ++i )
+  {
+    double currentX = *x++;
+    double currentY = *y++;
+    double currentZ = useZ ? *z++ : 0;
+    if ( qgsDoubleNear( currentX, prevX, epsilon ) &&
+         qgsDoubleNear( currentY, prevY, epsilon ) &&
+         ( !useZ || qgsDoubleNear( currentZ, prevZ, epsilon ) ) )
+    {
+      return true;
+    }
+    else
+    {
+      prevX = currentX;
+      prevY = currentY;
+      prevZ = currentZ;
+    }
+  }
+  return false;
+}
+
 QPolygonF QgsLineString::asQPolygonF() const
 {
   const int nb = mX.size();

diff --git a/src/core/geometry/qgslinestring.h b/src/core/geometry/qgslinestring.h
@@ -588,6 +588,16 @@ 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;
+
+    /**
+     * Returns TRUE if the linestring contains duplicate nodes within the specified tolerance.
+     *
+     * If \a useZValues is TRUE then z values will also be considered when testing for duplicates.
+     *
+     * \since QGIS 3.16
+     */
+    bool hasDuplicateNodes( double epsilon = 4 * std::numeric_limits<double>::epsilon(), bool useZValues = false ) const;
+
     QPolygonF asQPolygonF() const override;
 
     bool fromWkb( QgsConstWkbPtr &wkb ) override;