Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Optimise calculation of QgsGeometry::vertexNrFromVertexId
By moving logic to abstract geometry subclasses so that they
can trivially retrieve the vertex number, instead of relying
on the inefficient coordinateSequence method.

Has flow on speed boosts to many geometry operations like
calculation of closest points in a geometry, which will
benefit snapping related operations.
  • Loading branch information
nyalldawson committed Oct 22, 2017
1 parent 2e8e72d commit 5d67572
Show file tree
Hide file tree
Showing 21 changed files with 315 additions and 44 deletions.
13 changes: 13 additions & 0 deletions python/core/geometry/qgsabstractgeometry.sip
Expand Up @@ -246,6 +246,19 @@ class QgsAbstractGeometry
\param p destination QPainter
%End

virtual int vertexNumberFromVertexId( QgsVertexId id ) const = 0;
%Docstring
Returns the vertex number corresponding to a vertex ``id``.

The vertex numbers start at 0, so a return value of 0 corresponds
to the first vertex.

Returns -1 if a corresponding vertex could not be found.

.. versionadded:: 3.0
:rtype: int
%End

virtual bool nextVertex( QgsVertexId &id, QgsPoint &vertex /Out/ ) const = 0;
%Docstring
Returns next vertex id and coordinates
Expand Down
2 changes: 2 additions & 0 deletions python/core/geometry/qgscurve.sip
Expand Up @@ -104,6 +104,8 @@ class QgsCurve: QgsAbstractGeometry

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

virtual int vertexNumberFromVertexId( QgsVertexId id ) const;


virtual bool pointAt( int node, QgsPoint &point /Out/, QgsVertexId::VertexType &type /Out/ ) const = 0;
%Docstring
Expand Down
2 changes: 2 additions & 0 deletions python/core/geometry/qgscurvepolygon.sip
Expand Up @@ -143,6 +143,8 @@ Adds an interior ring to the geometry (takes ownership)

virtual int nCoordinates() const;

virtual int vertexNumberFromVertexId( QgsVertexId id ) const;

virtual bool isEmpty() const;

virtual double closestSegment( const QgsPoint &pt, QgsPoint &segmentPt /Out/, QgsVertexId &vertexAfter /Out/, bool *leftOf /Out/ = 0, double epsilon = 4 * DBL_EPSILON ) const;
Expand Down
28 changes: 17 additions & 11 deletions python/core/geometry/qgsgeometry.sip
Expand Up @@ -1293,24 +1293,30 @@ Returns an extruded version of this geometry.
.. versionadded:: 2.10
%End

bool vertexIdFromVertexNr( int nr, QgsVertexId &id /Out/ ) const;
bool vertexIdFromVertexNr( int number, QgsVertexId &id /Out/ ) const;
%Docstring
Calculates the vertex ID from a vertex number
\param nr vertex number
\param id reference to QgsVertexId for storing result
:return: true if vertex was found
Calculates the vertex ID from a vertex ``number``.

If a matching vertex was found, it will be stored in ``id``.

Returns true if vertex was found.

.. versionadded:: 2.10
.. seealso:: vertexNrFromVertexId
.. seealso:: vertexNrFromVertexId()
:rtype: bool
%End

int vertexNrFromVertexId( QgsVertexId i ) const;
int vertexNrFromVertexId( QgsVertexId id ) const;
%Docstring
Returns the vertex number corresponding to a vertex idd
\param i vertex id
:return: vertex number
Returns the vertex number corresponding to a vertex ``id``.

The vertex numbers start at 0, so a return value of 0 corresponds
to the first vertex.

Returns -1 if a corresponding vertex could not be found.

.. versionadded:: 2.10
.. seealso:: vertexIdFromVertexNr
.. seealso:: vertexIdFromVertexNr()
:rtype: int
%End

Expand Down
2 changes: 2 additions & 0 deletions python/core/geometry/qgsgeometrycollection.sip
Expand Up @@ -55,6 +55,8 @@ class QgsGeometryCollection: QgsAbstractGeometry

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

virtual int vertexNumberFromVertexId( QgsVertexId id ) const;


virtual bool addGeometry( QgsAbstractGeometry *g /Transfer/ );
%Docstring
Expand Down
3 changes: 3 additions & 0 deletions python/core/geometry/qgsmultipoint.sip
Expand Up @@ -45,6 +45,9 @@ class QgsMultiPointV2: QgsGeometryCollection

virtual QgsAbstractGeometry *boundary() const /Factory/;

virtual int vertexNumberFromVertexId( QgsVertexId id ) const;



protected:

Expand Down
2 changes: 2 additions & 0 deletions python/core/geometry/qgspoint.sip
Expand Up @@ -364,6 +364,8 @@ class QgsPoint: QgsAbstractGeometry

virtual int nCoordinates() const;

virtual int vertexNumberFromVertexId( QgsVertexId id ) const;

virtual QgsAbstractGeometry *boundary() const /Factory/;


Expand Down
12 changes: 12 additions & 0 deletions src/core/geometry/qgsabstractgeometry.h
Expand Up @@ -273,6 +273,18 @@ class CORE_EXPORT QgsAbstractGeometry
*/
virtual void draw( QPainter &p ) const = 0;

