Add API method to remove duplicate nodes from geometries

Removes duplicate nodes from the geometry, wherever removing the nodes does not result in a degenerate geometry. By default, z values are not considered when detecting duplicate nodes. E.g. two nodes with the same x and y coordinate but different z values will still be considered duplicate and one will be removed. If useZValues is true, then the z values are also tested and nodes with the same x and y but different z will be maintained. Note that duplicate nodes are not tested between different parts of a multipart geometry. E.g. a multipoint geometry with overlapping points will not be changed by this method. The function will return true if nodes were removed, or false if no duplicate nodes were found. Includes unit tests and a processing algorithm which exposes this functionality.
qgis · Dec 3, 2017 · e12621c · e12621c
1 parent 0b452ca
commit e12621c
Show file tree

Hide file tree

Showing 34 changed files with 720 additions and 2 deletions.
diff --git a/python/core/geometry/qgsabstractgeometry.sip b/python/core/geometry/qgsabstractgeometry.sip
@@ -436,6 +436,29 @@ Returns the centroid of the geometry
  :rtype: QgsAbstractGeometry
 %End
 
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false ) = 0;
+%Docstring
+ Removes duplicate nodes from the geometry, wherever removing the nodes does not result in a
+ degenerate geometry.
+
+ The ``epsilon`` parameter specifies the tolerance for coordinates when determining that
+ vertices are identical.
+
+ By default, z values are not considered when detecting duplicate nodes. E.g. two nodes
+ with the same x and y coordinate but different z values will still be considered
+ duplicate and one will be removed. If ``useZValues`` is true, then the z values are
+ also tested and nodes with the same x and y but different z will be maintained.
+
+ Note that duplicate nodes are not tested between different parts of a multipart geometry. E.g.
+ a multipoint geometry with overlapping points will not be changed by this method.
+
+ The function will return true if nodes were removed, or false if no duplicate nodes
+ were found.
+
+.. versionadded:: 3.0
+ :rtype: bool
+%End
+
     virtual double vertexAngle( QgsVertexId vertex ) const = 0;
 %Docstring
  Returns approximate angle at a vertex. This is usually the average angle between adjacent

diff --git a/python/core/geometry/qgscircularstring.sip b/python/core/geometry/qgscircularstring.sip
@@ -83,6 +83,9 @@ class QgsCircularString: QgsCurve
 
     virtual QgsCircularString *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
 
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
+
     virtual void draw( QPainter &p ) const;
 
      virtual void transform( const QgsCoordinateTransform &ct, QgsCoordinateTransform::TransformDirection d = QgsCoordinateTransform::ForwardTransform,

diff --git a/python/core/geometry/qgscompoundcurve.sip b/python/core/geometry/qgscompoundcurve.sip
@@ -79,6 +79,8 @@ class QgsCompoundCurve: QgsCurve
 
     virtual QgsCompoundCurve *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
 
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
 
     int nCurves() const;
 %Docstring

diff --git a/python/core/geometry/qgscurvepolygon.sip b/python/core/geometry/qgscurvepolygon.sip
@@ -67,6 +67,8 @@ class QgsCurvePolygon: QgsSurface
 
     virtual QgsCurvePolygon *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
 
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
 
     int numInteriorRings() const;
 %Docstring

diff --git a/python/core/geometry/qgsgeometry.sip b/python/core/geometry/qgsgeometry.sip
@@ -688,6 +688,29 @@ Returns true if WKB of the geometry is of WKBMulti* type
  :rtype: QgsGeometry
 %End
 
+    bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+%Docstring
+ Removes duplicate nodes from the geometry, wherever removing the nodes does not result in a
+ degenerate geometry.
+
+ The ``epsilon`` parameter specifies the tolerance for coordinates when determining that
+ vertices are identical.
+
+ By default, z values are not considered when detecting duplicate nodes. E.g. two nodes
+ with the same x and y coordinate but different z values will still be considered
+ duplicate and one will be removed. If ``useZValues`` is true, then the z values are
+ also tested and nodes with the same x and y but different z will be maintained.
+
+ Note that duplicate nodes are not tested between different parts of a multipart geometry. E.g.
+ a multipoint geometry with overlapping points will not be changed by this method.
+
+ The function will return true if nodes were removed, or false if no duplicate nodes
+ were found.
+
+.. versionadded:: 3.0
+ :rtype: bool
+%End
+
     bool intersects( const QgsRectangle &r ) const;
 %Docstring
 Tests for intersection with a rectangle (uses GEOS)

diff --git a/python/core/geometry/qgsgeometrycollection.sip b/python/core/geometry/qgsgeometrycollection.sip
@@ -52,6 +52,9 @@ class QgsGeometryCollection: QgsAbstractGeometry
     virtual void clear();
 
     virtual QgsGeometryCollection *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
+
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
     virtual QgsAbstractGeometry *boundary() const /Factory/;
 
     virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ ) const;

