Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
QgsSpatialIndexKDBush is implicitly shared for fast copies
  • Loading branch information
nyalldawson committed Jul 7, 2018
1 parent 0df1056 commit 5c552dd
Show file tree
Hide file tree
Showing 6 changed files with 235 additions and 63 deletions.
85 changes: 85 additions & 0 deletions python/core/auto_generated/qgsspatialindexkdbush.sip.in
@@ -0,0 +1,85 @@
/************************************************************************
* This file has been generated automatically from *
* *
* src/core/qgsspatialindexkdbush.h *
* *
* Do not edit manually ! Edit header and run scripts/sipify.pl again *
************************************************************************/





class QgsSpatialIndexKDBush
{
%Docstring

A very fast static spatial index for 2D points based on a flat KD-tree.

Compared to QgsSpatialIndex, this index:
- supports single point features only (no multipoints)
- is static (features cannot be added or removed from the index after construction)
- is much faster!
- supports true "distance based" searches, i.e. return all points within a radius
from a search point

.. seealso:: :py:class:`QgsSpatialIndex`

.. versionadded:: 3.4
%End

%TypeHeaderCode
#include "qgsspatialindexkdbush.h"
%End
public:

explicit QgsSpatialIndexKDBush( QgsFeatureIterator &fi, QgsFeedback *feedback = 0 );
%Docstring
Constructor - creates KDBush index and bulk loads it with features from the iterator.

The optional ``feedback`` object can be used to allow cancelation of bulk feature loading. Ownership
of ``feedback`` is not transferred, and callers must take care that the lifetime of feedback exceeds
that of the spatial index construction.

Any non-single point features encountered during iteration will be ignored and not included in the index.
%End

explicit QgsSpatialIndexKDBush( const QgsFeatureSource &source, QgsFeedback *feedback = 0 );
%Docstring
Constructor - creates KDBush index and bulk loads it with features from the source.

The optional ``feedback`` object can be used to allow cancelation of bulk feature loading. Ownership
of ``feedback`` is not transferred, and callers must take care that the lifetime of feedback exceeds
that of the spatial index construction.

Any non-single point features encountered during iteration will be ignored and not included in the index.
%End

QgsSpatialIndexKDBush( const QgsSpatialIndexKDBush &other );
%Docstring
Copy constructor
%End


~QgsSpatialIndexKDBush();

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

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

};

/************************************************************************
* This file has been generated automatically from *
* *
* src/core/qgsspatialindexkdbush.h *
* *
* Do not edit manually ! Edit header and run scripts/sipify.pl again *
************************************************************************/
1 change: 1 addition & 0 deletions src/core/CMakeLists.txt
Expand Up @@ -914,6 +914,7 @@ SET(QGIS_CORE_HDRS
qgssnappingutils.h
qgsspatialindex.h
qgsspatialindexkdbush.h
qgsspatialindexkdbush_p.h
qgsspatialiteutils.h
qgssqlstatement.h
qgssqliteutils.h
Expand Down
90 changes: 29 additions & 61 deletions src/core/qgsspatialindexkdbush.cpp
Expand Up @@ -16,91 +16,59 @@
***************************************************************************/

#include "qgsspatialindexkdbush.h"
#include "kdbush.hpp"
#include "qgsspatialindexkdbush_p.h"
#include "qgsfeatureiterator.h"
#include "qgsfeedback.h"
#include "qgsfeaturesource.h"

class PointXYKDBush : public kdbush::KDBush< std::pair<double, double>, QgsFeatureId >
QgsSpatialIndexKDBush::QgsSpatialIndexKDBush( QgsFeatureIterator &fi, QgsFeedback *feedback )
: d( new QgsSpatialIndexKDBushPrivate( fi, feedback ) )
{
public:

explicit PointXYKDBush( QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
{
fillFromIterator( fi, feedback );
}

explicit PointXYKDBush( const QgsFeatureSource &source, QgsFeedback *feedback )
{
points.reserve( source.featureCount() );
ids.reserve( source.featureCount() );
QgsFeatureIterator it = source.getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) );
fillFromIterator( it, feedback );
}

void fillFromIterator( QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
{
QgsFeatureId size = 0;

QgsFeature f;
while ( fi.nextFeature( f ) )
{
if ( feedback && feedback->isCanceled() )
return;

if ( !f.hasGeometry() )
continue;

if ( QgsWkbTypes::flatType( f.geometry().wkbType() ) == QgsWkbTypes::Point )
{
const QgsPoint *point = qgsgeometry_cast< const QgsPoint * >( f.geometry().constGet() );
points.emplace_back( point->x(), point->y() );
}
else
{
// not a point
continue;
}

ids.push_back( f.id() );
size++;
}

sortKD( 0, size - 1, 0 );
}

};

//
// QgsSpatialIndexKDBush
//
}

QgsSpatialIndexKDBush::QgsSpatialIndexKDBush( QgsFeatureIterator &fi, QgsFeedback *feedback )
: mIndex( qgis::make_unique < PointXYKDBush >( fi, feedback ) )
QgsSpatialIndexKDBush::QgsSpatialIndexKDBush( const QgsFeatureSource &source, QgsFeedback *feedback )
: d( new QgsSpatialIndexKDBushPrivate( source, feedback ) )
{
}

QgsSpatialIndexKDBush::QgsSpatialIndexKDBush( const QgsSpatialIndexKDBush &other )
{
d = other.d;
d->ref.ref();
}

