Skip to content

Commit 2e8e72d

Browse files
nyalldawsonnyalldawson
committedOct 22, 2017
Optimise determination of adjacent vertices and move to QgsAbstractGeometry
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.
·
ltr-3_40final-3_0_0
1 parent 51fb665 commit 2e8e72d

21 files changed

+278
-111
lines changed
 

‎doc/api_break.dox

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1372,6 +1372,7 @@ QgsGeometryUtils {#qgis_api_break_3_0_QgsGeometryUtils}
13721372
----------------
13731373

13741374
- componentType enum has been renamed to ComponentType and its members were CamelCased too: VERTEX, RING and PART become Vertex, Ring and Part, respectively.
1375+
- adjacentVertices was removed - use QgsAbstractGeometry.adjacentVertices instead.
13751376

13761377

13771378
QgsGPSConnectionRegistry {#qgis_api_break_3_0_QgsGPSConnectionRegistry}

‎python/core/geometry/qgsabstractgeometry.sip

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -256,6 +256,12 @@ class QgsAbstractGeometry
256256
:rtype: bool
257257
%End
258258

259+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ ) = 0;
260+
%Docstring
261+
Returns the vertices adjacent to a specified ``vertex`` within a geometry.
262+
.. versionadded:: 3.0
263+
%End
264+
259265
virtual QgsCoordinateSequence coordinateSequence() const = 0;
260266
%Docstring
261267
Retrieves the sequence of geometries, rings and nodes.

‎python/core/geometry/qgscurve.sip

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,6 +102,8 @@ class QgsCurve: QgsAbstractGeometry
102102

103103
virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
104104

105+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
106+
105107

106108
virtual bool pointAt( int node, QgsPoint &point /Out/, QgsVertexId::VertexType &type /Out/ ) const = 0;
107109
%Docstring

‎python/core/geometry/qgscurvepolygon.sip

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -150,6 +150,7 @@ Adds an interior ring to the geometry (takes ownership)
150150

151151
virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
152152

153+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
153154

154155
virtual bool hasCurvedSegments() const;
155156

‎python/core/geometry/qgsgeometrycollection.sip

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,8 @@ class QgsGeometryCollection: QgsAbstractGeometry
5353

5454
virtual QgsAbstractGeometry *boundary() const /Factory/;
5555

56+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
57+
5658

5759
virtual bool addGeometry( QgsAbstractGeometry *g /Transfer/ );
5860
%Docstring

‎python/core/geometry/qgsgeometryutils.sip

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -74,11 +74,6 @@ class QgsGeometryUtils
7474
:rtype: bool
7575
%End
7676

77-
static void adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex /Out/, QgsVertexId &afterVertex /Out/ );
78-
%Docstring
79-
Returns vertices adjacent to a specified vertex within a geometry.
80-
%End
81-
8277
static double sqrDistance2D( const QgsPoint &pt1, const QgsPoint &pt2 );
8378
%Docstring
8479
Returns the squared 2D distance between two points.

‎python/core/geometry/qgspoint.sip

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -378,6 +378,8 @@ class QgsPoint: QgsAbstractGeometry
378378

379379
virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const;
380380

381+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex /Out/, QgsVertexId &nextVertex /Out/ );
382+
381383

382384
virtual double vertexAngle( QgsVertexId vertex ) const;
383385

‎src/core/geometry/qgsabstractgeometry.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -282,6 +282,12 @@ class CORE_EXPORT QgsAbstractGeometry
282282
*/
283283
virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const = 0;
284284