diff --git a/python/core/geometry/qgslinestring.sip b/python/core/geometry/qgslinestring.sip
@@ -179,6 +179,8 @@ Closes the line string by appending the first point to the end of the line, if i
 
     virtual QgsLineString *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
 
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
 
     virtual bool fromWkb( QgsConstWkbPtr &wkb );
 

diff --git a/python/core/geometry/qgspoint.sip b/python/core/geometry/qgspoint.sip
@@ -339,6 +339,9 @@ class QgsPoint: QgsAbstractGeometry
     virtual QgsPoint *clone() const /Factory/;
 
     virtual QgsPoint *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;
+
+    virtual bool removeDuplicateNodes( double epsilon = 4 * DBL_EPSILON, bool useZValues = false );
+
     virtual void clear();
 
     virtual bool fromWkb( QgsConstWkbPtr &wkb );

diff --git a/python/plugins/processing/tests/testdata/custom/line_duplicate_nodes.gml b/python/plugins/processing/tests/testdata/custom/line_duplicate_nodes.gml
@@ -0,0 +1,19 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<ogr:FeatureCollection
+     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+     xsi:schemaLocation="http://ogr.maptools.org/ line_duplicate_nodes.xsd"
+     xmlns:ogr="http://ogr.maptools.org/"
+     xmlns:gml="http://www.opengis.net/gml">
+  <gml:boundedBy>
+    <gml:Box>
+      <gml:coord><gml:X>2</gml:X><gml:Y>0</gml:Y></gml:coord>
+      <gml:coord><gml:X>3</gml:X><gml:Y>3</gml:Y></gml:coord>
+    </gml:Box>
+  </gml:boundedBy>
+
+  <gml:featureMember>
+    <ogr:line_duplicate_nodes fid="lines.2">
+      <ogr:geometryProperty><gml:LineString srsName="EPSG:4326"><gml:coordinates>2,0 2,2 3,2 3,3 3,3</gml:coordinates></gml:LineString></ogr:geometryProperty>
+    </ogr:line_duplicate_nodes>
+  </gml:featureMember>
+</ogr:FeatureCollection>
diff --git a/python/plugins/processing/tests/testdata/custom/line_duplicate_nodes.xsd b/python/plugins/processing/tests/testdata/custom/line_duplicate_nodes.xsd
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<xs:schema targetNamespace="http://ogr.maptools.org/" xmlns:ogr="http://ogr.maptools.org/" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:gml="http://www.opengis.net/gml" elementFormDefault="qualified" version="1.0">
+<xs:import namespace="http://www.opengis.net/gml" schemaLocation="http://schemas.opengis.net/gml/2.1.2/feature.xsd"/>
+<xs:element name="FeatureCollection" type="ogr:FeatureCollectionType" substitutionGroup="gml:_FeatureCollection"/>
+<xs:complexType name="FeatureCollectionType">
+  <xs:complexContent>
+    <xs:extension base="gml:AbstractFeatureCollectionType">
+      <xs:attribute name="lockId" type="xs:string" use="optional"/>
+      <xs:attribute name="scope" type="xs:string" use="optional"/>
+    </xs:extension>
+  </xs:complexContent>
+</xs:complexType>
+<xs:element name="line_duplicate_nodes" type="ogr:line_duplicate_nodes_Type" substitutionGroup="gml:_Feature"/>
+<xs:complexType name="line_duplicate_nodes_Type">
+  <xs:complexContent>
+    <xs:extension base="gml:AbstractFeatureType">
+      <xs:sequence>
+        <xs:element name="geometryProperty" type="gml:LineStringPropertyType" nillable="true" minOccurs="0" maxOccurs="1"/>
+      </xs:sequence>
+    </xs:extension>
+  </xs:complexContent>
+</xs:complexType>
+</xs:schema>
diff --git a/python/plugins/processing/tests/testdata/expected/removed_duplicated_nodes_line.gml b/python/plugins/processing/tests/testdata/expected/removed_duplicated_nodes_line.gml
@@ -0,0 +1,19 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<ogr:FeatureCollection
+     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+     xsi:schemaLocation="http://ogr.maptools.org/ removed_duplicated_nodes_line.xsd"
+     xmlns:ogr="http://ogr.maptools.org/"
+     xmlns:gml="http://www.opengis.net/gml">
+  <gml:boundedBy>
+    <gml:Box>
+      <gml:coord><gml:X>2</gml:X><gml:Y>0</gml:Y></gml:coord>
+      <gml:coord><gml:X>3</gml:X><gml:Y>3</gml:Y></gml:coord>
+    </gml:Box>
+  </gml:boundedBy>
+
+  <gml:featureMember>
+    <ogr:removed_duplicated_nodes_line fid="lines.2">
+      <ogr:geometryProperty><gml:LineString srsName="EPSG:4326"><gml:coordinates>2,0 2,2 3,2 3,3</gml:coordinates></gml:LineString></ogr:geometryProperty>
+    </ogr:removed_duplicated_nodes_line>
+  </gml:featureMember>
+</ogr:FeatureCollection>
diff --git a/python/plugins/processing/tests/testdata/expected/removed_duplicated_nodes_line.xsd b/python/plugins/processing/tests/testdata/expected/removed_duplicated_nodes_line.xsd
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<xs:schema targetNamespace="http://ogr.maptools.org/" xmlns:ogr="http://ogr.maptools.org/" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:gml="http://www.opengis.net/gml" elementFormDefault="qualified" version="1.0">
+<xs:import namespace="http://www.opengis.net/gml" schemaLocation="http://schemas.opengis.net/gml/2.1.2/feature.xsd"/>
+<xs:element name="FeatureCollection" type="ogr:FeatureCollectionType" substitutionGroup="gml:_FeatureCollection"/>
+<xs:complexType name="FeatureCollectionType">
+  <xs:complexContent>
+    <xs:extension base="gml:AbstractFeatureCollectionType">
+      <xs:attribute name="lockId" type="xs:string" use="optional"/>
+      <xs:attribute name="scope" type="xs:string" use="optional"/>
+    </xs:extension>
+  </xs:complexContent>
+</xs:complexType>
+<xs:element name="removed_duplicated_nodes_line" type="ogr:removed_duplicated_nodes_line_Type" substitutionGroup="gml:_Feature"/>
+<xs:complexType name="removed_duplicated_nodes_line_Type">
+  <xs:complexContent>
+    <xs:extension base="gml:AbstractFeatureType">
+      <xs:sequence>
+        <xs:element name="geometryProperty" type="gml:LineStringPropertyType" nillable="true" minOccurs="0" maxOccurs="1"/>
+      </xs:sequence>
+    </xs:extension>
+  </xs:complexContent>
+</xs:complexType>
+</xs:schema>
diff --git a/python/plugins/processing/tests/testdata/qgis_algorithm_tests.yaml b/python/plugins/processing/tests/testdata/qgis_algorithm_tests.yaml
@@ -4582,3 +4582,15 @@ tests:
         name: expected/difference.gml
         type: vector
 