QgsSpatialIndexKDBush::QgsSpatialIndexKDBush( const QgsFeatureSource &source, QgsFeedback *feedback )
: mIndex( qgis::make_unique < PointXYKDBush >( source, feedback ) )
QgsSpatialIndexKDBush &QgsSpatialIndexKDBush::operator=( const QgsSpatialIndexKDBush &other )
{
if ( !d->ref.deref() )
{
delete d;
}

d = other.d;
d->ref.ref();
return *this;
}

QgsSpatialIndexKDBush::~QgsSpatialIndexKDBush() = default;
QgsSpatialIndexKDBush::~QgsSpatialIndexKDBush()
{
if ( !d->ref.deref() )
delete d;
}

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

QList<QgsFeatureId> QgsSpatialIndexKDBush::intersect( const QgsRectangle &rectangle ) const
{
QList<QgsFeatureId> result;
mIndex->range( rectangle.xMinimum(),
rectangle.yMinimum(),
rectangle.xMaximum(),
d->index->range( rectangle.xMinimum(),
rectangle.yMinimum(),
rectangle.xMaximum(),
rectangle.yMaximum(), [&result]( const QgsFeatureId id ) { result << id; } );
return result;
}
13 changes: 11 additions & 2 deletions src/core/qgsspatialindexkdbush.h
Expand Up @@ -22,7 +22,7 @@ class QgsPointXY;
class QgsFeatureIterator;
class QgsFeedback;
class QgsFeatureSource;
class PointXYKDBush;
class QgsSpatialIndexKDBushPrivate;
class QgsRectangle;

#include "qgis_core.h"
Expand All @@ -43,6 +43,8 @@ class QgsRectangle;
* - supports true "distance based" searches, i.e. return all points within a radius
* from a search point
*
* QgsSpatialIndexKDBush objects are implicitly shared and can be inexpensively copied.
*
* \see QgsSpatialIndex, which is an general, mutable index for geometry bounding boxes.
* \since QGIS 3.4
*/
Expand Down Expand Up @@ -72,6 +74,12 @@ class CORE_EXPORT QgsSpatialIndexKDBush
*/
explicit QgsSpatialIndexKDBush( const QgsFeatureSource &source, QgsFeedback *feedback = nullptr );

//! Copy constructor
QgsSpatialIndexKDBush( const QgsSpatialIndexKDBush &other );

//! Assignment operator
QgsSpatialIndexKDBush &operator=( const QgsSpatialIndexKDBush &other );

~QgsSpatialIndexKDBush();

/**
Expand All @@ -87,7 +95,8 @@ class CORE_EXPORT QgsSpatialIndexKDBush

private:

std::unique_ptr< PointXYKDBush > mIndex;
//! Implicitly shared data pointer
QgsSpatialIndexKDBushPrivate *d = nullptr;
};

#endif // QGSSPATIALINDEXKDBUSH_H
Empty file.
109 changes: 109 additions & 0 deletions src/core/qgsspatialindexkdbush_p.h
@@ -0,0 +1,109 @@
/***************************************************************************
qgsspatialindexkdbush_p.h
-----------------
begin : July 2018
copyright : (C) 2018 by Nyall Dawson
email : nyall dot dawson at gmail dot com
***************************************************************************/

/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/

#ifndef QGSSPATIALINDEXKDBUSH_PRIVATE_H
#define QGSSPATIALINDEXKDBUSH_PRIVATE_H

/// @cond PRIVATE

//
// W A R N I N G
// -------------
//
// This file is not part of the QGIS API. It exists purely as an
// implementation detail. This header file may change from version to
// version without notice, or even be removed.
//

#include "qgsfeature.h"

#include "qgsfeatureiterator.h"
#include "qgsfeedback.h"
#include "qgsfeaturesource.h"
#include <memory>
#include <QList>
#include "kdbush.hpp"

class PointXYKDBush : public kdbush::KDBush< std::pair<double, double>, QgsFeatureId >
{
public:

explicit PointXYKDBush( QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
{
fillFromIterator( fi, feedback );
}

explicit PointXYKDBush( const QgsFeatureSource &source, QgsFeedback *feedback )
{
points.reserve( source.featureCount() );
ids.reserve( source.featureCount() );
QgsFeatureIterator it = source.getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) );
fillFromIterator( it, feedback );
}

void fillFromIterator( QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
{
QgsFeatureId size = 0;

QgsFeature f;
while ( fi.nextFeature( f ) )
{
if ( feedback && feedback->isCanceled() )
return;

if ( !f.hasGeometry() )
continue;

if ( QgsWkbTypes::flatType( f.geometry().wkbType() ) == QgsWkbTypes::Point )
{
const QgsPoint *point = qgsgeometry_cast< const QgsPoint * >( f.geometry().constGet() );
points.emplace_back( point->x(), point->y() );
}
else
{
// not a point
continue;
}

ids.push_back( f.id() );
size++;
}

sortKD( 0, size - 1, 0 );
}

};

class QgsSpatialIndexKDBushPrivate
{
public:

explicit QgsSpatialIndexKDBushPrivate( QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
: index( qgis::make_unique < PointXYKDBush >( fi, feedback ) )
{}

explicit QgsSpatialIndexKDBushPrivate( const QgsFeatureSource &source, QgsFeedback *feedback = nullptr )
: index( qgis::make_unique < PointXYKDBush >( source, feedback ) )
{}

QAtomicInt ref = 1;
std::unique_ptr< PointXYKDBush > index;
};

/// @endcond

#endif // QGSSPATIALINDEXKDBUSH_PRIVATE_H

0 comments on commit 5c552dd

Please sign in to comment.