Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Add API for QgsSpatialIndex to optionally store feature geometries
This potentially avoids a second expensive feature request after
building a spatial index and later needing to re-request features
which match spatial index search.

It's non-default, as it requires the index to store all feature
geometries, so it's more memory expensive.
  • Loading branch information
nyalldawson committed Feb 19, 2019
1 parent 68b4602 commit 2655535
Show file tree
Hide file tree
Showing 5 changed files with 237 additions and 18 deletions.
39 changes: 36 additions & 3 deletions python/core/auto_generated/qgsspatialindex.sip.in
Expand Up @@ -39,12 +39,19 @@ QgsSpatialIndex objects are implicitly shared and can be inexpensively copied.
public:


QgsSpatialIndex();
enum Flag
{
FlagStoreFeatureGeometries,
};
typedef QFlags<QgsSpatialIndex::Flag> Flags;


QgsSpatialIndex( QgsSpatialIndex::Flags flags = 0 );
%Docstring
Constructor for QgsSpatialIndex. Creates an empty R-tree index.
%End

explicit QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback = 0 );
explicit QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback = 0, QgsSpatialIndex::Flags flags = 0 );
%Docstring
Constructor - creates R-tree and bulk loads it with features from the iterator.
This is much faster approach than creating an empty index and then inserting features one by one.
Expand All @@ -56,7 +63,7 @@ that of the spatial index construction.
.. versionadded:: 2.8
%End

explicit QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback = 0 );
explicit QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback = 0, QgsSpatialIndex::Flags flags = 0 );
%Docstring
Constructor - creates R-tree and bulk loads it with features from the source.
This is much faster approach than creating an empty index and then inserting features one by one.
Expand Down Expand Up @@ -152,13 +159,39 @@ by the ``neighbours`` argument.
%End


SIP_PYOBJECT geometry( QgsFeatureId id ) const /TypeHint="QgsGeometry"/;
%Docstring
Returns the stored geometry for the indexed feature with matching ``id``. A KeyError will be raised if no
geometry with the specified feature id exists in the index.

Geometry is only stored if the QgsSpatialIndex was created with the FlagStoreFeatureGeometries flag.

.. versionadded:: 3.6
%End
%MethodCode
std::unique_ptr< QgsGeometry > g = qgis::make_unique< QgsGeometry >( sipCpp->geometry( a0 ) );
if ( g->isNull() )
{
PyErr_SetString( PyExc_KeyError, QStringLiteral( "No geometry with feature id %1 exists in the index." ).arg( a0 ).toUtf8().constData() );
sipIsErr = 1;
}
else
{
sipRes = sipConvertFromType( g.release(), sipType_QgsGeometry, Py_None );
}
%End


int refs() const;
%Docstring
Gets reference count - just for debugging!
%End

};

QFlags<QgsSpatialIndex::Flag> operator|(QgsSpatialIndex::Flag f1, QFlags<QgsSpatialIndex::Flag> f2);


/************************************************************************
* This file has been generated automatically from *
* *
Expand Down
56 changes: 45 additions & 11 deletions src/core/qgsspatialindex.cpp
Expand Up @@ -98,9 +98,10 @@ class QgsFeatureIteratorDataStream : public IDataStream
{
public:
//! constructor - needs to load all data to a vector for later access when bulk loading
explicit QgsFeatureIteratorDataStream( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
explicit QgsFeatureIteratorDataStream( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = nullptr )
: mFi( fi )
, mFeedback( feedback )
, mFlags( flags )
{
readNextEntry();
}
Expand Down Expand Up @@ -131,6 +132,8 @@ class QgsFeatureIteratorDataStream : public IDataStream
//! sets the stream pointer to the first entry, if possible.
void rewind() override { Q_ASSERT( false && "not available" ); }

QHash< QgsFeatureId, QgsGeometry > geometries;

protected:
void readNextEntry()
{
Expand All @@ -142,6 +145,8 @@ class QgsFeatureIteratorDataStream : public IDataStream
if ( QgsSpatialIndex::featureInfo( f, r, id ) )
{
mNextData = new RTree::Data( 0, nullptr, r, id );
if ( mFlags & QgsSpatialIndex::FlagStoreFeatureGeometries )
geometries.insert( f.id(), f.geometry() );
return;
}
}
Expand All @@ -151,6 +156,8 @@ class QgsFeatureIteratorDataStream : public IDataStream
QgsFeatureIterator mFi;
RTree::Data *mNextData = nullptr;
QgsFeedback *mFeedback = nullptr;
QgsSpatialIndex::Flags mFlags = nullptr;

};


Expand All @@ -163,11 +170,16 @@ class QgsFeatureIteratorDataStream : public IDataStream
class QgsSpatialIndexData : public QSharedData
{
public:
QgsSpatialIndexData()
QgsSpatialIndexData( QgsSpatialIndex::Flags flags )
: mFlags( flags )
{
initTree();
}

QgsSpatialIndex::Flags mFlags = nullptr;

QHash< QgsFeatureId, QgsGeometry > mGeometries;

/**
* Constructor for QgsSpatialIndexData which bulk loads features from the specified feature iterator
* \a fi.
Expand All @@ -176,14 +188,19 @@ class QgsSpatialIndexData : public QSharedData
* of \a feedback is not transferred, and callers must take care that the lifetime of feedback exceeds
* that of the spatial index construction.
*/
explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = nullptr )
: mFlags( flags )
{
QgsFeatureIteratorDataStream fids( fi, feedback );
QgsFeatureIteratorDataStream fids( fi, feedback, mFlags );
initTree( &fids );
if ( flags & QgsSpatialIndex::FlagStoreFeatureGeometries )
mGeometries = fids.geometries;
}

