Add QgsGeometry::normalize()

A port of the equivalent method from GEOS, but with added support for curved geometries and M values Reorganizes the geometry into a normalized form (or "canonical" form). Polygon rings will be rearranged so that their starting vertex is the lower left and ring orientation follows the right hand rule, collections are ordered by geometry type, and other normalization techniques are applied. The resultant geometry will be geometrically equivalent to the original geometry.
qgis · Apr 28, 2021 · 1c11a91 · 1c11a91
1 parent e3a73a1
commit 1c11a91
Show file tree

Hide file tree

Showing 24 changed files with 194 additions and 32 deletions.
diff --git a/python/core/auto_generated/geometry/qgsabstractgeometry.sip.in b/python/core/auto_generated/geometry/qgsabstractgeometry.sip.in
@@ -179,6 +179,17 @@ For instance, a polygon geometry will have a boundary consisting of the linestri
 .. versionadded:: 3.0
 %End
 
+    virtual void normalize() = 0;
+%Docstring
+Reorganizes the geometry into a normalized form (or "canonical" form).
+
+Polygon rings will be rearranged so that their starting vertex is the lower left and ring orientation follows the
+right hand rule, collections are ordered by geometry type, and other normalization techniques are applied. The
+resultant geometry will be geometrically equivalent to the original geometry.
+
+.. versionadded:: 3.20
+%End
+
 
     virtual bool fromWkb( QgsConstWkbPtr &wkb ) = 0;
 %Docstring

diff --git a/python/core/auto_generated/geometry/qgscircularstring.sip.in b/python/core/auto_generated/geometry/qgscircularstring.sip.in
@@ -203,6 +203,7 @@ Appends the contents of another circular ``string`` to the end of this circular
 
     virtual bool transform( QgsAbstractGeometryTransformer *transformer, QgsFeedback *feedback = 0 );
 
+    void scroll( int firstVertexIndex ) final;
 
 
     virtual QgsCircularString *createEmptyWithSameType() const /Factory/;
@@ -222,7 +223,6 @@ Appends the contents of another circular ``string`` to the end of this circular
     int compareToSameClass( const QgsAbstractGeometry *other ) const final;
     virtual QgsRectangle calculateBoundingBox() const;
 
-    void scroll( int firstVertexIndex ) final;
 
 };
 

diff --git a/python/core/auto_generated/geometry/qgscompoundcurve.sip.in b/python/core/auto_generated/geometry/qgscompoundcurve.sip.in
@@ -187,6 +187,7 @@ Appends first point if not already closed.
 
     virtual bool transform( QgsAbstractGeometryTransformer *transformer, QgsFeedback *feedback = 0 );
 
+    void scroll( int firstVertexIndex ) final;
 
 
     virtual QgsCompoundCurve *createEmptyWithSameType() const /Factory/;
@@ -206,7 +207,6 @@ Appends first point if not already closed.
     int compareToSameClass( const QgsAbstractGeometry *other ) const final;
     virtual QgsRectangle calculateBoundingBox() const;
 
-    void scroll( int firstVertexIndex ) final;
 
 };
 

diff --git a/python/core/auto_generated/geometry/qgscurve.sip.in b/python/core/auto_generated/geometry/qgscurve.sip.in
@@ -191,6 +191,7 @@ Returns a geometry without curves. Caller takes ownership
 
     virtual QgsCurve *toCurveType() const /Factory/;
 
+    void normalize() final /HoldGIL/;
 
     virtual QgsRectangle boundingBox() const;
 
@@ -284,18 +285,6 @@ Returns the curve's orientation, e.g. clockwise or counter-clockwise.
 .. versionadded:: 3.6
 %End
 
-
-
-  protected:
-
-    virtual void clearCache() const;
-
-
-    virtual int childCount() const;
-
-    virtual QgsPoint childPoint( int index ) const;
-
-
     virtual void scroll( int firstVertexIndex ) = 0;
 %Docstring
 Scrolls the curve vertices so that they start with the vertex at the given index.
@@ -316,6 +305,17 @@ Scrolls the curve vertices so that they start with the vertex at the given index
 
 
 
