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