Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Return full point container for matches, remove redundant point method
  • Loading branch information
nyalldawson committed Jul 7, 2018
1 parent 66c1788 commit ae4e4cd
Show file tree
Hide file tree
Showing 5 changed files with 45 additions and 77 deletions.
16 changes: 4 additions & 12 deletions python/core/auto_generated/qgsspatialindexkdbush.sip.in
Expand Up @@ -65,27 +65,19 @@ Copy constructor

~QgsSpatialIndexKDBush();

QSet<QgsFeatureId> intersect( const QgsRectangle &rectangle ) const;
QList<QgsSpatialIndexKDBushData> intersect( const QgsRectangle &rectangle ) const;
%Docstring
Returns the set of features which fall within the specified ``rectangle``.
Returns the list of features which fall within the specified ``rectangle``.
%End


QSet<QgsFeatureId> within( const QgsPointXY &point, double radius ) const;
QList<QgsSpatialIndexKDBushData> within( const QgsPointXY &point, double radius ) const;
%Docstring
Returns the set of features which are within the given search ``radius``
Returns the list of features which are within the given search ``radius``
of ``point``.
%End


bool point( QgsFeatureId id, QgsPointXY &point ) const;
%Docstring
Fetches the point from the index with matching ``id`` and stores it in ``point``.

Returns true if the point was found, or false if no matching feature ID is present
in the index.
%End

qgssize size() const;
%Docstring
Returns the size of the index, i.e. the number of points contained within the index.
Expand Down
17 changes: 6 additions & 11 deletions src/core/qgsspatialindexkdbush.cpp
Expand Up @@ -56,10 +56,10 @@ QgsSpatialIndexKDBush::~QgsSpatialIndexKDBush()
delete d;
}

QSet<QgsFeatureId> QgsSpatialIndexKDBush::within( const QgsPointXY &point, double radius ) const
QList<QgsSpatialIndexKDBushData> QgsSpatialIndexKDBush::within( const QgsPointXY &point, double radius ) const
{
QSet<QgsFeatureId> result;
d->index->within( point.x(), point.y(), radius, [&result]( const QgsSpatialIndexKDBushData & p ) { result.insert( p.id ); } );
QList<QgsSpatialIndexKDBushData> result;
d->index->within( point.x(), point.y(), radius, [&result]( const QgsSpatialIndexKDBushData & p ) { result << p; } );
return result;
}

Expand All @@ -68,23 +68,18 @@ void QgsSpatialIndexKDBush::within( const QgsPointXY &point, double radius, cons
d->index->within( point.x(), point.y(), radius, visitor );
}

bool QgsSpatialIndexKDBush::point( QgsFeatureId id, QgsPointXY &point ) const
{
return d->index->point( id, point );
}

qgssize QgsSpatialIndexKDBush::size() const
{
return d->index->size();
}

QSet<QgsFeatureId> QgsSpatialIndexKDBush::intersect( const QgsRectangle &rectangle ) const
QList<QgsSpatialIndexKDBushData> QgsSpatialIndexKDBush::intersect( const QgsRectangle &rectangle ) const
{
QSet<QgsFeatureId> result;
QList<QgsSpatialIndexKDBushData> result;
d->index->range( rectangle.xMinimum(),
rectangle.yMinimum(),
rectangle.xMaximum(),
rectangle.yMaximum(), [&result]( const QgsSpatialIndexKDBushData & p ) { result << p.id; } );
rectangle.yMaximum(), [&result]( const QgsSpatialIndexKDBushData & p ) { result << p; } );
return result;
}

Expand Down
16 changes: 4 additions & 12 deletions src/core/qgsspatialindexkdbush.h
Expand Up @@ -84,9 +84,9 @@ class CORE_EXPORT QgsSpatialIndexKDBush
~QgsSpatialIndexKDBush();

/**
* Returns the set of features which fall within the specified \a rectangle.
* Returns the list of features which fall within the specified \a rectangle.
*/
QSet<QgsFeatureId> intersect( const QgsRectangle &rectangle ) const;
QList<QgsSpatialIndexKDBushData> intersect( const QgsRectangle &rectangle ) const;

