1 /*************************************************************************** 2 qgsspatialindex.h - wrapper class for spatial index library 3 ---------------------- 4 begin : December 2006 5 copyright : (C) 2006 by Martin Dobias 6 email : wonder.sk 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 QGSSPATIALINDEX_H 17 #define QGSSPATIALINDEX_H 18 19 20 #include "qgis_sip.h" 21 22 // forward declaration 23 namespace SpatialIndex SIP_SKIP 24 { 25 class IStorageManager; 26 class ISpatialIndex; 27 class Region; 28 class Point; 29 30 namespace StorageManager 31 { 32 class IBuffer; 33 } 34 } 35 36 class QgsFeedback; 37 class QgsFeature; 38 class QgsRectangle; 39 class QgsPointXY; 40 41 #include "qgis_core.h" 42 #include "qgsfeaturesink.h" 43 #include <QList> 44 #include <QSharedDataPointer> 45 46 #include "qgsfeature.h" 47 48 class QgsSpatialIndexData; 49 class QgsFeatureIterator; 50 class QgsFeatureSource; 51 52 /** 53 * \ingroup core 54 * \class QgsSpatialIndex 55 * 56 * \brief A spatial index for QgsFeature objects. 57 * 58 * QgsSpatialIndex objects are implicitly shared and can be inexpensively copied. 59 * 60 * \note While the underlying libspatialindex is not thread safe on some platforms, the QgsSpatialIndex 61 * class implements its own locks and accordingly, a single QgsSpatialIndex object can safely 62 * be used across multiple threads. 63 * 64 * \see QgsSpatialIndexKDBush, which is an optimised non-mutable index for point geometries only. 65 * \see QgsMeshSpatialIndex, which is for mesh faces 66 */ 67 class CORE_EXPORT QgsSpatialIndex : public QgsFeatureSink 68 { 69 70 public: 71 72 /* creation of spatial index */ 73 74 //! Flags controlling index behavior 75 enum Flag 76 { 77 FlagStoreFeatureGeometries = 1 << 0, //!< Indicates that the spatial index should also store feature geometries. This requires more memory, but can speed up operations by avoiding additional requests to data providers to fetch matching feature geometries. Additionally, it is required for non-bounding box nearest neighbor searches. 78 }; 79 Q_DECLARE_FLAGS( Flags, Flag ) 80 81 /** 82 * Constructor for QgsSpatialIndex. Creates an empty R-tree index. 83 */ 84 QgsSpatialIndex( QgsSpatialIndex::Flags flags = QgsSpatialIndex::Flags() ); 85 86 /** 87 * Constructor - creates R-tree and bulk loads it with features from the iterator. 88 * This is much faster approach than creating an empty index and then inserting features one by one. 89 * 90 * The optional \a feedback object can be used to allow cancellation of bulk feature loading. Ownership 91 * of \a feedback is not transferred, and callers must take care that the lifetime of feedback exceeds 92 * that of the spatial index construction. 93 * 94 * \since QGIS 2.8 95 */ 96 explicit QgsSpatialIndex( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = QgsSpatialIndex::Flags() ); 97 98 #ifndef SIP_RUN 99 100 /** 101 * Constructor - creates R-tree and bulk loads it with features from the iterator. 102 * This is much faster approach than creating an empty index and then inserting features one by one. 103 * 104 * This construct and bulk load variant allows for a \a callback function to be specified, which is 105 * called for each added feature in turn. It allows for bulk spatial index load along with other feature 106 * based operations on a single iteration through a feature source. If \a callback returns FALSE, the 107 * load and iteration is canceled. 108 * 109 * \note Not available in Python bindings 110 * \since QGIS 2.12 111 */ 112 explicit QgsSpatialIndex( const QgsFeatureIterator &fi, const std::function< bool( const QgsFeature & ) > &callback, QgsSpatialIndex::Flags flags = QgsSpatialIndex::Flags() ); 113 #endif 114 115 /** 116 * Constructor - creates R-tree and bulk loads it with features from the source. 117 * This is much faster approach than creating an empty index and then inserting features one by one. 118 * 119 * The optional \a feedback object can be used to allow cancellation of bulk feature loading. Ownership 120 * of \a feedback is not transferred, and callers must take care that the lifetime of feedback exceeds 121 * that of the spatial index construction. 122 123 * 124 * \since QGIS 3.0 125 */ 126 explicit QgsSpatialIndex( const QgsFeatureSource &source, QgsFeedback *feedback = nullptr, QgsSpatialIndex::Flags flags = QgsSpatialIndex::Flags() ); 127 128 //! Copy constructor 129 QgsSpatialIndex( const QgsSpatialIndex &other ); 130 131 //! Destructor finalizes work with spatial index 132 ~QgsSpatialIndex() override; 133 134 //! Implement assignment operator 135 QgsSpatialIndex &operator=( const QgsSpatialIndex &other ); 136 137 /* operations */ 138 139 /** 140 * Adds a \a feature to the index. 141 * \deprecated Use addFeature() instead 142 */ 143 Q_DECL_DEPRECATED bool insertFeature( const QgsFeature &feature ) SIP_DEPRECATED; 144 145 /** 146 * Adds a \a feature to the index. 147 * 148 * The \a flags argument is ignored. 149 * 150 * \since QGIS 3.4 151 */ 152 bool addFeature( QgsFeature &feature, QgsFeatureSink::Flags flags = QgsFeatureSink::Flags() ) override; 153 154 /** 155 * Adds a list of \a features to the index. 156 * 157 * The \a flags argument is ignored. 158 * 159 * \see addFeature() 160 */ 161 bool addFeatures( QgsFeatureList &features, QgsFeatureSink::Flags flags = QgsFeatureSink::Flags() ) override; 162 163 /** 164 * Add a feature \a id to the index with a specified bounding box. 165 * \returns TRUE if feature was successfully added to index. 166 * \deprecated Use addFeature() instead 167 */ 168 Q_DECL_DEPRECATED bool insertFeature( QgsFeatureId id, const QgsRectangle &bounds ) SIP_DEPRECATED; 169 170 /** 171 * Add a feature \a id to the index with a specified bounding box. 172 * \returns TRUE if feature was successfully added to index. 173 * \since QGIS 3.4 174 */ 175 bool addFeature( QgsFeatureId id, const QgsRectangle &bounds ); 176 177 /** 178 * Removes a \a feature from the index. 179 */ 180 bool deleteFeature( const QgsFeature &feature ); 181 182 183 /* queries */ 184 185 /** 186 * Returns a list of features with a bounding box which intersects the specified \a rectangle. 187 * 188 * \note The intersection test is performed based on the feature bounding boxes only, so for non-point 189 * geometry features it is necessary to manually test the returned features for exact geometry intersection 190 * when required. 191 */ 192 QList<QgsFeatureId> intersects( const QgsRectangle &rectangle ) const; 193 194 /** 195 * Returns nearest neighbors to a \a point. The number of neighbors returned is specified 196 * by the \a neighbors argument. 197 * 198 * If the \a maxDistance argument is greater than 0, then only features within the specified 199 * distance of \a point will be considered. 200 * 201 * Note that in some cases the number of returned features may differ from the requested 202 * number of \a neighbors. E.g. if not enough features exist within the \a maxDistance of the 203 * search point. If multiple features are equidistant from the search \a point then the 204 * number of returned feature IDs may exceed \a neighbors. 205 * 206 * \warning If this QgsSpatialIndex object was not constructed with the FlagStoreFeatureGeometries flag, 207 * then the nearest neighbor test is performed based on the feature bounding boxes ONLY, so for non-point 208 * geometry features this method is not guaranteed to return the actual closest neighbors. 209 */ 210 QList<QgsFeatureId> nearestNeighbor( const QgsPointXY &point, int neighbors = 1, double maxDistance = 0 ) const; 211 212 /** 213 * Returns nearest neighbors to a \a geometry. The number of neighbors returned is specified 214 * by the \a neighbors argument. 215 * 216 * If the \a maxDistance argument is greater than 0, then only features within the specified 217 * distance of \a point will be considered. 218 * 219 * Note that in some cases the number of returned features may differ from the requested 220 * number of \a neighbors. E.g. if not enough features exist within the \a maxDistance of the 221 * search point. If multiple features are equidistant from the search \a point then the 222 * number of returned feature IDs may exceed \a neighbors. 223 * 224 * \warning If this QgsSpatialIndex object was not constructed with the FlagStoreFeatureGeometries flag, 225 * then the nearest neighbor test is performed based on the feature bounding boxes ONLY, so for non-point 226 * geometry features this method is not guaranteed to return the actual closest neighbors. 227 * 228 * \since QGIS 3.8 229 */ 230 QList<QgsFeatureId> nearestNeighbor( const QgsGeometry &geometry, int neighbors = 1, double maxDistance = 0 ) const; 231 232 #ifndef SIP_RUN 233 234 /** 235 * Returns the stored geometry for the indexed feature with matching \a id. 236 * 237 * Geometry is only stored if the QgsSpatialIndex was created with the FlagStoreFeatureGeometries flag. 238 * 239 * \since QGIS 3.6 240 */ 241 QgsGeometry geometry( QgsFeatureId id ) const; 242 243 #else 244 245 /** 246 * Returns the stored geometry for the indexed feature with matching \a id. 247 * 248 * Geometry is only stored if the QgsSpatialIndex was created with the FlagStoreFeatureGeometries flag. 249 * 250 * \throws KeyError if no geometry with the specified feature id exists in the index. 251 * 252 * \since QGIS 3.6 253 */ 254 SIP_PYOBJECT geometry( QgsFeatureId id ) const SIP_TYPEHINT( QgsGeometry ); 255 % MethodCode 256 std::unique_ptr< QgsGeometry > g = std::make_unique< QgsGeometry >( sipCpp->geometry( a0 ) ); 257 if ( g->isNull() ) 258 { 259 PyErr_SetString( PyExc_KeyError, QStringLiteral( "No geometry with feature id %1 exists in the index." ).arg( a0 ).toUtf8().constData() ); 260 sipIsErr = 1; 261 } 262 else 263 { 264 sipRes = sipConvertFromType( g.release(), sipType_QgsGeometry, Py_None ); 265 } 266 % End 267 #endif 268 269 /* debugging */ 270 271 //! Gets reference count - just for debugging! 272 QAtomicInt SIP_PYALTERNATIVETYPE( int ) refs() const; 273 274 private: 275 276 /** 277 * Calculates feature info to insert into index. 278 * \param f input feature 279 * \param r will be set to spatial index region 280 * \param id will be set to feature's ID 281 * \returns TRUE if feature info was successfully retrieved and the feature can be added to 282 * the index 283 */ 284 static bool featureInfo( const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id ) SIP_SKIP; 285 286 /** 287 * Calculates feature info to insert into index. 288 * \param f input feature 289 * \param rect will be set to feature's geometry bounding box 290 * \param id will be set to feature's ID 291 * \returns TRUE if feature info was successfully retrieved and the feature can be added to 292 * the index 293 * \since QGIS 3.0 294 */ 295 static bool featureInfo( const QgsFeature &f, QgsRectangle &rect, QgsFeatureId &id ); 296 297 friend class QgsFeatureIteratorDataStream; // for access to featureInfo() 298 299 private: 300 301 QSharedDataPointer<QgsSpatialIndexData> d; 302 303 }; 304 305 Q_DECLARE_OPERATORS_FOR_FLAGS( QgsSpatialIndex::Flags ) 306 307 #endif //QGSSPATIALINDEX_H 308