QgsSpatialIndexData( const QgsSpatialIndexData &other )
: QSharedData( other )
, mFlags( other.mFlags )
, mGeometries( other.mGeometries )
{
QMutexLocker locker( &other.mMutex );

Expand Down Expand Up @@ -241,19 +258,19 @@ class QgsSpatialIndexData : public QSharedData
// -------------------------------------------------------------------------


QgsSpatialIndex::QgsSpatialIndex()
QgsSpatialIndex::QgsSpatialIndex( QgsSpatialIndex::Flags flags )
{
d = new QgsSpatialIndexData;
d = new QgsSpatialIndexData( flags );
}

QgsSpatialIndex::QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback )
QgsSpatialIndex::QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback, QgsSpatialIndex::Flags flags )
{
d = new QgsSpatialIndexData( fi, feedback );
d = new QgsSpatialIndexData( fi, feedback, flags );
}

QgsSpatialIndex::QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback )
QgsSpatialIndex::QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback, QgsSpatialIndex::Flags flags )
{
d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setNoAttributes() ), feedback );
d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setNoAttributes() ), feedback, flags );
}

QgsSpatialIndex::QgsSpatialIndex( const QgsSpatialIndex &other ) //NOLINT
Expand Down Expand Up @@ -306,7 +323,16 @@ bool QgsSpatialIndex::addFeature( QgsFeature &feature, QgsFeatureSink::Flags )
if ( !featureInfo( feature, rect, id ) )
return false;

return addFeature( id, rect );
if ( addFeature( id, rect ) )
{
if ( d->mFlags & QgsSpatialIndex::FlagStoreFeatureGeometries )
{
QMutexLocker locker( &d->mMutex );
d->mGeometries.insert( feature.id(), feature.geometry() );
}
return true;
}
return false;
}

bool QgsSpatialIndex::addFeatures( QgsFeatureList &features, QgsFeatureSink::Flags flags )
Expand Down Expand Up @@ -370,6 +396,8 @@ bool QgsSpatialIndex::deleteFeature( const QgsFeature &f )

QMutexLocker locker( &d->mMutex );
// TODO: handle exceptions
if ( d->mFlags & QgsSpatialIndex::FlagStoreFeatureGeometries )
d->mGeometries.remove( f.id() );
return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
}

Expand Down Expand Up @@ -400,6 +428,12 @@ QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, i
return list;
}

QgsGeometry QgsSpatialIndex::geometry( QgsFeatureId id ) const
{
QMutexLocker locker( &d->mMutex );
return d->mGeometries.value( id );
}

QAtomicInt QgsSpatialIndex::refs() const
{
return d->ref;
Expand Down
51 changes: 48 additions & 3 deletions src/core/qgsspatialindex.h
Expand Up @@ -71,10 +71,17 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink

/* creation of spatial index */

//! Flags controlling index behavior
enum Flag
{
FlagStoreFeatureGeometries = 1 << 0, //!< Indicates that the spatial index should also store feature geometries. This requires more memory, but can speed up operations by avoiding additional requests to data providers to fetch matching feature geometries. Additionally, it is required for non-bounding box nearest neighbour searches.
};
Q_DECLARE_FLAGS( Flags, Flag )

/**
* Constructor for QgsSpatialIndex. Creates an empty R-tree index.
*/
QgsSpatialIndex();
QgsSpatialIndex( QgsSpatialIndex::Flags flags = nullptr );

/**
* Constructor - creates R-tree and bulk loads it with features from the iterator.
Expand All @@ -86,7 +93,7 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink
*
* \since QGIS 2.8
*/
explicit QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr );
explicit QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = nullptr );

/**
* Constructor - creates R-tree and bulk loads it with features from the source.
Expand All @@ -99,7 +106,7 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink
*
* \since QGIS 3.0
*/
explicit QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback = nullptr );
explicit QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = nullptr );

//! Copy constructor
QgsSpatialIndex( const QgsSpatialIndex &other );
Expand Down Expand Up @@ -176,6 +183,42 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink
*/
QList<QgsFeatureId> nearestNeighbor( const QgsPointXY &point, int neighbors ) const;

#ifndef SIP_RUN

/**
* Returns the stored geometry for the indexed feature with matching \a id.
*
* Geometry is only stored if the QgsSpatialIndex was created with the FlagStoreFeatureGeometries flag.
*
* \since QGIS 3.6
*/
QgsGeometry geometry( QgsFeatureId id ) const;

#else