/**
* Calls a \a visitor function for all features which fall within the specified \a rectangle.
Expand All @@ -96,10 +96,10 @@ class CORE_EXPORT QgsSpatialIndexKDBush
void intersect( const QgsRectangle &rectangle, const std::function<void( QgsSpatialIndexKDBushData )> &visitor ) const SIP_SKIP;

/**
* Returns the set of features which are within the given search \a radius
* Returns the list of features which are within the given search \a radius
* of \a point.
*/
QSet<QgsFeatureId> within( const QgsPointXY &point, double radius ) const;
QList<QgsSpatialIndexKDBushData> within( const QgsPointXY &point, double radius ) const;

/**
* Calls a \a visitor function for all features which are within the given search \a radius
Expand All @@ -109,14 +109,6 @@ class CORE_EXPORT QgsSpatialIndexKDBush
*/
void within( const QgsPointXY &point, double radius, const std::function<void( QgsSpatialIndexKDBushData )> &visitor ) SIP_SKIP;

/**
* Fetches the point from the index with matching \a id and stores it in \a point.
*
* Returns true if the point was found, or false if no matching feature ID is present
* in the index.
*/
bool point( QgsFeatureId id, QgsPointXY &point ) const;

/**
* Returns the size of the index, i.e. the number of points contained within the index.
*/
Expand Down
11 changes: 0 additions & 11 deletions src/core/qgsspatialindexkdbush_p.h
Expand Up @@ -90,17 +90,6 @@ class PointXYKDBush : public kdbush::KDBush< std::pair<double, double>, QgsSpati
sortKD( 0, size - 1, 0 );
}

bool point( QgsFeatureId id, QgsPointXY &point ) const
{
auto it = std::find_if( points.begin(), points.end(),
[id]( const QgsSpatialIndexKDBushData & d ) { return d.id == id; } );
if ( it == points.end() )
return false;

point = QgsPointXY( it->coords.first, it->coords.second );
return true;
}

std::size_t size() const
{
return points.size();
Expand Down
62 changes: 31 additions & 31 deletions tests/src/core/testqgsspatialindexkdbush.cpp
Expand Up @@ -51,6 +51,18 @@ static QList<QgsFeature> _pointFeatures()
return feats;
}

bool testContains( const QList<QgsSpatialIndexKDBushData> &data, QgsFeatureId id, const QgsPointXY &point )
{
for ( const QgsSpatialIndexKDBushData &d : data )
{
if ( d.id == id )
{
return d.point() == point;
}
}
return false;
}