285+
/**
286+
* Returns the vertices adjacent to a specified \a vertex within a geometry.
287+
* \since QGIS 3.0
288+
*/
289+
virtual void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) = 0;
290+
285291
/**
286292
* Retrieves the sequence of geometries, rings and nodes.
287293
* \returns coordinate sequence

‎src/core/geometry/qgscurve.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,34 @@ bool QgsCurve::nextVertex( QgsVertexId &id, QgsPoint &vertex ) const
7878
return pointAt( id.vertex, vertex, id.type );
7979
}
8080

81+
void QgsCurve::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
82+
{
83+
int n = numPoints();
84+
if ( vertex.vertex < 0 || vertex.vertex >= n )
85+
{
86+
previousVertex = QgsVertexId();
87+
nextVertex = QgsVertexId();
88+
return;
89+
}
90+
91+
if ( vertex.vertex == 0 )
92+
{
93+
previousVertex = QgsVertexId();
94+
}
95+
else
96+
{
97+
previousVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex - 1 );
98+
}
99+
if ( vertex.vertex == n - 1 )
100+
{
101+
nextVertex = QgsVertexId();
102+
}
103+
else
104+
{
105+
nextVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex + 1 );
106+
}
107+
}
108+
81109
QgsAbstractGeometry *QgsCurve::boundary() const
82110
{
83111
if ( isEmpty() )

‎src/core/geometry/qgscurve.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,7 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry
103103

104104
QgsCoordinateSequence coordinateSequence() const override;
105105
bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
106+
void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
106107

107108
/**
108109
* Returns the point and vertex id of a point within the curve.

‎src/core/geometry/qgscurvepolygon.cpp

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -773,6 +773,61 @@ bool QgsCurvePolygon::nextVertex( QgsVertexId &vId, QgsPoint &vertex ) const
773773
}
774774
}
775775

776+
void ringAdjacentVertices( const QgsCurve *curve, QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
777+
{
778+
int n = curve->numPoints();
779+
if ( vertex.vertex < 0 || vertex.vertex >= n )
780+
{
781+
previousVertex = QgsVertexId();
782+
nextVertex = QgsVertexId();
783+
return;
784+
}
785+
786+
if ( vertex.vertex == 0 && n < 3 )
787+
{
788+
previousVertex = QgsVertexId();
789+
}
790+
else if ( vertex.vertex == 0 )
791+
{
792+
previousVertex = QgsVertexId( vertex.part, vertex.ring, n - 2 );
793+
}
794+
else
795+
{
796+
previousVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex - 1 );
797+
}
798+
if ( vertex.vertex == n - 1 && n < 3 )
799+
{
800+
nextVertex = QgsVertexId();
801+
}
802+
else if ( vertex.vertex == n - 1 )
803+
{
804+
nextVertex = QgsVertexId( vertex.part, vertex.ring, 1 );
805+
}
806+
else
807+
{
808+
nextVertex = QgsVertexId( vertex.part, vertex.ring, vertex.vertex + 1 );
809+
}
810+
}
811+
812+
void QgsCurvePolygon::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
813+
{
814+
if ( !mExteriorRing || vertex.ring < 0 || vertex.ring >= 1 + mInteriorRings.size() )
815+
{
816+
previousVertex = QgsVertexId();
817+
nextVertex = QgsVertexId();
818+
return;
819+
}
820+
821+
if ( vertex.ring == 0 )
822+
{
823+
ringAdjacentVertices( mExteriorRing.get(), vertex, previousVertex, nextVertex );
824+
}
825+
else
826+
{
827+
ringAdjacentVertices( mInteriorRings.at( vertex.ring - 1 ), vertex, previousVertex, nextVertex );
828+
}
829+
}
830+
776831
bool QgsCurvePolygon::insertVertex( QgsVertexId vId, const QgsPoint &vertex )
777832
{
778833
if ( !mExteriorRing || vId.ring < 0 || vId.ring >= 1 + mInteriorRings.size() )

‎src/core/geometry/qgscurvepolygon.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -122,7 +122,7 @@ class CORE_EXPORT QgsCurvePolygon: public QgsSurface
122122
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;
123123

124124
bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
125-
125+
void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
126126
bool hasCurvedSegments() const override;
127127

128128
/**

‎src/core/geometry/qgsgeometry.cpp

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -387,7 +387,7 @@ void QgsGeometry::adjacentVertices( int atVertex, int &beforeVertex, int &afterV
387387
}
388388

389389
QgsVertexId beforeVertexId, afterVertexId;
390-
QgsGeometryUtils::adjacentVertices( *( d->geometry ), id, beforeVertexId, afterVertexId );
390+
d->geometry->adjacentVertices( id, beforeVertexId, afterVertexId );
391391
beforeVertex = vertexNrFromVertexId( beforeVertexId );
392392
afterVertex = vertexNrFromVertexId( afterVertexId );
393393
}
@@ -1918,7 +1918,7 @@ double QgsGeometry::interpolateAngle( double distance ) const
19181918
QgsVertexId v2 = previous;
19191919
QgsVertexId v1;
19201920
QgsVertexId v3;
1921-
QgsGeometryUtils::adjacentVertices( *segmentized.geometry(), v2, v1, v3 );
1921+
segmentized.geometry()->adjacentVertices( v2, v1, v3 );
19221922
if ( v1.isValid() && v3.isValid() )
19231923
{
19241924
QgsPoint p1 = segmentized.geometry()->vertexAt( v1 );

‎src/core/geometry/qgsgeometrycollection.cpp

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,18 @@ QgsAbstractGeometry *QgsGeometryCollection::boundary() const
8080
return nullptr;
8181
}
8282

83+
void QgsGeometryCollection::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
84+
{
85+
if ( vertex.part < 0 || vertex.part >= mGeometries.count() )
86+
{
87+
previousVertex = QgsVertexId();
88+
nextVertex = QgsVertexId();
89+
return;
90+
}
91+
92+
mGeometries.at( vertex.part )->adjacentVertices( vertex, previousVertex, nextVertex );
93+
}
94+
8395
int QgsGeometryCollection::numGeometries() const
8496
{
8597
return mGeometries.size();

‎src/core/geometry/qgsgeometrycollection.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,7 @@ class CORE_EXPORT QgsGeometryCollection: public QgsAbstractGeometry
6565
QString geometryType() const override;
6666
void clear() override;
6767
QgsAbstractGeometry *boundary() const override SIP_FACTORY;
68+
void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
6869

6970
//! Adds a geometry and takes ownership. Returns true in case of success.
7071
virtual bool addGeometry( QgsAbstractGeometry *g SIP_TRANSFER );

‎src/core/geometry/qgsgeometryutils.cpp

Lines changed: 0 additions & 76 deletions
Original file line numberDiff line numberDiff line change
@@ -202,82 +202,6 @@ bool QgsGeometryUtils::verticesAtDistance( const QgsAbstractGeometry &geometry,
202202
return false;
203203
}
204204

205-
void QgsGeometryUtils::adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex, QgsVertexId &afterVertex )
206-
{
207-
bool polygonType = ( geom.dimension() == 2 );
208-
209-
QgsCoordinateSequence coords = geom.coordinateSequence();
210-
211-
//get feature
212-
if ( coords.size() <= atVertex.part )
213-
{
214-
return; //error, no such feature
215-
}
216-
217-
const QgsRingSequence &part = coords.at( atVertex.part );
218-
219-
//get ring
220-
if ( part.size() <= atVertex.ring )
221-
{
222-
return; //error, no such ring
223-
}
224-
const QgsPointSequence &ring = part.at( atVertex.ring );
225-
if ( ring.size() <= atVertex.vertex )
226-
{
227-
return;
228-
}
229-
230-
//vertex in the middle
231-
if ( atVertex.vertex > 0 && atVertex.vertex < ring.size() - 1 )
232-
{
233-
beforeVertex.part = atVertex.part;
234-
beforeVertex.ring = atVertex.ring;
235-
beforeVertex.vertex = atVertex.vertex - 1;
236-
afterVertex.part = atVertex.part;
237-
afterVertex.ring = atVertex.ring;
238-
afterVertex.vertex = atVertex.vertex + 1;
239-
}
240-
else if ( atVertex.vertex == 0 )
241-
{
242-
if ( ring.size() > 1 )
243-
{
244-
afterVertex.part = atVertex.part;
245-
afterVertex.ring = atVertex.ring;
246-
afterVertex.vertex = atVertex.vertex + 1;
247-
}
248-
else
249-
{
250-
afterVertex = QgsVertexId(); //after vertex invalid
251-
}
252-
if ( polygonType && ring.size() > 3 )
253-
{
254-
beforeVertex.part = atVertex.part;
255-
beforeVertex.ring = atVertex.ring;
256-
beforeVertex.vertex = ring.size() - 2;
257-
}
258-
else
259-
{
260-
beforeVertex = QgsVertexId(); //before vertex invalid
261-
}
262-
}
263-
else if ( atVertex.vertex == ring.size() - 1 )
264-
{
265-
beforeVertex.part = atVertex.part;
266-
beforeVertex.ring = atVertex.ring;
267-
beforeVertex.vertex = atVertex.vertex - 1;
268-
if ( polygonType )
269-
{
270-
afterVertex.part = atVertex.part;
271-
afterVertex.ring = atVertex.ring;
272-
afterVertex.vertex = 1;
273-
}
274-
else
275-
{
276-
afterVertex = QgsVertexId(); //after vertex invalid
277-
}
278-
}
279-
}
280-
281205
double QgsGeometryUtils::sqrDistance2D( const QgsPoint &pt1, const QgsPoint &pt2 )
282206
{
283207
return ( pt1.x() - pt2.x() ) * ( pt1.x() - pt2.x() ) + ( pt1.y() - pt2.y() ) * ( pt1.y() - pt2.y() );

‎src/core/geometry/qgsgeometryutils.h

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -79,11 +79,6 @@ class CORE_EXPORT QgsGeometryUtils
7979
QgsVertexId &previousVertex SIP_OUT,
8080
QgsVertexId &nextVertex SIP_OUT );
8181

82-
/**
83-
* Returns vertices adjacent to a specified vertex within a geometry.
84-
*/
85-
static void adjacentVertices( const QgsAbstractGeometry &geom, QgsVertexId atVertex, QgsVertexId &beforeVertex SIP_OUT, QgsVertexId &afterVertex SIP_OUT );
86-
8782
/**
8883
* Returns the squared 2D distance between two points.
8984
*/

‎src/core/geometry/qgspoint.cpp

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -393,6 +393,12 @@ bool QgsPoint::nextVertex( QgsVertexId &id, QgsPoint &vertex ) const
393393
}
394394
}
395395

396+
void QgsPoint::adjacentVertices( QgsVertexId, QgsVertexId &previousVertex, QgsVertexId &nextVertex )
397+
{
398+
previousVertex = QgsVertexId();
399+
nextVertex = QgsVertexId();
400+
}
401+
396402
double QgsPoint::vertexAngle( QgsVertexId vertex ) const
397403
{
398404
Q_UNUSED( vertex );

‎src/core/geometry/qgspoint.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -414,6 +414,7 @@ class CORE_EXPORT QgsPoint: public QgsAbstractGeometry
414414

415415
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;
416416
bool nextVertex( QgsVertexId &id, QgsPoint &vertex SIP_OUT ) const override;
417+
void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
417418

418419
/**
419420
* Angle undefined. Always returns 0.0

0 commit comments

Comments
 (0)
Please sign in to comment.