/**
* Returns the vertex number corresponding to a vertex \a id.
*
* The vertex numbers start at 0, so a return value of 0 corresponds
* to the first vertex.
*
* Returns -1 if a corresponding vertex could not be found.
*
* \since QGIS 3.0
*/
virtual int vertexNumberFromVertexId( QgsVertexId id ) const = 0;

/**
* Returns next vertex id and coordinates
* \param id initial value should be the starting vertex id. The next vertex id will be stored
Expand Down
9 changes: 9 additions & 0 deletions src/core/geometry/qgscurve.cpp
Expand Up @@ -106,6 +106,15 @@ void QgsCurve::adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex
}
}

int QgsCurve::vertexNumberFromVertexId( QgsVertexId id ) const
{
if ( id.part != 0 || id.ring != 0 )
return -1;
if ( id.vertex < 0 || id.vertex >= numPoints() )
return -1;
return id.vertex;
}

QgsAbstractGeometry *QgsCurve::boundary() const
{
if ( isEmpty() )
Expand Down
1 change: 1 addition & 0 deletions src/core/geometry/qgscurve.h
Expand Up @@ -104,6 +104,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;
int vertexNumberFromVertexId( QgsVertexId id ) const override;

/**
* Returns the point and vertex id of a point within the curve.
Expand Down
35 changes: 35 additions & 0 deletions src/core/geometry/qgscurvepolygon.cpp
Expand Up @@ -717,6 +717,41 @@ int QgsCurvePolygon::nCoordinates() const
return count;
}

int QgsCurvePolygon::vertexNumberFromVertexId( QgsVertexId id ) const
{
if ( id.part != 0 )
return -1;

if ( id.ring < 0 || id.ring >= ringCount() )
return -1;

int number = 0;
if ( id.ring == 0 && mExteriorRing )
{
return mExteriorRing->vertexNumberFromVertexId( QgsVertexId( 0, 0, id.vertex ) );
}
else
{
number += mExteriorRing->numPoints();
}

for ( int i = 0; i < mInteriorRings.count(); ++i )
{
if ( id.ring == i + 1 )
{
int partNumber = mInteriorRings.at( i )->vertexNumberFromVertexId( QgsVertexId( 0, 0, id.vertex ) );
if ( partNumber == -1 )
return -1;
return number + partNumber;
}
else
{
number += mInteriorRings.at( i )->numPoints();
}
}
return -1; // should not happen
}

bool QgsCurvePolygon::isEmpty() const
{
if ( !mExteriorRing )
Expand Down
1 change: 1 addition & 0 deletions src/core/geometry/qgscurvepolygon.h
Expand Up @@ -118,6 +118,7 @@ class CORE_EXPORT QgsCurvePolygon: public QgsSurface

QgsCoordinateSequence coordinateSequence() const override;
int nCoordinates() const override;
int vertexNumberFromVertexId( QgsVertexId id ) const override;
bool isEmpty() const override;
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;

Expand Down
28 changes: 6 additions & 22 deletions src/core/geometry/qgsgeometry.cpp
Expand Up @@ -334,8 +334,12 @@ QgsPointXY QgsGeometry::closestVertex( const QgsPointXY &point, int &atVertex, i
}
sqrDist = QgsGeometryUtils::sqrDistance2D( pt, vp );

QgsVertexId prevVertex;
QgsVertexId nextVertex;
d->geometry->adjacentVertices( id, prevVertex, nextVertex );
atVertex = vertexNrFromVertexId( id );
adjacentVertices( atVertex, beforeVertex, afterVertex );
beforeVertex = vertexNrFromVertexId( prevVertex );
afterVertex = vertexNrFromVertexId( nextVertex );
return QgsPointXY( vp.x(), vp.y() );
}

Expand Down Expand Up @@ -2451,27 +2455,7 @@ int QgsGeometry::vertexNrFromVertexId( QgsVertexId id ) const
{
return -1;
}

QgsCoordinateSequence coords = d->geometry->coordinateSequence();

int vertexCount = 0;
for ( int part = 0; part < coords.size(); ++part )
{
const QgsRingSequence &featureCoords = coords.at( part );
for ( int ring = 0; ring < featureCoords.size(); ++ring )
{
const QgsPointSequence &ringCoords = featureCoords.at( ring );
for ( int vertex = 0; vertex < ringCoords.size(); ++vertex )
{
if ( vertex == id.vertex && ring == id.ring && part == id.part )
{
return vertexCount;
}
++vertexCount;
}
}
}
return -1;
return d->geometry->vertexNumberFromVertexId( id );
}

QString QgsGeometry::lastError() const
Expand Down
28 changes: 17 additions & 11 deletions src/core/geometry/qgsgeometry.h
Expand Up @@ -1277,23 +1277,29 @@ class CORE_EXPORT QgsGeometry
void draw( QPainter &p ) const;

/**
* Calculates the vertex ID from a vertex number
* \param nr vertex number
* \param id reference to QgsVertexId for storing result
* \returns true if vertex was found
* Calculates the vertex ID from a vertex \a number.
*
* If a matching vertex was found, it will be stored in \a id.
*
* Returns true if vertex was found.
*
* \since QGIS 2.10
* \see vertexNrFromVertexId
* \see vertexNrFromVertexId()
*/
bool vertexIdFromVertexNr( int nr, QgsVertexId &id SIP_OUT ) const;
bool vertexIdFromVertexNr( int number, QgsVertexId &id SIP_OUT ) const;