+  protected:
+
+    virtual void clearCache() const;
+
+
+    virtual int childCount() const;
+
+    virtual QgsPoint childPoint( int index ) const;
+
+
+
 };
 
 /************************************************************************

diff --git a/python/core/auto_generated/geometry/qgscurvepolygon.sip.in b/python/core/auto_generated/geometry/qgscurvepolygon.sip.in
@@ -58,6 +58,7 @@ Curve polygon geometry type
 
     virtual QString asKml( int precision = 17 ) const;
 
+    void normalize() final /HoldGIL/;
 
     virtual double area() const /HoldGIL/;
 

diff --git a/python/core/auto_generated/geometry/qgsgeometry.sip.in b/python/core/auto_generated/geometry/qgsgeometry.sip.in
@@ -2027,6 +2027,17 @@ The ``method`` argument dictates which validator to utilize.
 The ``flags`` parameter indicates optional flags which control the type of validity checking performed.
 
 .. versionadded:: 1.5
+%End
+
+    void normalize();
+%Docstring
+Reorganizes the geometry into a normalized form (or "canonical" form).
+
+Polygon rings will be rearranged so that their starting vertex is the lower left and ring orientation follows the
+right hand rule, collections are ordered by geometry type, and other normalization techniques are applied. The
+resultant geometry will be geometrically equivalent to the original geometry.
+
+.. versionadded:: 3.20
 %End
 
     static QgsGeometry unaryUnion( const QVector<QgsGeometry> &geometries );

diff --git a/python/core/auto_generated/geometry/qgsgeometrycollection.sip.in b/python/core/auto_generated/geometry/qgsgeometrycollection.sip.in
@@ -150,6 +150,7 @@ An IndexError will be raised if no geometry with the specified index exists.
     }
 %End
 
+    void normalize() final /HoldGIL/;
     virtual void transform( const QgsCoordinateTransform &ct, QgsCoordinateTransform::TransformDirection d = QgsCoordinateTransform::ForwardTransform, bool transformZ = false ) throw( QgsCsException );
 
     virtual void transform( const QTransform &t, double zTranslate = 0.0, double zScale = 1.0, double mTranslate = 0.0, double mScale = 1.0 );

diff --git a/python/core/auto_generated/geometry/qgslinestring.sip.in b/python/core/auto_generated/geometry/qgslinestring.sip.in
@@ -553,6 +553,7 @@ of the curve.
 
     virtual bool transform( QgsAbstractGeometryTransformer *transformer, QgsFeedback *feedback = 0 );
 
+    void scroll( int firstVertexIndex ) final;
 
 
     virtual QgsLineString *createEmptyWithSameType() const /Factory/;
@@ -652,7 +653,6 @@ corresponds to the last point in the line.
     int compareToSameClass( const QgsAbstractGeometry *other ) const final;
     virtual QgsRectangle calculateBoundingBox() const;
 
-    void scroll( int firstVertexIndex ) final;
 
 };
 

diff --git a/python/core/auto_generated/geometry/qgspoint.sip.in b/python/core/auto_generated/geometry/qgspoint.sip.in
@@ -349,6 +349,7 @@ Example
 
     QgsPoint operator-( QgsVector v ) const /HoldGIL/;
 
+    void normalize() final /HoldGIL/;
     virtual bool isEmpty() const /HoldGIL/;
 
     virtual QgsRectangle boundingBox() const /HoldGIL/;

diff --git a/src/core/geometry/qgsabstractgeometry.h b/src/core/geometry/qgsabstractgeometry.h
@@ -235,6 +235,17 @@ class CORE_EXPORT QgsAbstractGeometry
      */
     virtual QgsAbstractGeometry *boundary() const = 0 SIP_FACTORY;
 
