QGIS API Documentation  2.99.0-Master (f1c3692)
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.h"
27 
28 using namespace SpatialIndex;
29 
30 
31 
38 class QgisVisitor : public SpatialIndex::IVisitor
39 {
40  public:
41  explicit QgisVisitor( QList<QgsFeatureId> &list )
42  : mList( list ) {}
43 
44  void visitNode( const INode &n ) override
45  { Q_UNUSED( n ); }
46 
47  void visitData( const IData &d ) override
48  {
49  mList.append( d.getIdentifier() );
50  }
51 
52  void visitData( std::vector<const IData *> &v ) override
53  { Q_UNUSED( v ); }
54 
55  private:
56  QList<QgsFeatureId> &mList;
57 };
58 
64 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
65 {
66  public:
67  explicit QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex *newIndex )
68  : mNewIndex( newIndex ) {}
69 
70  void visitNode( const INode &n ) override
71  { Q_UNUSED( n ); }
72 
73  void visitData( const IData &d ) override
74  {
75  SpatialIndex::IShape *shape = nullptr;
76  d.getShape( &shape );
77  mNewIndex->insertData( 0, nullptr, *shape, d.getIdentifier() );
78  delete shape;
79  }
80 
81  void visitData( std::vector<const IData *> &v ) override
82  { Q_UNUSED( v ); }
83 
84  private:
85  SpatialIndex::ISpatialIndex *mNewIndex = nullptr;
86 };
87 
88 
95 class QgsFeatureIteratorDataStream : public IDataStream
96 {
97  public:
99  explicit QgsFeatureIteratorDataStream( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
100  : mFi( fi )
101  , mFeedback( feedback )
102  {
103  readNextEntry();
104  }
105 
107  {
108  delete mNextData;
109  }
110 
112  IData *getNext() override
113  {
114  if ( mFeedback && mFeedback->isCanceled() )
115  return nullptr;
116 
117  RTree::Data *ret = mNextData;
118  mNextData = nullptr;
119  readNextEntry();
120  return ret;
121  }
122 
124  bool hasNext() override { return nullptr != mNextData; }
125 
127  uint32_t size() override { Q_ASSERT( false && "not available" ); return 0; }
128 
130  void rewind() override { Q_ASSERT( false && "not available" ); }
131 
132  protected:
134  {
135  QgsFeature f;
136  SpatialIndex::Region r;
137  QgsFeatureId id;
138  while ( mFi.nextFeature( f ) )
139  {
140  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
141  {
142  mNextData = new RTree::Data( 0, nullptr, r, id );
143  return;
144  }
145  }
146  }
147 
148  private:
149  QgsFeatureIterator mFi;
150  RTree::Data *mNextData = nullptr;
151  QgsFeedback *mFeedback = nullptr;
152 };
153 
154 
161 class QgsSpatialIndexData : public QSharedData
162 {
163  public:
165  {
166  initTree();
167  }
168 
177  explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
178  {
179  QgsFeatureIteratorDataStream fids( fi, feedback );
180  initTree( &fids );
181  }
182 
184  : QSharedData( other )
185  {
186  initTree();
187 
188  // copy R-tree data one by one (is there a faster way??)
189  double low[] = { DBL_MIN, DBL_MIN };
190  double high[] = { DBL_MAX, DBL_MAX };
191  SpatialIndex::Region query( low, high, 2 );
192  QgsSpatialIndexCopyVisitor visitor( mRTree );
193  other.mRTree->intersectsWithQuery( query, visitor );
194  }
195 
197  {
198  delete mRTree;
199  delete mStorage;
200  }
201 
202  QgsSpatialIndexData &operator=( const QgsSpatialIndexData &rh ) = delete;
203 
204  void initTree( IDataStream *inputStream = nullptr )
205  {
206  // for now only memory manager
207  mStorage = StorageManager::createNewMemoryStorageManager();
208 
209  // R-Tree parameters
210  double fillFactor = 0.7;
211  unsigned long indexCapacity = 10;
212  unsigned long leafCapacity = 10;
213  unsigned long dimension = 2;
214  RTree::RTreeVariant variant = RTree::RV_RSTAR;
215 
216  // create R-tree
217  SpatialIndex::id_type indexId;
218 
219  if ( inputStream )
220  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
221  leafCapacity, dimension, variant, indexId );
222  else
223  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
224  leafCapacity, dimension, variant, indexId );
225  }
226 
228  SpatialIndex::IStorageManager *mStorage = nullptr;
229 
231  SpatialIndex::ISpatialIndex *mRTree = nullptr;
232 
233 };
234 
235 // -------------------------------------------------------------------------
236 
237 
239 {
240  d = new QgsSpatialIndexData;
241 }
242 
244 {
245  d = new QgsSpatialIndexData( fi, feedback );
246 }
247 
249 {
250  d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) ), feedback );
251 }
252 
254  : d( other.d )
255 {
256 }
257 
259 {
260 }
261 
263 {
264  if ( this != &other )
265  d = other.d;
266  return *this;
267 }
268 
269 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle &rect )
270 {
271  double pt1[2] = { rect.xMinimum(), rect.yMinimum() },
272  pt2[2] = { rect.xMaximum(), rect.yMaximum() };
273  return SpatialIndex::Region( pt1, pt2, 2 );
274 }
275 
276 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id )
277 {
278  QgsRectangle rect;
279  if ( !featureInfo( f, rect, id ) )
280  return false;
281 
282  r = rectToRegion( rect );
283  return true;
284 }
285 
286 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, QgsRectangle &rect, QgsFeatureId &id )
287 {
288  if ( !f.hasGeometry() )
289  return false;
290 
291  id = f.id();
292  rect = f.geometry().boundingBox();
293  return true;
294 }
295 
297 {
298  QgsRectangle rect;
299  QgsFeatureId id;
300  if ( !featureInfo( f, rect, id ) )
301  return false;
302 
303  return insertFeature( id, rect );
304 }
305 
307 {
308  SpatialIndex::Region r( rectToRegion( rect ) );
309 
310  // TODO: handle possible exceptions correctly
311  try
312  {
313  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
314  return true;
315  }
316  catch ( Tools::Exception &e )
317  {
318  Q_UNUSED( e );
319  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
320  }
321  catch ( const std::exception &e )
322  {
323  Q_UNUSED( e );
324  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
325  }
326  catch ( ... )
327  {
328  QgsDebugMsg( "unknown spatial index exception caught" );
329  }
330 
331  return false;
332 }
333 
335 {
336  SpatialIndex::Region r;
337  QgsFeatureId id;
338  if ( !featureInfo( f, r, id ) )
339  return false;
340 
341  // TODO: handle exceptions
342  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
343 }
344 
345 QList<QgsFeatureId> QgsSpatialIndex::intersects( const QgsRectangle &rect ) const
346 {
347  QList<QgsFeatureId> list;
348  QgisVisitor visitor( list );
349 
350  SpatialIndex::Region r = rectToRegion( rect );
351 
352  d->mRTree->intersectsWithQuery( r, visitor );
353 
354  return list;
355 }
356 
357 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
358 {
359  QList<QgsFeatureId> list;
360  QgisVisitor visitor( list );
361 
362  double pt[2] = { point.x(), point.y() };
363  Point p( pt, 2 );
364 
365  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
366 
367  return list;
368 }
369 
370 QAtomicInt QgsSpatialIndex::refs() const
371 {
372  return d->ref;
373 }
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:71
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
Definition: qgsrectangle.h:39
QgsSpatialIndex & operator=(const QgsSpatialIndex &other)
Implement assignment operator.
SpatialIndex::ISpatialIndex * mRTree
R-tree containing spatial index.
QList< QgsFeatureId > nearestNeighbor(const QgsPointXY &point, int neighbors) const
Returns nearest neighbors (their count is specified by second parameter)
bool deleteFeature(const QgsFeature &f)
Remove feature from index.
#define QgsDebugMsg(str)
Definition: qgslogger.h:37
double y
Definition: qgspointxy.h:48
A class to represent a 2D point.
Definition: qgspointxy.h:43
QList< QgsFeatureId > intersects(const QgsRectangle &rect) const
Returns features that intersect the specified rectangle.
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
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:62
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:190
QgsSpatialIndexCopyVisitor(SpatialIndex::ISpatialIndex *newIndex)
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 cancelation of something running in a worker thread...
Definition: qgsfeedback.h:44
QgisVisitor(QList< QgsFeatureId > &list)
void visitData(std::vector< const IData *> &v) override
#define FID_TO_NUMBER(fid)
Definition: qgsfeature.h:51
Data of spatial index that may be implicitly shared.
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 - creates R-tree.
void visitData(std::vector< const IData *> &v) override
Utility class for bulk loading of R-trees.
QgsGeometry geometry() const
Returns the geometry associated with this feature.
Definition: qgsfeature.cpp:101
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...
void visitData(const IData &d) override
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:126
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:111
uint32_t size() override
returns the total number of entries available in the stream.
bool insertFeature(const QgsFeature &f)
Add feature to index.
~QgsSpatialIndex()
Destructor finalizes work with spatial index.
An interface for objects which provide features via a getFeatures method.
Custom visitor that adds found features to list.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:116
qint64 QgsFeatureId
Definition: qgsfeature.h:37
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:121
QList< int > QgsAttributeList
Definition: qgsfield.h:27
virtual QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest()) const =0
Returns an iterator for the features in the source.
QAtomicInt refs() const
get reference count - just for debugging!