Skip to content

Commit

Permalink
Made QgsSpatialIndex implicitly shared class.
Browse files Browse the repository at this point in the history 
As a bonus, spatial index is a bit faster (10%) as we do not use random eviction buffer
anymore (which makes sense only when using disk storage manager).

Added basic tests for spatial index
  • Loading branch information
@wonder-sk
wonder-sk committed Dec 3, 2013
1 parent 9d00185 commit 5386324
Show file tree
Hide file tree
Showing 4 changed files with 261 additions and 46 deletions.
135 changes: 103 additions & 32 deletions src/core/qgsspatialindex.cpp
View file
Expand Up @@ -25,6 +25,7 @@
using namespace SpatialIndex;



// custom visitor that adds found features to list
class QgisVisitor : public SpatialIndex::IVisitor
{
Expand All @@ -47,38 +48,102 @@ class QgisVisitor : public SpatialIndex::IVisitor
QList<QgsFeatureId>& mList;
};

class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
{
public:
QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex* newIndex )
: mNewIndex( newIndex ) {}

void visitNode( const INode& n )
{ Q_UNUSED( n ); }

void visitData( const IData& d )
{
SpatialIndex::IShape* shape;
d.getShape( &shape );
mNewIndex->insertData( 0, 0, *shape, d.getIdentifier() );
delete shape;
}

void visitData( std::vector<const IData*>& v )
{ Q_UNUSED( v ); }

private:
SpatialIndex::ISpatialIndex* mNewIndex;
};


/** Data of spatial index that may be implicitly shared */
class QgsSpatialIndexData : public QSharedData
{
public:
QgsSpatialIndexData()
{
initTree();
}

QgsSpatialIndexData( const QgsSpatialIndexData& other )
: QSharedData( other )
{
initTree();

// copy R-tree data one by one (is there a faster way??)
double low[] = { DBL_MIN, DBL_MIN };
double high[] = { DBL_MAX, DBL_MAX };
SpatialIndex::Region query( low, high, 2 );
QgsSpatialIndexCopyVisitor visitor( mRTree );
other.mRTree->intersectsWithQuery( query, visitor );
}

~QgsSpatialIndexData()
{
delete mRTree;
delete mStorage;
}

void initTree()
{
// for now only memory manager
mStorage = StorageManager::createNewMemoryStorageManager();

// R-Tree parameters
double fillFactor = 0.7;
unsigned long indexCapacity = 10;
unsigned long leafCapacity = 10;
unsigned long dimension = 2;
RTree::RTreeVariant variant = RTree::RV_RSTAR;

// create R-tree
SpatialIndex::id_type indexId;
mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
leafCapacity, dimension, variant, indexId );
}

/** storage manager */
SpatialIndex::IStorageManager* mStorage;

/** R-tree containing spatial index */
SpatialIndex::ISpatialIndex* mRTree;
};

// -------------------------------------------------------------------------


QgsSpatialIndex::QgsSpatialIndex()
{
// for now only memory manager
mStorageManager = StorageManager::createNewMemoryStorageManager();

// create buffer

unsigned int capacity = 10;
bool writeThrough = false;
mStorage = StorageManager::createNewRandomEvictionsBuffer( *mStorageManager, capacity, writeThrough );

// R-Tree parameters
double fillFactor = 0.7;
unsigned long indexCapacity = 10;
unsigned long leafCapacity = 10;
unsigned long dimension = 2;
RTree::RTreeVariant variant = RTree::RV_RSTAR;

// create R-tree
SpatialIndex::id_type indexId;
mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
leafCapacity, dimension, variant, indexId );
d = new QgsSpatialIndexData;
}

QgsSpatialIndex::QgsSpatialIndex( const QgsSpatialIndex& other )
: d( other.d )
{
}

QgsSpatialIndex:: ~QgsSpatialIndex()
{
delete mRTree;
delete mStorage;
delete mStorageManager;
}


Region QgsSpatialIndex::rectToRegion( QgsRectangle rect )
{
double pt1[2], pt2[2];
Expand All @@ -89,7 +154,7 @@ Region QgsSpatialIndex::rectToRegion( QgsRectangle rect )
return Region( pt1, pt2, 2 );
}