+  - algorithm: native:removeduplicatenodes
+    name: Remove duplicate nodes lines
+    params:
+      INPUT:
+        name: custom/line_duplicate_nodes.gml
+        type: vector
+      TOLERANCE: 1.0e-06
+      USE_Z_VALUE: false
+    results:
+      OUTPUT:
+        name: expected/removed_duplicated_nodes_line.gml
+        type: vector
diff --git a/src/analysis/CMakeLists.txt b/src/analysis/CMakeLists.txt
@@ -51,6 +51,7 @@ SET(QGIS_ANALYSIS_SRCS
   processing/qgsalgorithmpackage.cpp
   processing/qgsalgorithmpromotetomultipart.cpp
   processing/qgsalgorithmrasterlayeruniquevalues.cpp
+  processing/qgsalgorithmremoveduplicatenodes
   processing/qgsalgorithmremovenullgeometry.cpp
   processing/qgsalgorithmrenamelayer.cpp
   processing/qgsalgorithmsaveselectedfeatures.cpp

diff --git a/src/analysis/processing/qgsalgorithmremoveduplicatenodes.cpp b/src/analysis/processing/qgsalgorithmremoveduplicatenodes.cpp
@@ -0,0 +1,96 @@
+/***************************************************************************
+                         qgsalgorithmremoveduplicatenodes.cpp
+                         ---------------------
+    begin                : November 2017
+    copyright            : (C) 2017 by Nyall Dawson
+    email                : nyall dot dawson at gmail dot com
+ ***************************************************************************/
+
+/***************************************************************************
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+#include "qgsalgorithmremoveduplicatenodes.h"
+
+///@cond PRIVATE
+
+QString QgsAlgorithmRemoveDuplicateNodes::name() const
+{
+  return QStringLiteral( "removeduplicatenodes" );
+}
+
+QString QgsAlgorithmRemoveDuplicateNodes::displayName() const
+{
+  return QObject::tr( "Remove duplicate nodes" );
+}
+
+QStringList QgsAlgorithmRemoveDuplicateNodes::tags() const
+{
+  return QObject::tr( "points,valid,overlapping" ).split( ',' );
+}
+
+QString QgsAlgorithmRemoveDuplicateNodes::group() const
+{
+  return QObject::tr( "Vector geometry" );
+}
+
+QString QgsAlgorithmRemoveDuplicateNodes::outputName() const
+{
+  return QObject::tr( "Cleaned" );
+}
+
+QString QgsAlgorithmRemoveDuplicateNodes::shortHelpString() const
+{
+  return QObject::tr( "This algorithm removes duplicate nodes from features, wherever removing the nodes does "
+                      "not result in a degenerate geometry.\n\n"
+                      "The tolerance parameter specifies the tolerance for coordinates when determining whether "
+                      "vertices are identical.\n\n"
+                      "By default, z values are not considered when detecting duplicate nodes. E.g. two nodes "
+                      "with the same x and y coordinate but different z values will still be considered "
+                      "duplicate and one will be removed. If the Use Z Value parameter is true, then the z values are "
+                      "also tested and nodes with the same x and y but different z will be maintained.\n\n"
+                      "Note that duplicate nodes are not tested between different parts of a multipart geometry. E.g. "
+                      "a multipoint geometry with overlapping points will not be changed by this method." );
+}
+
+QgsAlgorithmRemoveDuplicateNodes *QgsAlgorithmRemoveDuplicateNodes::createInstance() const
+{
+  return new QgsAlgorithmRemoveDuplicateNodes();
+}
+
+void QgsAlgorithmRemoveDuplicateNodes::initParameters( const QVariantMap & )
+{
+  addParameter( new QgsProcessingParameterNumber( QStringLiteral( "TOLERANCE" ),
+                QObject::tr( "Tolerance" ), QgsProcessingParameterNumber::Double,
+                0.000001, false, 0, 10000000.0 ) );
+  addParameter( new QgsProcessingParameterBoolean( QStringLiteral( "USE_Z_VALUE" ),
+                QObject::tr( "Use Z Value" ), false ) );
+}
+
+bool QgsAlgorithmRemoveDuplicateNodes::prepareAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback * )
+{
+  mTolerance = parameterAsDouble( parameters, QStringLiteral( "TOLERANCE" ), context );
+  mUseZValues = parameterAsBool( parameters, QStringLiteral( "USE_Z_VALUE" ), context );
+  return true;
+}
+
+QgsFeature QgsAlgorithmRemoveDuplicateNodes::processFeature( const QgsFeature &feature, QgsProcessingContext &, QgsProcessingFeedback * )
+{
+  QgsFeature f = feature;
+  if ( f.hasGeometry() )
+  {
+    QgsGeometry geometry = f.geometry();
+    geometry.removeDuplicateNodes( mTolerance, mUseZValues );
+    f.setGeometry( geometry );
+  }
+  return f;
+}
+
+///@endcond
+
+
diff --git a/src/analysis/processing/qgsalgorithmremoveduplicatenodes.h b/src/analysis/processing/qgsalgorithmremoveduplicatenodes.h
@@ -0,0 +1,62 @@
+/***************************************************************************
+                         qgsalgorithmremoveduplicatenodes.h
+                         ---------------------
+    begin                : November 2017
+    copyright            : (C) 2017 by Nyall Dawson
+    email                : nyall dot dawson at gmail dot com
+ ***************************************************************************/
+
+/***************************************************************************
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+#ifndef QGSALGORITHMREMOVEDUPLICATENODES_H
+#define QGSALGORITHMREMOVEDUPLICATENODES_H
+
+#define SIP_NO_FILE
+
+#include "qgis.h"
+#include "qgsprocessingalgorithm.h"
+
+///@cond PRIVATE
+
+/**
+ * Native remove duplicate nodes algorithm.
+ */
+class QgsAlgorithmRemoveDuplicateNodes : public QgsProcessingFeatureBasedAlgorithm
+{
+
+  public:
+
+    QgsAlgorithmRemoveDuplicateNodes() = default;
+    QString name() const override;
+    QString displayName() const override;
+    virtual QStringList tags() const override;
+    QString group() const override;
+    QString shortHelpString() const override;
+    QgsAlgorithmRemoveDuplicateNodes *createInstance() const override SIP_FACTORY;
+    void initParameters( const QVariantMap &configuration = QVariantMap() ) override;
+
+  protected:
+    QString outputName() const override;
+    bool prepareAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback ) override;
+    QgsFeature processFeature( const QgsFeature &feature,  QgsProcessingContext &, QgsProcessingFeedback *feedback ) override;
+
+  private:
+
+    double mTolerance = 1.0;
+    bool mUseZValues = false;
+
+};
+
+
+///@endcond PRIVATE
+
+#endif // QGSALGORITHMSIMPLIFY_H
+
+