Better duplicate node detection/removal handling

qgis · Oct 16, 2020 · 41a30ac · 41a30ac
1 parent 5f67531
commit 41a30ac
Show file tree

Hide file tree

Showing 5 changed files with 66 additions and 33 deletions.
diff --git a/python/core/auto_generated/geometry/qgslinestring.sip.in b/python/core/auto_generated/geometry/qgslinestring.sip.in
@@ -421,9 +421,9 @@ 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;
+    QVector< QgsVertexId > collectDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false ) const;
 %Docstring
-Returns ``True`` if the linestring contains duplicate nodes within the specified tolerance.
+Returns a list of any duplicate nodes contained in the geometry, within the specified tolerance.
 
 If ``useZValues`` is ``True`` then z values will also be considered when testing for duplicates.
 

diff --git a/src/core/geometry/qgslinestring.cpp b/src/core/geometry/qgslinestring.cpp
@@ -363,10 +363,11 @@ bool QgsLineString::removeDuplicateNodes( double epsilon, bool useZValues )
   return result;
 }
 
-bool QgsLineString::hasDuplicateNodes( double epsilon, bool useZValues ) const
+QVector< QgsVertexId > QgsLineString::collectDuplicateNodes( double epsilon, bool useZValues ) const
 {
+  QVector< QgsVertexId > res;
   if ( mX.count() <= 1 )
-    return false;
+    return res;
 
   const double *x = mX.constData();
   const double *y = mY.constData();
@@ -377,6 +378,8 @@ bool QgsLineString::hasDuplicateNodes( double epsilon, bool useZValues ) const
   double prevX = *x++;
   double prevY = *y++;
   double prevZ = z ? *z++ : 0;
+
+  QgsVertexId id;
   for ( int i = 1; i < mX.count(); ++i )
   {
     double currentX = *x++;
@@ -386,7 +389,8 @@ bool QgsLineString::hasDuplicateNodes( double epsilon, bool useZValues ) const
          qgsDoubleNear( currentY, prevY, epsilon ) &&
          ( !useZ || qgsDoubleNear( currentZ, prevZ, epsilon ) ) )
     {
-      return true;
+      id.vertex = i;
+      res << id;
     }
     else
     {
@@ -395,7 +399,7 @@ bool QgsLineString::hasDuplicateNodes( double epsilon, bool useZValues ) const
       prevZ = currentZ;
     }
   }
-  return false;
+  return res;
 }
 
 QPolygonF QgsLineString::asQPolygonF() const

diff --git a/src/core/geometry/qgslinestring.h b/src/core/geometry/qgslinestring.h
@@ -590,13 +590,13 @@ class CORE_EXPORT QgsLineString: public QgsCurve
     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.
+     * Returns a list of any duplicate nodes contained in the geometry, 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;
+    QVector< QgsVertexId > collectDuplicateNodes( double epsilon = 4 * std::numeric_limits<double>::epsilon(), bool useZValues = false ) const;
 
     QPolygonF asQPolygonF() const override;
 

diff --git a/src/core/qgsgeometryvalidator.cpp b/src/core/qgsgeometryvalidator.cpp
@@ -116,42 +116,48 @@ void QgsGeometryValidator::validatePolyline( int i, const QgsLineString *line, b
     return;
   }
 
-  int j = 0;
   std::unique_ptr< QgsLineString > noDupes;
 
