1 /*************************************************************************** 2 qgsgenericspatialindex.h 3 ------------------------ 4 Date : December 2019 5 Copyright : (C) 2019 by Nyall Dawson 6 Email : nyall dot dawson at gmail dot com 7 *************************************************************************** 8 * * 9 * This program is free software; you can redistribute it and/or modify * 10 * it under the terms of the GNU General Public License as published by * 11 * the Free Software Foundation; either version 2 of the License, or * 12 * (at your option) any later version. * 13 * * 14 ***************************************************************************/ 15 16 #ifndef QGSGENERICSPATIALINDEX_H 17 #define QGSGENERICSPATIALINDEX_H 18 19 #include "qgis_core.h" 20 #include "qgsspatialindexutils.h" 21 #include "qgslogger.h" 22 23 #include <memory> 24 #include <QMutex> 25 #include <QString> 26 27 #define SIP_NO_FILE 28 29 #include <functional> 30 #include <spatialindex/SpatialIndex.h> 31 32 class QgsRectangle; 33 34 /** 35 * \ingroup core 36 * \class QgsGenericSpatialIndex 37 * 38 * \brief A generic rtree spatial index based on a libspatialindex backend. 39 * 40 * \note Not available in Python bindings. 41 * \since QGIS 3.12 42 */ 43 template <typename T> 44 class QgsGenericSpatialIndex 45 { 46 public: 47 48 /** 49 * Constructor for QgsGenericSpatialIndex. 50 */ QgsGenericSpatialIndex()51 QgsGenericSpatialIndex() 52 { 53 mStorageManager.reset( SpatialIndex::StorageManager::createNewMemoryStorageManager() ); 54 mRTree = createSpatialIndex( *mStorageManager ); 55 } 56 57 /** 58 * Inserts new \a data into the spatial index, with the specified \a bounds. 59 * 60 * Ownership of \a data is not transferred, and it is the caller's responsibility to ensure that 61 * it exists for the lifetime of the spatial index. 62 */ insert(T * data,const QgsRectangle & bounds)63 bool insert( T *data, const QgsRectangle &bounds ) 64 { 65 const SpatialIndex::Region r( QgsSpatialIndexUtils::rectangleToRegion( bounds ) ); 66 67 const QMutexLocker locker( &mMutex ); 68 69 const qint64 id = mNextId++; 70 mIdToData.insert( id, data ); 71 mDataToId.insert( data, id ); 72 try 73 { 74 mRTree->insertData( 0, nullptr, r, static_cast< qint64 >( id ) ); 75 return true; 76 } 77 catch ( Tools::Exception &e ) 78 { 79 Q_UNUSED( e ) 80 QgsDebugMsg( QStringLiteral( "Tools::Exception caught: " ).arg( e.what().c_str() ) ); 81 } 82 catch ( const std::exception &e ) 83 { 84 Q_UNUSED( e ) 85 QgsDebugMsg( QStringLiteral( "std::exception caught: " ).arg( e.what() ) ); 86 } 87 catch ( ... ) 88 { 89 QgsDebugMsg( QStringLiteral( "unknown spatial index exception caught" ) ); 90 } 91 92 return false; 93 } 94 95 /** 96 * Removes existing \a data from the spatial index, with the specified \a bounds. 97 * 98 * \a data is not deleted, and it is the caller's responsibility to ensure that 99 * it is appropriately cleaned up. 100 */ remove(T * data,const QgsRectangle & bounds)101 bool remove( T *data, const QgsRectangle &bounds ) 102 { 103 const SpatialIndex::Region r = QgsSpatialIndexUtils::rectangleToRegion( bounds ); 104 105 const QMutexLocker locker( &mMutex ); 106 107 const qint64 id = mDataToId.value( data, 0 ); 108 if ( id == 0 ) 109 return false; 110 111 // TODO: handle exceptions 112 const bool res = mRTree->deleteData( r, id ); 113 mDataToId.remove( data ); 114 mIdToData.remove( id ); 115 return res; 116 } 117 118 /** 119 * Performs an intersection check against the index, for data intersecting the specified \a bounds. 120 * 121 * The \a callback function will be called once for each matching data object encountered. 122 */ intersects(const QgsRectangle & bounds,const std::function<bool (T * data)> & callback)123 bool intersects( const QgsRectangle &bounds, const std::function< bool( T *data )> &callback ) const 124 { 125 GenericIndexVisitor<T> visitor( callback, mIdToData ); 126 const SpatialIndex::Region r = QgsSpatialIndexUtils::rectangleToRegion( bounds ); 127 128 const QMutexLocker locker( &mMutex ); 129 mRTree->intersectsWithQuery( r, visitor ); 130 return true; 131 } 132 133 /** 134 * Returns TRUE if the index contains no items. 135 */ isEmpty()136 bool isEmpty( ) const 137 { 138 const QMutexLocker locker( &mMutex ); 139 return mIdToData.isEmpty(); 140 } 141 142 private: 143 createSpatialIndex(SpatialIndex::IStorageManager & storageManager)144 std::unique_ptr< SpatialIndex::ISpatialIndex > createSpatialIndex( SpatialIndex::IStorageManager &storageManager ) 145 { 146 // R-Tree parameters 147 constexpr double fillFactor = 0.7; 148 constexpr unsigned long indexCapacity = 10; 149 constexpr unsigned long leafCapacity = 10; 150 constexpr unsigned long dimension = 2; 151 constexpr SpatialIndex::RTree::RTreeVariant variant = SpatialIndex::RTree::RV_RSTAR; 152 153 // create R-tree 154 SpatialIndex::id_type indexId; 155 return std::unique_ptr< SpatialIndex::ISpatialIndex >( SpatialIndex::RTree::createNewRTree( storageManager, fillFactor, indexCapacity, 156 leafCapacity, dimension, variant, indexId ) ); 157 } 158 159 std::unique_ptr< SpatialIndex::IStorageManager > mStorageManager; 160 std::unique_ptr< SpatialIndex::ISpatialIndex > mRTree; 161 162 mutable QMutex mMutex; 163 164 qint64 mNextId = 1; 165 QHash< qint64, T * > mIdToData; 166 QHash< T *, qint64 > mDataToId; 167 168 template <typename TT> 169 class GenericIndexVisitor : public SpatialIndex::IVisitor 170 { 171 public: GenericIndexVisitor(const std::function<bool (TT * data)> & callback,const QHash<qint64,TT * > & data)172 explicit GenericIndexVisitor( const std::function< bool( TT *data )> &callback, const QHash< qint64, TT * > &data ) 173 : mCallback( callback ) 174 , mData( data ) 175 {} 176 visitNode(const SpatialIndex::INode & n)177 void visitNode( const SpatialIndex::INode &n ) override 178 { Q_UNUSED( n ) } 179 visitData(const SpatialIndex::IData & d)180 void visitData( const SpatialIndex::IData &d ) override 181 { 182 const qint64 id = d.getIdentifier(); 183 T *data = mData.value( id ); 184 mCallback( data ); 185 } 186 visitData(std::vector<const SpatialIndex::IData * > & v)187 void visitData( std::vector<const SpatialIndex::IData *> &v ) override 188 { Q_UNUSED( v ) } 189 190 private: 191 const std::function< bool( TT *data )> &mCallback; 192 QHash< qint64, TT * > mData; 193 }; 194 195 }; 196 197 #endif // QGSGENERICSPATIALINDEX_H 198