/**
* Returns the vertex number corresponding to a vertex idd
* \param i vertex id
* \returns vertex number
* Returns the vertex number corresponding to a vertex \a id.
*
* The vertex numbers start at 0, so a return value of 0 corresponds
* to the first vertex.
*
* Returns -1 if a corresponding vertex could not be found.
*
* \since QGIS 2.10
* \see vertexIdFromVertexNr
* \see vertexIdFromVertexNr()
*/
int vertexNrFromVertexId( QgsVertexId i ) const;
int vertexNrFromVertexId( QgsVertexId id ) const;

/**
* Returns an error string referring to the last error encountered
Expand Down
26 changes: 26 additions & 0 deletions src/core/geometry/qgsgeometrycollection.cpp
Expand Up @@ -92,6 +92,32 @@ void QgsGeometryCollection::adjacentVertices( QgsVertexId vertex, QgsVertexId &p
mGeometries.at( vertex.part )->adjacentVertices( vertex, previousVertex, nextVertex );
}

int QgsGeometryCollection::vertexNumberFromVertexId( QgsVertexId id ) const
{
if ( id.part < 0 || id.part >= mGeometries.count() )
return -1;

int number = 0;
int part = 0;
for ( QgsAbstractGeometry *geometry : mGeometries )
{
if ( part == id.part )
{
int partNumber = geometry->vertexNumberFromVertexId( QgsVertexId( 0, id.ring, id.vertex ) );
if ( partNumber == -1 )
return -1;
return number + partNumber;
}
else
{
number += geometry->nCoordinates();
}

part++;
}
return -1; // should not happen
}

int QgsGeometryCollection::numGeometries() const
{
return mGeometries.size();
Expand Down
1 change: 1 addition & 0 deletions src/core/geometry/qgsgeometrycollection.h
Expand Up @@ -66,6 +66,7 @@ class CORE_EXPORT QgsGeometryCollection: public QgsAbstractGeometry
void clear() override;
QgsAbstractGeometry *boundary() const override SIP_FACTORY;
void adjacentVertices( QgsVertexId vertex, QgsVertexId &previousVertex SIP_OUT, QgsVertexId &nextVertex SIP_OUT ) override;
int vertexNumberFromVertexId( QgsVertexId id ) const override;

//! Adds a geometry and takes ownership. Returns true in case of success.
virtual bool addGeometry( QgsAbstractGeometry *g SIP_TRANSFER );
Expand Down
8 changes: 8 additions & 0 deletions src/core/geometry/qgsmultipoint.cpp
Expand Up @@ -154,6 +154,14 @@ QgsAbstractGeometry *QgsMultiPointV2::boundary() const
return nullptr;
}

int QgsMultiPointV2::vertexNumberFromVertexId( QgsVertexId id ) const
{
if ( id.part < 0 || id.part >= mGeometries.count() || id.vertex != 0 || id.ring != 0 )
return -1;

return id.part; // can shortcut the calculation, since each part will have 1 vertex
}

bool QgsMultiPointV2::wktOmitChildType() const
{
return true;
Expand Down
2 changes: 2 additions & 0 deletions src/core/geometry/qgsmultipoint.h
Expand Up @@ -43,6 +43,8 @@ class CORE_EXPORT QgsMultiPointV2: public QgsGeometryCollection
bool addGeometry( QgsAbstractGeometry *g SIP_TRANSFER ) override;
bool insertGeometry( QgsAbstractGeometry *g SIP_TRANSFER, int index ) override;
QgsAbstractGeometry *boundary() const override SIP_FACTORY;
int vertexNumberFromVertexId( QgsVertexId id ) const override;


#ifndef SIP_RUN

Expand Down
8 changes: 8 additions & 0 deletions src/core/geometry/qgspoint.cpp
Expand Up @@ -320,6 +320,14 @@ int QgsPoint::nCoordinates() const
return 1;
}

int QgsPoint::vertexNumberFromVertexId( QgsVertexId id ) const
{
if ( id.vertex != 0 )
return -1;
else
return 0;
}

QgsAbstractGeometry *QgsPoint::boundary() const
{
return nullptr;
Expand Down
1 change: 1 addition & 0 deletions src/core/geometry/qgspoint.h
Expand Up @@ -405,6 +405,7 @@ class CORE_EXPORT QgsPoint: public QgsAbstractGeometry
void transform( const QTransform &t ) override;
QgsCoordinateSequence coordinateSequence() const override;
int nCoordinates() const override;
int vertexNumberFromVertexId( QgsVertexId id ) const override;
QgsAbstractGeometry *boundary() const override SIP_FACTORY;

//low-level editing
Expand Down

0 comments on commit 5d67572

Please sign in to comment.