+    /**
+     * Reorganizes the geometry into a normalized form (or "canonical" form).
+     *
+     * Polygon rings will be rearranged so that their starting vertex is the lower left and ring orientation follows the
+     * right hand rule, collections are ordered by geometry type, and other normalization techniques are applied. The
+     * resultant geometry will be geometrically equivalent to the original geometry.
+     *
+     * \since QGIS 3.20
+     */
+    virtual void normalize() = 0;
+
     //import
 
     /**

diff --git a/src/core/geometry/qgscircularstring.h b/src/core/geometry/qgscircularstring.h
@@ -163,6 +163,7 @@ class CORE_EXPORT QgsCircularString: public QgsCurve
     double yAt( int index ) const override SIP_HOLDGIL;
 
     bool transform( QgsAbstractGeometryTransformer *transformer, QgsFeedback *feedback = nullptr ) override;
+    void scroll( int firstVertexIndex ) final;
 
 #ifndef SIP_RUN
     void filterVertices( const std::function< bool( const QgsPoint & ) > &filter ) override;
@@ -201,7 +202,6 @@ class CORE_EXPORT QgsCircularString: public QgsCurve
 
     int compareToSameClass( const QgsAbstractGeometry *other ) const final;
     QgsRectangle calculateBoundingBox() const override;
-    void scroll( int firstVertexIndex ) final;
 
   private:
     QVector<double> mX;

diff --git a/src/core/geometry/qgscompoundcurve.h b/src/core/geometry/qgscompoundcurve.h
@@ -148,6 +148,7 @@ class CORE_EXPORT QgsCompoundCurve: public QgsCurve
     double yAt( int index ) const override SIP_HOLDGIL;
 
     bool transform( QgsAbstractGeometryTransformer *transformer, QgsFeedback *feedback = nullptr ) override;
+    void scroll( int firstVertexIndex ) final;
 
 #ifndef SIP_RUN
     void filterVertices( const std::function< bool( const QgsPoint & ) > &filter ) override;
@@ -186,7 +187,6 @@ class CORE_EXPORT QgsCompoundCurve: public QgsCurve
 
     int compareToSameClass( const QgsAbstractGeometry *other ) const final;
     QgsRectangle calculateBoundingBox() const override;
-    void scroll( int firstVertexIndex ) final;
 
   private:
     QVector< QgsCurve * > mCurves;

diff --git a/src/core/geometry/qgscurve.cpp b/src/core/geometry/qgscurve.cpp
@@ -199,6 +199,33 @@ QgsCurve *QgsCurve::toCurveType() const
   return clone();
 }
 
+void QgsCurve::normalize()
+{
+  if ( isEmpty() )
+    return;
+
+  if ( !isClosed() )
+  {
+    return;
+  }
+
+  int minCoordinateIndex = 0;
+  QgsPoint minCoord;
+  int i = 0;
+  for ( auto it = vertices_begin(); it != vertices_end(); ++it )
+  {
+    const QgsPoint vertex = *it;
+    if ( minCoord.isEmpty() || minCoord.compareTo( &vertex ) > 0 )
+    {
+      minCoord = vertex;
+      minCoordinateIndex = i;
+    }
+    i++;
+  }
+
+  scroll( minCoordinateIndex );
+}
+
 QgsRectangle QgsCurve::boundingBox() const
 {
   if ( mBoundingBox.isNull() )

diff --git a/src/core/geometry/qgscurve.h b/src/core/geometry/qgscurve.h
@@ -176,6 +176,7 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry SIP_ABSTRACT
     int partCount() const override;
     QgsPoint vertexAt( QgsVertexId id ) const override;
     QgsCurve *toCurveType() const override SIP_FACTORY;
+    void normalize() final SIP_HOLDGIL;
 
     QgsRectangle boundingBox() const override;
     bool isValid( QString &error SIP_OUT, int flags = 0 ) const override;
@@ -262,6 +263,19 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry SIP_ABSTRACT
      */
     Orientation orientation() const;
 
