Optimise determination of adjacent vertices and move to QgsAbstractGe…

…ometry Previously the method in QgsGeometryUtils was relying on QgsAbstractGeometry::coordinateSequence, which is an absolute performance killer. Instead move to optimised methods in the various abstract geometry subclasses which rely only on trivial calculations.
qgis · Oct 22, 2017 · 2e8e72d · 2e8e72d
1 parent 51fb665
commit 2e8e72d
Show file tree

Hide file tree

Showing 21 changed files with 278 additions and 111 deletions.
diff --git a/doc/api_break.dox b/doc/api_break.dox
@@ -1372,6 +1372,7 @@ QgsGeometryUtils         {#qgis_api_break_3_0_QgsGeometryUtils}
 ----------------
 
 - componentType enum has been renamed to ComponentType and its members were CamelCased too: VERTEX, RING and PART become Vertex, Ring and Part, respectively.
+- adjacentVertices was removed - use QgsAbstractGeometry.adjacentVertices instead.
 
 
 QgsGPSConnectionRegistry        {#qgis_api_break_3_0_QgsGPSConnectionRegistry}

diff --git a/python/core/geometry/qgsabstractgeometry.sip b/python/core/geometry/qgsabstractgeometry.sip
@@ -256,6 +256,12 @@ class QgsAbstractGeometry
  :rtype: bool
 %End
 
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ ) = 0;
+%Docstring
+ Returns the vertices adjacent to a specified ``vertex`` within a geometry.
+.. versionadded:: 3.0
+%End
+
     virtual QgsCoordinateSequence coordinateSequence() const = 0;
 %Docstring
  Retrieves the sequence of geometries, rings and nodes.

diff --git a/python/core/geometry/qgscurve.sip b/python/core/geometry/qgscurve.sip
@@ -102,6 +102,8 @@ class QgsCurve: QgsAbstractGeometry
 
     virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
 
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
+
 
     virtual bool pointAt( int node, QgsPoint &point /Out/, QgsVertexId::VertexType &type /Out/ ) const = 0;
 %Docstring

diff --git a/python/core/geometry/qgscurvepolygon.sip b/python/core/geometry/qgscurvepolygon.sip
@@ -150,6 +150,7 @@ Adds an interior ring to the geometry (takes ownership)
 
     virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
 
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
 
     virtual bool hasCurvedSegments() const;
 

diff --git a/python/core/geometry/qgsgeometrycollection.sip b/python/core/geometry/qgsgeometrycollection.sip
@@ -53,6 +53,8 @@ class QgsGeometryCollection: QgsAbstractGeometry
 
     virtual QgsAbstractGeometry *boundary() const /Factory/;
 
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
+
 
     virtual bool addGeometry( QgsAbstractGeometry *g /Transfer/ );
 %Docstring

diff --git a/python/core/geometry/qgsgeometryutils.sip b/python/core/geometry/qgsgeometryutils.sip
@@ -74,11 +74,6 @@ class QgsGeometryUtils
  :rtype: bool
 %End
 
-    static void adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex /Out/, QgsVertexId &afterVertex /Out/ );
-%Docstring
- Returns vertices adjacent to a specified vertex within a geometry.
-%End
-
     static double sqrDistance2D( const QgsPoint &pt1, const QgsPoint &pt2 );
 %Docstring
  Returns the squared 2D distance between two points.

diff --git a/python/core/geometry/qgspoint.sip b/python/core/geometry/qgspoint.sip
@@ -378,6 +378,8 @@ class QgsPoint: QgsAbstractGeometry
 
     virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
 
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
+
 
     virtual double vertexAngle( QgsVertexId vertex ) const;
 

diff --git a/src/core/geometry/qgsabstractgeometry.h b/src/core/geometry/qgsabstractgeometry.h
@@ -282,6 +282,12 @@ class CORE_EXPORT QgsAbstractGeometry
      */
     virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const = 0;
 