-  // QgsLineString::hasDuplicateNodes() is much more efficient then the duplicate
-  // point detection/removal code below, so assume the
-  // most likely situation that a linestring DOESN'T have duplicate nodes
-  // and defer the expensive duplicate point emission/removal to only if
-  // we really need to do it
-  if ( line->hasDuplicateNodes( 1E-8 ) )
+  // test for duplicate nodes, and if we find any flag errors and then remove them so that the subsequent
+  // tests work OK.
+  const QVector< QgsVertexId > duplicateNodes = line->collectDuplicateNodes( 1E-8 );
+  if ( !duplicateNodes.empty() )
   {
     noDupes.reset( line->clone() );
-    while ( j < noDupes->numPoints() - 1 )
+    for ( int j = duplicateNodes.size() - 1; j >= 0; j-- )
     {
-      int n = 0;
-      QgsPointXY dupeLocation;
-      while ( j < noDupes->numPoints() - 1 && qgsDoubleNear( noDupes->xAt( j ), noDupes->xAt( j + 1 ), 1E-8 ) && qgsDoubleNear( noDupes->yAt( j ), noDupes->yAt( j + 1 ), 1E-8 ) )
-      {
-        dupeLocation = QgsPointXY( noDupes->pointN( j ) );
-        noDupes->deleteVertex( QgsVertexId( -1, -1, j ) );
-        n++;
-      }
+      const QgsVertexId duplicateVertex = duplicateNodes.at( j );
+      const QgsPointXY duplicationLocation = noDupes->vertexAt( duplicateVertex );
+      noDupes->deleteVertex( duplicateVertex );
+      int n = 1;
 
-      if ( n > 0 )
+      // count how many other points exist at this location too
+      for ( int k = j - 1; k >= 0; k-- )
       {
-        QString msg = QObject::tr( "line %1 contains %n duplicate node(s) at %2", "number of duplicate nodes", n ).arg( i ).arg( j );
-        QgsDebugMsgLevel( msg, 2 );
-        emit errorFound( QgsGeometry::Error( msg, dupeLocation ) );
-        mErrorCount++;
+        const QgsVertexId prevDupe = duplicateNodes.at( k );
+        const QgsPoint prevPoint = noDupes->vertexAt( prevDupe );
+        if ( qgsDoubleNear( duplicationLocation.x(), prevPoint.x(), 1E-8 ) && qgsDoubleNear( duplicationLocation.y(), prevPoint.y(), 1E-8 ) )
+        {
+          noDupes->deleteVertex( prevDupe );
+          n++;
+        }
+        else
+        {
+          break;
+        }
       }
 
-      j++;
+      j -= n - 1;
+
+      QString msg = QObject::tr( "line %1 contains %n duplicate node(s) starting at vertex %2", "number of duplicate nodes", n + 1 ).arg( i + 1 ).arg( duplicateVertex.vertex - n + 1 );
+      QgsDebugMsgLevel( msg, 2 );
+      emit errorFound( QgsGeometry::Error( msg, duplicationLocation ) );
+      mErrorCount++;
     }
     line = noDupes.get();
   }
 
-  for ( j = 0; !mStop && j < line->numPoints() - 3; j++ )
+  for ( int j = 0; !mStop && j < line->numPoints() - 3; j++ )
   {
     const double xAtJ = line->xAt( j );
     const double yAtJ = line->yAt( j );

diff --git a/tests/src/python/test_qgsgeometryvalidator.py b/tests/src/python/test_qgsgeometryvalidator.py
@@ -12,13 +12,19 @@
 
 from qgis.core import (
     QgsGeometry,
-    QgsGeometryValidator
+    QgsGeometryValidator,
+    QgsPointXY
 )
 
 from qgis.testing import (
-    unittest
+    unittest,
+    start_app
 )
 
+from qgis.PyQt.QtTest import QSignalSpy
+
+app = start_app()
+
 
 class TestQgsGeometryValidator(unittest.TestCase):
 
@@ -60,6 +66,23 @@ def testIssue15660(self):
         # make sure validating this geometry doesn't crash QGIS
         QgsGeometryValidator.validateGeometry(g)
 
+    def test_linestring_duplicate_nodes(self):
+        g = QgsGeometry.fromWkt("LineString (1 1, 1 1, 1 1, 1 2, 1 3, 1 3, 1 3, 1 4, 1 5, 1 6, 1 6)")
+
+        validator = QgsGeometryValidator(g)
+        spy = QSignalSpy(validator.errorFound)
+        validator.run()
+
+        self.assertEqual(len(spy), 3)
+        self.assertEqual(spy[0][0].where(), QgsPointXY(1, 6))
+        self.assertEqual(spy[0][0].what(), 'line 1 contains 2 duplicate node(s) starting at vertex 10')
+
+        self.assertEqual(spy[1][0].where(), QgsPointXY(1, 3))
+        self.assertEqual(spy[1][0].what(), 'line 1 contains 3 duplicate node(s) starting at vertex 5')
+
+        self.assertEqual(spy[2][0].where(), QgsPointXY(1, 1))
+        self.assertEqual(spy[2][0].what(), 'line 1 contains 3 duplicate node(s) starting at vertex 1')
+
 
 if __name__ == '__main__':
     unittest.main()