/**
* Returns the stored geometry for the indexed feature with matching \a id. A KeyError will be raised if no
* geometry with the specified feature id exists in the index.
*
* Geometry is only stored if the QgsSpatialIndex was created with the FlagStoreFeatureGeometries flag.
*
* \since QGIS 3.6
*/
SIP_PYOBJECT geometry( QgsFeatureId id ) const SIP_TYPEHINT( QgsGeometry );
% MethodCode
std::unique_ptr< QgsGeometry > g = qgis::make_unique< QgsGeometry >( sipCpp->geometry( a0 ) );
if ( g->isNull() )
{
PyErr_SetString( PyExc_KeyError, QStringLiteral( "No geometry with feature id %1 exists in the index." ).arg( a0 ).toUtf8().constData() );
sipIsErr = 1;
}
else
{
sipRes = sipConvertFromType( g.release(), sipType_QgsGeometry, Py_None );
}
% End
#endif

/* debugging */

//! Gets reference count - just for debugging!
Expand Down Expand Up @@ -214,4 +257,6 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink

};

Q_DECLARE_OPERATORS_FOR_FLAGS( QgsSpatialIndex::Flags )

#endif //QGSSPATIALINDEX_H
73 changes: 73 additions & 0 deletions tests/src/core/testqgsspatialindex.cpp
Expand Up @@ -23,6 +23,7 @@
#include <qgsspatialindex.h>
#include <qgsvectordataprovider.h>
#include <qgsvectorlayer.h>
#include "qgslinestring.h"

static QgsFeature _pointFeature( QgsFeatureId id, qreal x, qreal y )
{
Expand Down Expand Up @@ -233,6 +234,78 @@ class TestQgsSpatialIndex : public QObject
delete indexInsert;
}

void testRetrieveGeometries()
{
QgsVectorLayer *vl = new QgsVectorLayer( QStringLiteral( "LineString" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
int fid = 0;
for ( int x = 0; x < 10; ++x )
{
QgsFeatureList flist;
for ( int y = 100; y < 110; ++y )
{
QgsFeature f( fid++ );
f.setGeometry( qgis::make_unique< QgsLineString >( QgsPoint( x, y ), QgsPoint( x + 0.5, y - 0.5 ) ) );
flist << f;
}
vl->dataProvider()->addFeatures( flist );
}

// iterator based population

// not storing geometries
QgsSpatialIndex i1( vl->getFeatures() );
QVERIFY( i1.geometry( 1 ).isNull() );
QVERIFY( i1.geometry( 50 ).isNull() );

// storing geometries
QgsSpatialIndex i2( vl->getFeatures(), nullptr, QgsSpatialIndex::FlagStoreFeatureGeometries );
QCOMPARE( i2.geometry( 1 ).asWkt( 1 ), QStringLiteral( "LineString (0 100, 0.5 99.5)" ) );
QCOMPARE( i2.geometry( 50 ).asWkt( 1 ), QStringLiteral( "LineString (4 109, 4.5 108.5)" ) );

// manual population

QgsSpatialIndex i3;
QgsFeatureIterator fi = vl->getFeatures();
QgsFeature f;
while ( fi.nextFeature( f ) )
{
i3.addFeature( f );
}
QVERIFY( i3.geometry( 1 ).isNull() );
QVERIFY( i3.geometry( 50 ).isNull() );


// storing geometries
QgsSpatialIndex i4( QgsSpatialIndex::FlagStoreFeatureGeometries );
fi = vl->getFeatures();
while ( fi.nextFeature( f ) )
{
i4.addFeature( f );
}
QCOMPARE( i4.geometry( 1 ).asWkt( 1 ), QStringLiteral( "LineString (0 100, 0.5 99.5)" ) );
QCOMPARE( i4.geometry( 50 ).asWkt( 1 ), QStringLiteral( "LineString (4 109, 4.5 108.5)" ) );


// not storing geometries
QgsSpatialIndex i5( *vl );
QVERIFY( i5.geometry( 1 ).isNull() );
QVERIFY( i5.geometry( 50 ).isNull() );

// storing geometries
QgsSpatialIndex i6( *vl, nullptr, QgsSpatialIndex::FlagStoreFeatureGeometries );
QCOMPARE( i6.geometry( 1 ).asWkt( 1 ), QStringLiteral( "LineString (0 100, 0.5 99.5)" ) );
QCOMPARE( i6.geometry( 50 ).asWkt( 1 ), QStringLiteral( "LineString (4 109, 4.5 108.5)" ) );

f = vl->getFeature( 1 );
QVERIFY( i6.deleteFeature( f ) );
QVERIFY( i6.geometry( 1 ).isNull() );
QCOMPARE( i6.geometry( 50 ).asWkt( 1 ), QStringLiteral( "LineString (4 109, 4.5 108.5)" ) );
f = vl->getFeature( 50 );

QVERIFY( i6.deleteFeature( f ) );
QVERIFY( i6.geometry( 50 ).isNull() );
}

};

QGSTEST_MAIN( TestQgsSpatialIndex )
Expand Down

0 comments on commit 2655535

Please sign in to comment.