+    /**
+     * Returns the vertices adjacent to a specified \a vertex within a geometry.
+     * \since QGIS 3.0
+     */
+    virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) = 0;
+
     /**
      * Retrieves the sequence of geometries, rings and nodes.
      * \returns coordinate sequence

diff --git a/src/core/geometry/qgscurve.cpp b/src/core/geometry/qgscurve.cpp
@@ -78,6 +78,34 @@ bool QgsCurve::nextVertex( QgsVertexId &id, QgsPoint &vertex ) const
   return pointAt( id.vertex, vertex, id.type );
 }
 
+void QgsCurve::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
+{
+  int n = numPoints();
+  if ( vertex.vertex < 0 || vertex.vertex >= n )
+  {
+    previousVertex = QgsVertexId();
+    nextVertex = QgsVertexId();
+    return;
+  }
+
+  if ( vertex.vertex == 0 )
+  {
+    previousVertex = QgsVertexId();
+  }
+  else
+  {
+    previousVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex - 1 );
+  }
+  if ( vertex.vertex == n - 1 )
+  {
+    nextVertex = QgsVertexId();
+  }
+  else
+  {
+    nextVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex + 1 );
+  }
+}
+
 QgsAbstractGeometry *QgsCurve::boundary() const
 {
   if ( isEmpty() )

diff --git a/src/core/geometry/qgscurve.h b/src/core/geometry/qgscurve.h
@@ -103,6 +103,7 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry
 
     QgsCoordinateSequence coordinateSequence() const override;
     bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
+    void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
 
     /**
      * Returns the point and vertex id of a point within the curve.

diff --git a/src/core/geometry/qgscurvepolygon.cpp b/src/core/geometry/qgscurvepolygon.cpp
@@ -773,6 +773,61 @@ bool QgsCurvePolygon::nextVertex( QgsVertexId &vId, QgsPoint &vertex ) const
   }
 }
 
+void ringAdjacentVertices( const QgsCurve *curve, QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
+{
+  int n = curve->numPoints();
+  if ( vertex.vertex < 0 || vertex.vertex >= n )
+  {
+    previousVertex = QgsVertexId();
+    nextVertex = QgsVertexId();
+    return;
+  }
+
+  if ( vertex.vertex == 0 && n < 3 )
+  {
+    previousVertex = QgsVertexId();
+  }
+  else if ( vertex.vertex == 0 )
+  {
+    previousVertex = QgsVertexId( vertex.part, vertex.ring, n - 2 );
+  }
+  else
+  {
+    previousVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex - 1 );
+  }
+  if ( vertex.vertex == n - 1 && n < 3 )
+  {
+    nextVertex = QgsVertexId();
+  }
+  else if ( vertex.vertex == n - 1 )
+  {
+    nextVertex = QgsVertexId( vertex.part, vertex.ring, 1 );
+  }
+  else
+  {
+    nextVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex + 1 );
+  }
+}
+
+void QgsCurvePolygon::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
+{
+  if ( !mExteriorRing || vertex.ring < 0 || vertex.ring >= 1 + mInteriorRings.size() )
+  {
+    previousVertex = QgsVertexId();
+    nextVertex = QgsVertexId();
+    return;
+  }
+
+  if ( vertex.ring == 0 )
+  {
+    ringAdjacentVertices( mExteriorRing.get(), vertex, previousVertex, nextVertex );
+  }
+  else
+  {
+    ringAdjacentVertices( mInteriorRings.at( vertex.ring - 1 ), vertex, previousVertex, nextVertex );
+  }
+}
+
 bool QgsCurvePolygon::insertVertex( QgsVertexId vId, const QgsPoint &vertex )
 {
   if ( !mExteriorRing || vId.ring < 0 || vId.ring >= 1 + mInteriorRings.size() )

diff --git a/src/core/geometry/qgscurvepolygon.h b/src/core/geometry/qgscurvepolygon.h
@@ -122,7 +122,7 @@ class CORE_EXPORT QgsCurvePolygon: public QgsSurface
     double closestSegment( const QgsPoint &pt, QgsPoint &segmentPt SIP_OUT, QgsVertexId &vertexAfter SIP_OUT, bool *leftOf SIP_OUT = nullptr, double epsilon = 4 * DBL_EPSILON ) const override;
 
     bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
-
+    void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
     bool hasCurvedSegments() const override;
 
     /**

diff --git a/src/core/geometry/qgsgeometry.cpp b/src/core/geometry/qgsgeometry.cpp
@@ -387,7 +387,7 @@ void QgsGeometry::adjacentVertices( int atVertex, int &beforeVertex, int &afterV
   }
 
   QgsVertexId beforeVertexId, afterVertexId;
-  QgsGeometryUtils::adjacentVertices( *( d->geometry ), id, beforeVertexId, afterVertexId );
+  d->geometry->adjacentVertices( id, beforeVertexId, afterVertexId );
   beforeVertex = vertexNrFromVertexId( beforeVertexId );
   afterVertex = vertexNrFromVertexId( afterVertexId );
 }
@@ -1918,7 +1918,7 @@ double QgsGeometry::interpolateAngle( double distance ) const
     QgsVertexId v2 = previous;
     QgsVertexId v1;
     QgsVertexId v3;
-    QgsGeometryUtils::adjacentVertices( *segmentized.geometry(), v2, v1, v3 );
+    segmentized.geometry()->adjacentVertices( v2, v1, v3 );
     if ( v1.isValid() && v3.isValid() )
     {
       QgsPoint p1 = segmentized.geometry()->vertexAt( v1 );

diff --git a/src/core/geometry/qgsgeometrycollection.cpp b/src/core/geometry/qgsgeometrycollection.cpp
@@ -80,6 +80,18 @@ QgsAbstractGeometry *QgsGeometryCollection::boundary() const
   return nullptr;
 }
 
+void QgsGeometryCollection::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
+{
+  if ( vertex.part < 0 || vertex.part >= mGeometries.count() )
+  {
+    previousVertex = QgsVertexId();
+    nextVertex = QgsVertexId();
+    return;
+  }
+
+  mGeometries.at( vertex.part )->adjacentVertices( vertex, previousVertex, nextVertex );
+}
+
 int QgsGeometryCollection::numGeometries() const
 {
   return mGeometries.size();

diff --git a/src/core/geometry/qgsgeometrycollection.h b/src/core/geometry/qgsgeometrycollection.h
@@ -65,6 +65,7 @@ class CORE_EXPORT QgsGeometryCollection: public QgsAbstractGeometry
     QString geometryType() const override;
     void clear() override;
     QgsAbstractGeometry *boundary() const override SIP_FACTORY;
+    void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
 
     //! Adds a geometry and takes ownership. Returns true in case of success.
     virtual bool addGeometry( QgsAbstractGeometry *g SIP_TRANSFER );

diff --git a/src/core/geometry/qgsgeometryutils.cpp b/src/core/geometry/qgsgeometryutils.cpp
@@ -202,82 +202,6 @@ bool QgsGeometryUtils::verticesAtDistance( const QgsAbstractGeometry &geometry,
   return false;
 }
 
-void QgsGeometryUtils::adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex, QgsVertexId &afterVertex )
-{
-  bool polygonType = ( geom.dimension()  == 2 );
-
-  QgsCoordinateSequence coords = geom.coordinateSequence();
-
-  //get feature
-  if ( coords.size() <= atVertex.part )
-  {
-    return; //error, no such feature
-  }
-
-  const QgsRingSequence &part = coords.at( atVertex.part );
-
-  //get ring
-  if ( part.size() <= atVertex.ring )
-  {
-    return; //error, no such ring
-  }
-  const QgsPointSequence &ring = part.at( atVertex.ring );
-  if ( ring.size() <= atVertex.vertex )
-  {
-    return;
-  }
-
-  //vertex in the middle
-  if ( atVertex.vertex > 0 && atVertex.vertex < ring.size() - 1 )
-  {
-    beforeVertex.part = atVertex.part;
-    beforeVertex.ring = atVertex.ring;
-    beforeVertex.vertex = atVertex.vertex - 1;
-    afterVertex.part = atVertex.part;
-    afterVertex.ring = atVertex.ring;
-    afterVertex.vertex = atVertex.vertex + 1;
-  }
-  else if ( atVertex.vertex == 0 )
-  {
-    if ( ring.size() > 1 )
-    {
-      afterVertex.part = atVertex.part;
-      afterVertex.ring = atVertex.ring;
-      afterVertex.vertex = atVertex.vertex + 1;
-    }
-    else
-    {
-      afterVertex = QgsVertexId(); //after vertex invalid
-    }
-    if ( polygonType && ring.size() > 3 )
-    {
-      beforeVertex.part = atVertex.part;
-      beforeVertex.ring = atVertex.ring;
-      beforeVertex.vertex = ring.size() - 2;
-    }
-    else
-    {
-      beforeVertex = QgsVertexId(); //before vertex invalid
-    }
-  }
-  else if ( atVertex.vertex == ring.size() - 1 )
-  {
-    beforeVertex.part = atVertex.part;
-    beforeVertex.ring = atVertex.ring;
-    beforeVertex.vertex = atVertex.vertex - 1;
-    if ( polygonType )
-    {
-      afterVertex.part = atVertex.part;
-      afterVertex.ring = atVertex.ring;
-      afterVertex.vertex = 1;
-    }
-    else
-    {
-      afterVertex = QgsVertexId(); //after vertex invalid
-    }
-  }
-}
-
 double QgsGeometryUtils::sqrDistance2D( const QgsPoint &pt1, const QgsPoint &pt2 )
 {
   return ( pt1.x() - pt2.x() ) * ( pt1.x() - pt2.x() ) + ( pt1.y() - pt2.y() ) * ( pt1.y() - pt2.y() );

diff --git a/src/core/geometry/qgsgeometryutils.h b/src/core/geometry/qgsgeometryutils.h
@@ -79,11 +79,6 @@ class CORE_EXPORT QgsGeometryUtils
                                     QgsVertexId &previousVertex SIP_OUT,
                                     QgsVertexId &nextVertex SIP_OUT );
 
-    /**
-     * Returns vertices adjacent to a specified vertex within a geometry.
-     */
-    static void adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex SIP_OUT, QgsVertexId &afterVertex SIP_OUT );
-
     /**
      * Returns the squared 2D distance between two points.
      */

diff --git a/src/core/geometry/qgspoint.cpp b/src/core/geometry/qgspoint.cpp
@@ -393,6 +393,12 @@ bool QgsPoint::nextVertex( QgsVertexId &id, QgsPoint &vertex ) const
   }
 }
 
+void QgsPoint::adjacentVertices( QgsVertexId, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
+{
+  previousVertex = QgsVertexId();
+  nextVertex = QgsVertexId();
+}
+
 double QgsPoint::vertexAngle( QgsVertexId vertex ) const
 {
   Q_UNUSED( vertex );

diff --git a/src/core/geometry/qgspoint.h b/src/core/geometry/qgspoint.h
@@ -414,6 +414,7 @@ class CORE_EXPORT QgsPoint: public QgsAbstractGeometry
 
     double closestSegment( const QgsPoint &pt, QgsPoint &segmentPt SIP_OUT, QgsVertexId &vertexAfter SIP_OUT, bool *leftOf SIP_OUT = nullptr, double epsilon = 4 * DBL_EPSILON ) const override;
     bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
+    void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
 
     /**
      * Angle undefined. Always returns 0.0