QGIS API Documentation  2.99.0-Master (dcec6bb)
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 
37 class QgisVisitor : public SpatialIndex::IVisitor
38 {
39  public:
40  explicit QgisVisitor( QList<QgsFeatureId> &list )
41  : mList( list ) {}
42 
43  void visitNode( const INode &n ) override
44  { Q_UNUSED( n ); }
45 
46  void visitData( const IData &d ) override
47  {
48  mList.append( d.getIdentifier() );
49  }
50 
51  void visitData( std::vector<const IData *> &v ) override
52  { Q_UNUSED( v ); }
53 
54  private:
55  QList<QgsFeatureId> &mList;
56 };
57 
62 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
63 {
64  public:
65  explicit QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex *newIndex )
66  : mNewIndex( newIndex ) {}
67 
68  void visitNode( const INode &n ) override
69  { Q_UNUSED( n ); }
70 
71  void visitData( const IData &d ) override
72  {
73  SpatialIndex::IShape *shape = nullptr;
74  d.getShape( &shape );
75  mNewIndex->insertData( 0, nullptr, *shape, d.getIdentifier() );
76  delete shape;
77  }
78 
79  void visitData( std::vector<const IData *> &v ) override
80  { Q_UNUSED( v ); }
81 
82  private:
83  SpatialIndex::ISpatialIndex *mNewIndex = nullptr;
84 };
85 
86 
92 class QgsFeatureIteratorDataStream : public IDataStream
93 {
94  public:
96  explicit QgsFeatureIteratorDataStream( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
97  : mFi( fi )
98  , mNextData( nullptr )
99  , mFeedback( feedback )
100  {
101  readNextEntry();
102  }
103 
105  {
106  delete mNextData;
107  }
108 
110  IData *getNext() override
111  {
112  if ( mFeedback && mFeedback->isCanceled() )
113  return nullptr;
114 
115  RTree::Data *ret = mNextData;
116  mNextData = nullptr;
117  readNextEntry();
118  return ret;
119  }
120 
122  bool hasNext() override { return nullptr != mNextData; }
123 
125  uint32_t size() override { Q_ASSERT( false && "not available" ); return 0; }
126 
128  void rewind() override { Q_ASSERT( false && "not available" ); }
129 
130  protected:
132  {
133  QgsFeature f;
134  SpatialIndex::Region r;
135  QgsFeatureId id;
136  while ( mFi.nextFeature( f ) )
137  {
138  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
139  {
140  mNextData = new RTree::Data( 0, nullptr, r, id );
141  return;
142  }
143  }
144  }
145 
146  private:
147  QgsFeatureIterator mFi;
148  RTree::Data *mNextData = nullptr;
149  QgsFeedback *mFeedback = nullptr;
150 };
151 
152 
158 class QgsSpatialIndexData : public QSharedData
159 {
160  public:
162  {
163  initTree();
164  }
165 
174  explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
175  {
176  QgsFeatureIteratorDataStream fids( fi, feedback );
177  initTree( &fids );
178  }
179 
181  : QSharedData( other )
182  {
183  initTree();
184 
185  // copy R-tree data one by one (is there a faster way??)
186  double low[] = { DBL_MIN, DBL_MIN };
187  double high[] = { DBL_MAX, DBL_MAX };
188  SpatialIndex::Region query( low, high, 2 );
189  QgsSpatialIndexCopyVisitor visitor( mRTree );
190  other.mRTree->intersectsWithQuery( query, visitor );
191  }
192 
194  {
195  delete mRTree;
196  delete mStorage;
197  }
198 
199  void initTree( IDataStream *inputStream = nullptr )
200  {
201  // for now only memory manager
202  mStorage = StorageManager::createNewMemoryStorageManager();
203 
204  // R-Tree parameters
205  double fillFactor = 0.7;
206  unsigned long indexCapacity = 10;
207  unsigned long leafCapacity = 10;
208  unsigned long dimension = 2;
209  RTree::RTreeVariant variant = RTree::RV_RSTAR;
210 
211  // create R-tree
212  SpatialIndex::id_type indexId;
213 
214  if ( inputStream )
215  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
216  leafCapacity, dimension, variant, indexId );
217  else
218  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
219  leafCapacity, dimension, variant, indexId );
220  }
221 
223  SpatialIndex::IStorageManager *mStorage = nullptr;
224 
226  SpatialIndex::ISpatialIndex *mRTree = nullptr;
227 
228  private:
229 
230  QgsSpatialIndexData &operator=( const QgsSpatialIndexData &rh );
231 };
232 
233 // -------------------------------------------------------------------------
234 
235 
237 {
238  d = new QgsSpatialIndexData;
239 }
240 
242 {
243  d = new QgsSpatialIndexData( fi, feedback );
244 }
245 
247 {
248  d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) ), feedback );
249 }
250 
252  : d( other.d )
253 {
254 }
255 
257 {
258 }
259 
261 {
262  if ( this != &other )
263  d = other.d;
264  return *this;
265 }
266 
267 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle &rect )
268 {
269  double pt1[2] = { rect.xMinimum(), rect.yMinimum() },
270  pt2[2] = { rect.xMaximum(), rect.yMaximum() };
271  return SpatialIndex::Region( pt1, pt2, 2 );
272 }
273 
274 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id )
275 {
276  QgsRectangle rect;
277  if ( !featureInfo( f, rect, id ) )
278  return false;
279 
280  r = rectToRegion( rect );
281  return true;
282 }
283 
284 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, QgsRectangle &rect, QgsFeatureId &id )
285 {
286  if ( !f.hasGeometry() )
287  return false;
288 
289  id = f.id();
290  rect = f.geometry().boundingBox();
291  return true;
292 }
293 
295 {
296  QgsRectangle rect;
297  QgsFeatureId id;
298  if ( !featureInfo( f, rect, id ) )
299  return false;
300 
301  return insertFeature( id, rect );
302 }
303 
305 {
306  SpatialIndex::Region r( rectToRegion( rect ) );
307 
308  // TODO: handle possible exceptions correctly
309  try
310  {
311  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
312  return true;
313  }
314  catch ( Tools::Exception &e )
315  {
316  Q_UNUSED( e );
317  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
318  }
319  catch ( const std::exception &e )
320  {
321  Q_UNUSED( e );
322  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
323  }
324  catch ( ... )
325  {
326  QgsDebugMsg( "unknown spatial index exception caught" );
327  }
328 
329  return false;
330 }
331 
333 {
334  SpatialIndex::Region r;
335  QgsFeatureId id;
336  if ( !featureInfo( f, r, id ) )
337  return false;
338 
339  // TODO: handle exceptions
340  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
341 }
342 
343 QList<QgsFeatureId> QgsSpatialIndex::intersects( const QgsRectangle &rect ) const
344 {
345  QList<QgsFeatureId> list;
346  QgisVisitor visitor( list );
347 
348  SpatialIndex::Region r = rectToRegion( rect );
349 
350  d->mRTree->intersectsWithQuery( r, visitor );
351 
352  return list;
353 }
354 
355 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
356 {
357  QList<QgsFeatureId> list;
358  QgisVisitor visitor( list );
359 
360  double pt[2] = { point.x(), point.y() };
361  Point p( pt, 2 );
362 
363  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
364 
365  return list;
366 }
367 
368 QAtomicInt QgsSpatialIndex::refs() const
369 {
370  return d->ref;
371 }
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:70
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
Definition: qgsrectangle.h:38
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:47
A class to represent a 2D point.
Definition: qgspointxy.h:42
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:61
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:43
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:46
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:106
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:91
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:96
qint64 QgsFeatureId
Definition: qgsfeature.h:37
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:101
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!