bool QgsSpatialIndex::featureInfo( QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
bool QgsSpatialIndex::featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
{
QgsGeometry *g = f.geometry();
if ( !g )
Expand All @@ -100,7 +165,8 @@ bool QgsSpatialIndex::featureInfo( QgsFeature& f, SpatialIndex::Region& r, QgsFe
return true;
}

bool QgsSpatialIndex::insertFeature( QgsFeature& f )

bool QgsSpatialIndex::insertFeature( const QgsFeature& f )
{
Region r;
QgsFeatureId id;
Expand All @@ -110,7 +176,7 @@ bool QgsSpatialIndex::insertFeature( QgsFeature& f )
// TODO: handle possible exceptions correctly
try
{
mRTree->insertData( 0, 0, r, FID_TO_NUMBER( id ) );
d->mRTree->insertData( 0, 0, r, FID_TO_NUMBER( id ) );
return true;
}
catch ( Tools::Exception &e )
Expand All @@ -131,30 +197,30 @@ bool QgsSpatialIndex::insertFeature( QgsFeature& f )
return false;
}

bool QgsSpatialIndex::deleteFeature( QgsFeature& f )
bool QgsSpatialIndex::deleteFeature( const QgsFeature& f )
{
Region r;
QgsFeatureId id;
if ( !featureInfo( f, r, id ) )
return false;

// TODO: handle exceptions
return mRTree->deleteData( r, FID_TO_NUMBER( id ) );
return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
}

QList<QgsFeatureId> QgsSpatialIndex::intersects( QgsRectangle rect )
QList<QgsFeatureId> QgsSpatialIndex::intersects( QgsRectangle rect ) const
{
QList<QgsFeatureId> list;
QgisVisitor visitor( list );

Region r = rectToRegion( rect );

mRTree->intersectsWithQuery( r, visitor );
d->mRTree->intersectsWithQuery( r, visitor );

return list;
}

QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( QgsPoint point, int neighbors )
QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( QgsPoint point, int neighbors ) const
{
QList<QgsFeatureId> list;
QgisVisitor visitor( list );
Expand All @@ -164,7 +230,12 @@ QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( QgsPoint point, int neighb
pt[1] = point.y();
Point p( pt, 2 );

mRTree->nearestNeighborQuery( neighbors, p, visitor );
d->mRTree->nearestNeighborQuery( neighbors, p, visitor );

return list;
}

int QgsSpatialIndex::refs() const
{
return d->ref;
}
31 changes: 17 additions & 14 deletions src/core/qgsspatialindex.h
View file
Expand Up @@ -35,9 +35,12 @@ class QgsRectangle;
class QgsPoint;

#include <QList>
#include <QSharedDataPointer>

#include "qgsfeature.h"

class QgsSpatialIndexData;

class CORE_EXPORT QgsSpatialIndex
{

Expand All @@ -48,44 +51,44 @@ class CORE_EXPORT QgsSpatialIndex
/** constructor - creates R-tree */
QgsSpatialIndex();

/** copy constructor */
QgsSpatialIndex( const QgsSpatialIndex& other );

/** destructor finalizes work with spatial index */
~QgsSpatialIndex();


/* operations */

/** add feature to index */
bool insertFeature( QgsFeature& f );
bool insertFeature( const QgsFeature& f );

/** remove feature from index */
bool deleteFeature( QgsFeature& f );
bool deleteFeature( const QgsFeature& f );


/* queries */

/** returns features that intersect the specified rectangle */
QList<QgsFeatureId> intersects( QgsRectangle rect );
QList<QgsFeatureId> intersects( QgsRectangle rect ) const;

/** returns nearest neighbors (their count is specified by second parameter) */
QList<QgsFeatureId> nearestNeighbor( QgsPoint point, int neighbors );
QList<QgsFeatureId> nearestNeighbor( QgsPoint point, int neighbors ) const;

/* debugging */

//! get reference count - just for debugging!
int refs() const;

protected:
// @note not available in python bindings
SpatialIndex::Region rectToRegion( QgsRectangle rect );
static SpatialIndex::Region rectToRegion( QgsRectangle rect );
// @note not available in python bindings
bool featureInfo( QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id );
bool featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id );

private:

/** storage manager */
SpatialIndex::IStorageManager* mStorageManager;

/** buffer for index data */
SpatialIndex::StorageManager::IBuffer* mStorage;

/** R-tree containing spatial index */
SpatialIndex::ISpatialIndex* mRTree;
QSharedDataPointer<QgsSpatialIndexData> d;

};

Expand Down
1 change: 1 addition & 0 deletions tests/src/core/CMakeLists.txt
View file
Expand Up @@ -113,3 +113,4 @@ ADD_QGIS_TEST(composerscalebartest testqgscomposerscalebar.cpp )
ADD_QGIS_TEST(ogcutilstest testqgsogcutils.cpp)
ADD_QGIS_TEST(vectorlayercachetest testqgsvectorlayercache.cpp )
ADD_QGIS_TEST(maprendererjobtest testmaprendererjob.cpp )
ADD_QGIS_TEST(spatialindextest testqgsspatialindex.cpp)

0 comments on commit 5386324

Please sign in to comment.