+    /**
+     * Scrolls the curve vertices so that they start with the vertex at the given index.
+     *
+     * \warning This should only be called on closed curves, or the shape of the curve will be altered and
+     * the result is undefined.
+     *
+     * \warning The \a firstVertexIndex must correspond to a segment vertex and not a curve point or the result
+     * is undefined.
+     *
+     * \since QGIS 3.20
+     */
+    virtual void scroll( int firstVertexIndex ) = 0;
+
 #ifndef SIP_RUN
 
     /**
@@ -305,20 +319,6 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry SIP_ABSTRACT
 
     int childCount() const override;
     QgsPoint childPoint( int index ) const override;
-
-    /**
-     * Scrolls the curve vertices so that they start with the vertex at the given index.
-     *
-     * \warning This should only be called on closed curves, or the shape of the curve will be altered and
-     * the result is undefined.
-     *
-     * \warning The \a firstVertexIndex must correspond to a segment vertex and not a curve point or the result
-     * is undefined.
-     *
-     * \since QGIS 3.20
-     */
-    virtual void scroll( int firstVertexIndex ) = 0;
-
 #ifndef SIP_RUN
 
     /**

diff --git a/src/core/geometry/qgscurvepolygon.cpp b/src/core/geometry/qgscurvepolygon.cpp
@@ -464,6 +464,27 @@ QString QgsCurvePolygon::asKml( int precision ) const
   return kml;
 }
 
+void QgsCurvePolygon::normalize()
+{
+  // normalize rings
+  if ( mExteriorRing )
+    mExteriorRing->normalize();
+
+  for ( QgsCurve *ring : std::as_const( mInteriorRings ) )
+  {
+    ring->normalize();
+  }
+
+  // sort rings
+  std::sort( mInteriorRings.begin(), mInteriorRings.end(), []( const QgsCurve * a, const QgsCurve * b )
+  {
+    return a->compareTo( b ) > 0;
+  } );
+
+  // normalize ring orientation
+  forceRHR();
+}
+
 double QgsCurvePolygon::area() const
 {
   if ( !mExteriorRing )

diff --git a/src/core/geometry/qgscurvepolygon.h b/src/core/geometry/qgscurvepolygon.h
@@ -58,6 +58,7 @@ class CORE_EXPORT QgsCurvePolygon: public QgsSurface
     QDomElement asGml3( QDomDocument &doc, int precision = 17, const QString &ns = "gml", QgsAbstractGeometry::AxisOrder axisOrder = QgsAbstractGeometry::AxisOrder::XY ) const override;
     json asJsonObject( int precision = 17 ) const override SIP_SKIP;
     QString asKml( int precision = 17 ) const override;
+    void normalize() final SIP_HOLDGIL;
 
     //surface interface
     double area() const override SIP_HOLDGIL;

diff --git a/src/core/geometry/qgsgeometry.cpp b/src/core/geometry/qgsgeometry.cpp
@@ -2717,6 +2717,17 @@ void QgsGeometry::validateGeometry( QVector<QgsGeometry::Error> &errors, const V
   }
 }
 
+void QgsGeometry::normalize()
+{
+  if ( !d->geometry )
+  {
+    return;
+  }
+
+  detach();
+  d->geometry->normalize();
+}
+
 bool QgsGeometry::isGeosValid( const QgsGeometry::ValidityFlags flags ) const
 {
   if ( !d->geometry )

diff --git a/src/core/geometry/qgsgeometry.h b/src/core/geometry/qgsgeometry.h
@@ -2140,6 +2140,17 @@ class CORE_EXPORT QgsGeometry
      */
     void validateGeometry( QVector<QgsGeometry::Error> &errors SIP_OUT, ValidationMethod method = ValidatorQgisInternal, QgsGeometry::ValidityFlags flags = QgsGeometry::ValidityFlags() ) const;
 
+    /**
+     * Reorganizes the geometry into a normalized form (or "canonical" form).
+     *
+     * Polygon rings will be rearranged so that their starting vertex is the lower left and ring orientation follows the
+     * right hand rule, collections are ordered by geometry type, and other normalization techniques are applied. The
+     * resultant geometry will be geometrically equivalent to the original geometry.
+     *
+     * \since QGIS 3.20
+     */
+    void normalize();
+
     /**
      * Compute the unary union on a list of \a geometries. May be faster than an iterative union on a set of geometries.
      * The returned geometry will be fully noded, i.e. a node will be created at every common intersection of the

diff --git a/src/core/geometry/qgsgeometrycollection.cpp b/src/core/geometry/qgsgeometrycollection.cpp
@@ -291,6 +291,18 @@ bool QgsGeometryCollection::removeGeometry( int nr )
   return true;
 }
 
+void QgsGeometryCollection::normalize()
+{
+  for ( QgsAbstractGeometry *geometry : std::as_const( mGeometries ) )
+  {
+    geometry->normalize();
+  }
+  std::sort( mGeometries.begin(), mGeometries.end(), []( const QgsAbstractGeometry * a, const QgsAbstractGeometry * b )
+  {
+    return a->compareTo( b ) > 0;
+  } );
+}
+
 int QgsGeometryCollection::dimension() const
 {
   int maxDim = 0;

diff --git a/src/core/geometry/qgsgeometrycollection.h b/src/core/geometry/qgsgeometrycollection.h
@@ -179,6 +179,7 @@ class CORE_EXPORT QgsGeometryCollection: public QgsAbstractGeometry
     % End
 #endif
 
+    void normalize() final SIP_HOLDGIL;
     void transform( const QgsCoordinateTransform &ct, QgsCoordinateTransform::TransformDirection d = QgsCoordinateTransform::ForwardTransform, bool transformZ = false ) override SIP_THROW( QgsCsException );
     void transform( const QTransform &t, double zTranslate = 0.0, double zScale = 1.0, double mTranslate = 0.0, double mScale = 1.0 ) override;