class TestQgsSpatialIndexKdBush : public QObject
{
Q_OBJECT
Expand All @@ -75,42 +87,30 @@ class TestQgsSpatialIndexKdBush : public QObject
QgsSpatialIndexKDBush index( *vl->dataProvider() );
QCOMPARE( index.size(), 4 );

QSet<QgsFeatureId> fids = index.intersect( QgsRectangle( 0, 0, 10, 10 ) );
QList<QgsSpatialIndexKDBushData> fids = index.intersect( QgsRectangle( 0, 0, 10, 10 ) );
QVERIFY( fids.count() == 1 );
QVERIFY( fids.contains( 1 ) );
QVERIFY( testContains( fids, 1, QgsPointXY( 1, 1 ) ) );

QSet<QgsFeatureId> fids2 = index.intersect( QgsRectangle( -10, -10, 0, 10 ) );
QList<QgsSpatialIndexKDBushData> fids2 = index.intersect( QgsRectangle( -10, -10, 0, 10 ) );
QCOMPARE( fids2.count(), 2 );
QVERIFY( fids2.contains( 2 ) );
QVERIFY( fids2.contains( 3 ) );
QVERIFY( testContains( fids2, 2, QgsPointXY( -1, 1 ) ) );
QVERIFY( testContains( fids2, 3, QgsPointXY( -1, -1 ) ) );

QSet<QgsFeatureId> fids3 = index.within( QgsPointXY( 0, 0 ), 2 );
QList<QgsSpatialIndexKDBushData> fids3 = index.within( QgsPointXY( 0, 0 ), 2 );
QCOMPARE( fids3.count(), 4 );
QVERIFY( fids3.contains( 1 ) );
QVERIFY( fids3.contains( 2 ) );
QVERIFY( fids3.contains( 3 ) );
QVERIFY( fids3.contains( 4 ) );
QVERIFY( testContains( fids3, 1, QgsPointXY( 1, 1 ) ) );
QVERIFY( testContains( fids3, 2, QgsPointXY( -1, 1 ) ) );
QVERIFY( testContains( fids3, 3, QgsPointXY( -1, -1 ) ) );
QVERIFY( testContains( fids3, 4, QgsPointXY( 1, -1 ) ) );

QSet<QgsFeatureId> fids4 = index.within( QgsPointXY( 0, 0 ), 1 );
QList<QgsSpatialIndexKDBushData> fids4 = index.within( QgsPointXY( 0, 0 ), 1 );
QCOMPARE( fids4.count(), 0 );

QSet<QgsFeatureId> fids5 = index.within( QgsPointXY( -1, -1 ), 2.1 );
QList<QgsSpatialIndexKDBushData> fids5 = index.within( QgsPointXY( -1, -1 ), 2.1 );
QCOMPARE( fids5.count(), 3 );
QVERIFY( fids5.contains( 2 ) );
QVERIFY( fids5.contains( 3 ) );
QVERIFY( fids5.contains( 4 ) );

QgsPointXY p;
QVERIFY( !index.point( -1, p ) );
QVERIFY( !index.point( 5, p ) );
QVERIFY( index.point( 1, p ) );
QCOMPARE( p, QgsPointXY( 1, 1 ) );
QVERIFY( index.point( 2, p ) );
QCOMPARE( p, QgsPointXY( -1, 1 ) );
QVERIFY( index.point( 3, p ) );
QCOMPARE( p, QgsPointXY( -1, -1 ) );
QVERIFY( index.point( 4, p ) );
QCOMPARE( p, QgsPointXY( 1, -1 ) );
QVERIFY( testContains( fids5, 2, QgsPointXY( -1, 1 ) ) );
QVERIFY( testContains( fids5, 3, QgsPointXY( -1, -1 ) ) );
QVERIFY( testContains( fids5, 4, QgsPointXY( 1, -1 ) ) );
}

void testCopy()
Expand All @@ -128,9 +128,9 @@ class TestQgsSpatialIndexKdBush : public QObject
QVERIFY( index->d->ref == 2 );

// test that copied index works
QSet<QgsFeatureId> fids = indexCopy->intersect( QgsRectangle( 0, 0, 10, 10 ) );
QList<QgsSpatialIndexKDBushData> fids = indexCopy->intersect( QgsRectangle( 0, 0, 10, 10 ) );
QVERIFY( fids.count() == 1 );
QVERIFY( fids.contains( 1 ) );
QVERIFY( testContains( fids, 1, QgsPointXY( 1, 1 ) ) );

// check that the index is still shared
QVERIFY( index->d == indexCopy->d );
Expand All @@ -141,7 +141,7 @@ class TestQgsSpatialIndexKdBush : public QObject
// test that copied index still works
fids = indexCopy->intersect( QgsRectangle( 0, 0, 10, 10 ) );
QVERIFY( fids.count() == 1 );
QVERIFY( fids.contains( 1 ) );
QVERIFY( testContains( fids, 1, QgsPointXY( 1, 1 ) ) );
QVERIFY( indexCopy->d->ref == 1 );

// assignment operator
Expand All @@ -157,7 +157,7 @@ class TestQgsSpatialIndexKdBush : public QObject
QVERIFY( index3.d->ref == 2 );
fids = index3.intersect( QgsRectangle( 0, 0, 10, 10 ) );
QVERIFY( fids.count() == 1 );
QVERIFY( fids.contains( 1 ) );
QVERIFY( testContains( fids, 1, QgsPointXY( 1, 1 ) ) );

indexCopy.reset();
QVERIFY( index3.d->ref == 1 );
Expand Down

0 comments on commit ae4e4cd

Please sign in to comment.