QGIS API Documentation  3.4.15-Madeira (e83d02e274)
qgsspatialindex.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsspatialindex.cpp - 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 #include "qgsspatialindex.h"
17 
18 #include "qgsgeometry.h"
19 #include "qgsfeature.h"
20 #include "qgsfeatureiterator.h"
21 #include "qgsrectangle.h"
22 #include "qgslogger.h"
23 #include "qgsfeaturesource.h"
24 #include "qgsfeedback.h"
25 
26 #include <spatialindex/SpatialIndex.h>
27 #include <QMutex>
28 #include <QMutexLocker>
29 
30 using namespace SpatialIndex;
31 
32 
33 
40 class QgisVisitor : public SpatialIndex::IVisitor
41 {
42  public:
43  explicit QgisVisitor( QList<QgsFeatureId> &list )
44  : mList( list ) {}
45 
46  void visitNode( const INode &n ) override
47  { Q_UNUSED( n ); }
48 
49  void visitData( const IData &d ) override
50  {
51  mList.append( d.getIdentifier() );
52  }
53 
54  void visitData( std::vector<const IData *> &v ) override
55  { Q_UNUSED( v ); }
56 
57  private:
58  QList<QgsFeatureId> &mList;
59 };
60 
66 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
67 {
68  public:
69  explicit QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex *newIndex )
70  : mNewIndex( newIndex ) {}
71 
72  void visitNode( const INode &n ) override
73  { Q_UNUSED( n ); }
74 
75  void visitData( const IData &d ) override
76  {
77  SpatialIndex::IShape *shape = nullptr;
78  d.getShape( &shape );
79  mNewIndex->insertData( 0, nullptr, *shape, d.getIdentifier() );
80  delete shape;
81  }
82 
83  void visitData( std::vector<const IData *> &v ) override
84  { Q_UNUSED( v ); }
85 
86  private:
87  SpatialIndex::ISpatialIndex *mNewIndex = nullptr;
88 };
89 
90 
97 class QgsFeatureIteratorDataStream : public IDataStream
98 {
99  public:
101  explicit QgsFeatureIteratorDataStream( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
102  : mFi( fi )
103  , mFeedback( feedback )
104  {
105  readNextEntry();
106  }
107 
109  {
110  delete mNextData;
111  }
112 
114  IData *getNext() override
115  {
116  if ( mFeedback && mFeedback->isCanceled() )
117  return nullptr;
118 
119  RTree::Data *ret = mNextData;
120  mNextData = nullptr;
121  readNextEntry();
122  return ret;
123  }
124 
126  bool hasNext() override { return nullptr != mNextData; }
127 
129  uint32_t size() override { Q_ASSERT( false && "not available" ); return 0; }
130 
132  void rewind() override { Q_ASSERT( false && "not available" ); }
133 
134  protected:
136  {
137  QgsFeature f;
138  SpatialIndex::Region r;
139  QgsFeatureId id;
140  while ( mFi.nextFeature( f ) )
141  {
142  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
143  {
144  mNextData = new RTree::Data( 0, nullptr, r, id );
145  return;
146  }
147  }
148  }
149 
150  private:
151  QgsFeatureIterator mFi;
152  RTree::Data *mNextData = nullptr;
153  QgsFeedback *mFeedback = nullptr;
154 };
155 
156 
163 class QgsSpatialIndexData : public QSharedData
164 {
165  public:
167  {
168  initTree();
169  }
170 
179  explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
180  {
181  QgsFeatureIteratorDataStream fids( fi, feedback );
182  initTree( &fids );
183  }
184 
186  : QSharedData( other )
187  {
188  QMutexLocker locker( &other.mMutex );
189 
190  initTree();
191 
192  // copy R-tree data one by one (is there a faster way??)
193  double low[] = { std::numeric_limits<double>::lowest(), std::numeric_limits<double>::lowest() };
194  double high[] = { std::numeric_limits<double>::max(), std::numeric_limits<double>::max() };
195  SpatialIndex::Region query( low, high, 2 );
196  QgsSpatialIndexCopyVisitor visitor( mRTree );
197  other.mRTree->intersectsWithQuery( query, visitor );
198  }
199 
201  {
202  delete mRTree;
203  delete mStorage;
204  }
205 
206  QgsSpatialIndexData &operator=( const QgsSpatialIndexData &rh ) = delete;
207 
208  void initTree( IDataStream *inputStream = nullptr )
209  {
210  // for now only memory manager
211  mStorage = StorageManager::createNewMemoryStorageManager();
212 
213  // R-Tree parameters
214  double fillFactor = 0.7;
215  unsigned long indexCapacity = 10;
216  unsigned long leafCapacity = 10;
217  unsigned long dimension = 2;
218  RTree::RTreeVariant variant = RTree::RV_RSTAR;
219 
220  // create R-tree
221  SpatialIndex::id_type indexId;
222 
223  if ( inputStream && inputStream->hasNext() )
224  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
225  leafCapacity, dimension, variant, indexId );
226  else
227  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
228  leafCapacity, dimension, variant, indexId );
229  }
230 
232  SpatialIndex::IStorageManager *mStorage = nullptr;
233 
235  SpatialIndex::ISpatialIndex *mRTree = nullptr;
236 
237  mutable QMutex mMutex;
238 
239 };
240 
241 // -------------------------------------------------------------------------
242 
243 
245 {
246  d = new QgsSpatialIndexData;
247 }
248 
250 {
251  d = new QgsSpatialIndexData( fi, feedback );
252 }
253 
255 {
256  d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setNoAttributes() ), feedback );
257 }
258 
260  : d( other.d )
261 {
262 }
263 
265 {
266 }
267 
269 {
270  if ( this != &other )
271  d = other.d;
272  return *this;
273 }
274 
275 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle &rect )
276 {
277  double pt1[2] = { rect.xMinimum(), rect.yMinimum() },
278  pt2[2] = { rect.xMaximum(), rect.yMaximum() };
279  return SpatialIndex::Region( pt1, pt2, 2 );
280 }
281 
282 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id )
283 {
284  QgsRectangle rect;
285  if ( !featureInfo( f, rect, id ) )
286  return false;
287 
288  r = rectToRegion( rect );
289  return true;
290 }
291 
292 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, QgsRectangle &rect, QgsFeatureId &id )
293 {
294  if ( !f.hasGeometry() )
295  return false;
296 
297  id = f.id();
298  rect = f.geometry().boundingBox();
299 
300  if ( !rect.isFinite() )
301  return false;
302 
303  return true;
304 }
305 
306 bool QgsSpatialIndex::addFeature( QgsFeature &feature, QgsFeatureSink::Flags )
307 {
308  QgsRectangle rect;
309  QgsFeatureId id;
310  if ( !featureInfo( feature, rect, id ) )
311  return false;
312 
313  return addFeature( id, rect );
314 }
315 
316 bool QgsSpatialIndex::addFeatures( QgsFeatureList &features, QgsFeatureSink::Flags flags )
317 {
318  QgsFeatureList::iterator fIt = features.begin();
319  bool result = true;
320  for ( ; fIt != features.end(); ++fIt )
321  {
322  result = result && addFeature( *fIt, flags );
323  }
324  return result;
325 }
326 
328 {
329  QgsFeature feature( f );
330  return addFeature( feature );
331 }
332 
334 {
335  return addFeature( id, bounds );
336 }
337 
339 {
340  SpatialIndex::Region r( rectToRegion( bounds ) );
341 
342  QMutexLocker locker( &d->mMutex );
343 
344  // TODO: handle possible exceptions correctly
345  try
346  {
347  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
348  return true;
349  }
350  catch ( Tools::Exception &e )
351  {
352  Q_UNUSED( e );
353  QgsDebugMsg( QStringLiteral( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
354  }
355  catch ( const std::exception &e )
356  {
357  Q_UNUSED( e );
358  QgsDebugMsg( QStringLiteral( "std::exception caught: " ).arg( e.what() ) );
359  }
360  catch ( ... )
361  {
362  QgsDebugMsg( QStringLiteral( "unknown spatial index exception caught" ) );
363  }
364 
365  return false;
366 }
367 
369 {
370  SpatialIndex::Region r;
371  QgsFeatureId id;
372  if ( !featureInfo( f, r, id ) )
373  return false;
374 
375  QMutexLocker locker( &d->mMutex );
376  // TODO: handle exceptions
377  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
378 }
379 
380 QList<QgsFeatureId> QgsSpatialIndex::intersects( const QgsRectangle &rect ) const
381 {
382  QList<QgsFeatureId> list;
383  QgisVisitor visitor( list );
384 
385  SpatialIndex::Region r = rectToRegion( rect );
386 
387  QMutexLocker locker( &d->mMutex );
388  d->mRTree->intersectsWithQuery( r, visitor );
389 
390  return list;
391 }
392 
393 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
394 {
395  QList<QgsFeatureId> list;
396  QgisVisitor visitor( list );
397 
398  double pt[2] = { point.x(), point.y() };
399  Point p( pt, 2 );
400 
401  QMutexLocker locker( &d->mMutex );
402  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
403 
404  return list;
405 }
406 
407 QAtomicInt QgsSpatialIndex::refs() const
408 {
409  return d->ref;
410 }
bool hasNext() override
returns true if there are more items in the stream.
IData * getNext() override
returns a pointer to the next entry in the stream or 0 at the end of the stream.
QgsFeatureId id
Definition: qgsfeature.h:64
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
Definition: qgsrectangle.h:40
QgsSpatialIndex & operator=(const QgsSpatialIndex &other)
Implement assignment operator.
SpatialIndex::ISpatialIndex * mRTree
R-tree containing spatial index.
bool isFinite() const
Returns true if the rectangle has finite boundaries.
Definition: qgsrectangle.h:515
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:171
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
QList< QgsFeature > QgsFeatureList
Definition: qgsfeature.h:571
double y
Definition: qgspointxy.h:48
A class to represent a 2D point.
Definition: qgspointxy.h:43
void visitData(std::vector< const IData * > &v) override
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
qint64 QgsFeatureId
Definition: qgsfeatureid.h:25
QgsFeatureIteratorDataStream(const QgsFeatureIterator &fi, QgsFeedback *feedback=nullptr)
constructor - needs to load all data to a vector for later access when bulk loading ...
void visitNode(const INode &n) override
Q_DECL_DEPRECATED bool insertFeature(const QgsFeature &feature)
Adds a feature to the index.
void initTree(IDataStream *inputStream=nullptr)
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:55
QgsSpatialIndexCopyVisitor(SpatialIndex::ISpatialIndex *newIndex)
void visitData(std::vector< const IData * > &v) override
void rewind() override
sets the stream pointer to the first entry, if possible.
QgsSpatialIndexData(const QgsSpatialIndexData &other)
void visitNode(const INode &n) override
Base class for feedback objects to be used for cancellation of something running in a worker thread...
Definition: qgsfeedback.h:44
QgisVisitor(QList< QgsFeatureId > &list)
QList< QgsFeatureId > nearestNeighbor(const QgsPointXY &point, int neighbors) const
Returns nearest neighbors to a point.
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:176
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:161
Data of spatial index that may be implicitly shared.
QList< QgsFeatureId > intersects(const QgsRectangle &rectangle) const
Returns a list of features with a bounding box which intersects the specified rectangle.
This class wraps a request for features to a vector layer (or directly its vector data provider)...
void visitData(const IData &d) override
QgsSpatialIndex()
Constructor for QgsSpatialIndex.
Utility class for bulk loading of R-trees.
double x
Definition: qgspointxy.h:47
QgsSpatialIndexData(const QgsFeatureIterator &fi, QgsFeedback *feedback=nullptr)
Constructor for QgsSpatialIndexData which bulk loads features from the specified feature iterator fi...
QAtomicInt refs() const
Gets reference count - just for debugging!
void visitData(const IData &d) override
uint32_t size() override
returns the total number of entries available in the stream.
bool deleteFeature(const QgsFeature &feature)
Removes a feature from the index.
A spatial index for QgsFeature objects.
An interface for objects which provide features via a getFeatures method.
bool addFeatures(QgsFeatureList &features, QgsFeatureSink::Flags flags=nullptr) override
Adds a list of features to the index.
Custom visitor that adds found features to list.
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:197
#define FID_TO_NUMBER(fid)
Definition: qgsfeatureid.h:29
QgsGeometry geometry
Definition: qgsfeature.h:67
bool addFeature(QgsFeature &feature, QgsFeatureSink::Flags flags=nullptr) override
Adds a feature to the index.
~QgsSpatialIndex() override
Destructor finalizes work with spatial index.
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:166
virtual QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest()) const =0
Returns an iterator for the features in the source.