Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
When a QgsSpatialIndex is storing feature geometry, then
nearestNeighbor search performs an EXACT nearest neighbour search,
instead of just a nearest-neighbour-by-bounding-box search
  • Loading branch information
nyalldawson committed Feb 19, 2019
1 parent 2655535 commit 362ba02
Show file tree
Hide file tree
Showing 4 changed files with 61 additions and 4 deletions.
5 changes: 3 additions & 2 deletions python/core/auto_generated/qgsspatialindex.sip.in
Expand Up @@ -152,9 +152,10 @@ Returns a list of features with a bounding box which intersects the specified ``
Returns nearest neighbors to a ``point``. The number of neighbours returned is specified
by the ``neighbours`` argument.

.. note::
.. warning::

The nearest neighbour test is performed based on the feature bounding boxes only, so for non-point
If this QgsSpatialIndex object was not constructed with the FlagStoreFeatureGeometries flag,
then the nearest neighbour test is performed based on the feature bounding boxes ONLY, so for non-point
geometry features this method is not guaranteed to return the actual closest neighbours.
%End

Expand Down
36 changes: 35 additions & 1 deletion src/core/qgsspatialindex.cpp
Expand Up @@ -87,6 +87,31 @@ class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
SpatialIndex::ISpatialIndex *mNewIndex = nullptr;
};

class QgsNearestNeighbourComparator : public INearestNeighborComparator
{
public:

QgsNearestNeighbourComparator( const QHash< QgsFeatureId, QgsGeometry > &geometries, const QgsPointXY &point )
: mGeometries( geometries )
, mPoint( QgsGeometry::fromPointXY( point ) )
{
}

QHash< QgsFeatureId, QgsGeometry > mGeometries;
QgsGeometry mPoint;

double getMinimumDistance( const IShape &, const IShape & ) override
{
Q_ASSERT( false ); // not implemented!
return 0;
}

double getMinimumDistance( const IShape &, const IData &data ) override
{
QgsGeometry other = mGeometries.value( data.getIdentifier() );
return other.distance( mPoint );
}
};

/**
* \ingroup core
Expand Down Expand Up @@ -423,7 +448,16 @@ QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, i
Point p( pt, 2 );

QMutexLocker locker( &d->mMutex );
d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
if ( d->mFlags & QgsSpatialIndex::FlagStoreFeatureGeometries )
{
QgsNearestNeighbourComparator nnc( d->mGeometries, point );
d->mRTree->nearestNeighborQuery( neighbors, p, visitor, nnc );
}
else
{
// simple bounding box search - meaningless for non-points
d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
}

return list;
}
Expand Down
3 changes: 2 additions & 1 deletion src/core/qgsspatialindex.h
Expand Up @@ -178,7 +178,8 @@ class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink
* Returns nearest neighbors to a \a point. The number of neighbours returned is specified
* by the \a neighbours argument.
*
* \note The nearest neighbour test is performed based on the feature bounding boxes only, so for non-point
* \warning If this QgsSpatialIndex object was not constructed with the FlagStoreFeatureGeometries flag,
* then the nearest neighbour test is performed based on the feature bounding boxes ONLY, so for non-point
* geometry features this method is not guaranteed to return the actual closest neighbours.
*/
QList<QgsFeatureId> nearestNeighbor( const QgsPointXY &point, int neighbors ) const;
Expand Down
21 changes: 21 additions & 0 deletions tests/src/core/testqgsspatialindex.cpp
Expand Up @@ -306,6 +306,27 @@ class TestQgsSpatialIndex : public QObject
QVERIFY( i6.geometry( 50 ).isNull() );
}

void testNearestNeighbour()
{
QgsSpatialIndex i;
QgsSpatialIndex i2( QgsSpatialIndex::FlagStoreFeatureGeometries );

QgsFeature f1( 1 );
f1.setGeometry( QgsGeometry::fromWkt( QStringLiteral( "LineString(1 1, 3 1, 3 3)" ) ) );
QgsFeature f2( 2 );
f2.setGeometry( QgsGeometry::fromWkt( QStringLiteral( "LineString(0 1, 0 3)" ) ) );
i.addFeature( f1 );
i2.addFeature( f1 );
i.addFeature( f2 );
i2.addFeature( f2 );

// i does not store feature geometries, so nearest neighbour search uses bounding box only
QCOMPARE( i.nearestNeighbor( QgsPointXY( 1, 3 ), 1 ), QList< QgsFeatureId >() << 1 );
// i2 does store feature geometries, so nearest neighbour is exact
QCOMPARE( i2.nearestNeighbor( QgsPointXY( 1, 3 ), 1 ), QList< QgsFeatureId >() << 2 );

}

};

QGSTEST_MAIN( TestQgsSpatialIndex )
Expand Down

0 comments on commit 362ba02

Please sign in to comment.