QGIS API Documentation  2.99.0-Master (01468d0)
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  , mFeedback( feedback )
99  {
100  readNextEntry();
101  }
102 
104  {
105  delete mNextData;
106  }
107 
109  IData *getNext() override
110  {
111  if ( mFeedback && mFeedback->isCanceled() )
112  return nullptr;
113 
114  RTree::Data *ret = mNextData;
115  mNextData = nullptr;
116  readNextEntry();
117  return ret;
118  }
119 
121  bool hasNext() override { return nullptr != mNextData; }
122 
124  uint32_t size() override { Q_ASSERT( false && "not available" ); return 0; }
125 
127  void rewind() override { Q_ASSERT( false && "not available" ); }
128 
129  protected:
131  {
132  QgsFeature f;
133  SpatialIndex::Region r;
134  QgsFeatureId id;
135  while ( mFi.nextFeature( f ) )
136  {
137  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
138  {
139  mNextData = new RTree::Data( 0, nullptr, r, id );
140  return;
141  }
142  }
143  }
144 
145  private:
146  QgsFeatureIterator mFi;
147  RTree::Data *mNextData = nullptr;
148  QgsFeedback *mFeedback = nullptr;
149 };
150 
151 
157 class QgsSpatialIndexData : public QSharedData
158 {
159  public:
161  {
162  initTree();
163  }
164 
173  explicit QgsSpatialIndexData( const QgsFeatureIterator &fi, QgsFeedback *feedback = nullptr )
174  {
175  QgsFeatureIteratorDataStream fids( fi, feedback );
176  initTree( &fids );
177  }
178 
180  : QSharedData( other )
181  {
182  initTree();
183 
184  // copy R-tree data one by one (is there a faster way??)
185  double low[] = { DBL_MIN, DBL_MIN };
186  double high[] = { DBL_MAX, DBL_MAX };
187  SpatialIndex::Region query( low, high, 2 );
188  QgsSpatialIndexCopyVisitor visitor( mRTree );
189  other.mRTree->intersectsWithQuery( query, visitor );
190  }
191 
193  {
194  delete mRTree;
195  delete mStorage;
196  }
197 
198  QgsSpatialIndexData &operator=( const QgsSpatialIndexData &rh ) = delete;
199 
200  void initTree( IDataStream *inputStream = nullptr )
201  {
202  // for now only memory manager
203  mStorage = StorageManager::createNewMemoryStorageManager();
204 
205  // R-Tree parameters
206  double fillFactor = 0.7;
207  unsigned long indexCapacity = 10;
208  unsigned long leafCapacity = 10;
209  unsigned long dimension = 2;
210  RTree::RTreeVariant variant = RTree::RV_RSTAR;
211 
212  // create R-tree
213  SpatialIndex::id_type indexId;
214 
215  if ( inputStream )
216  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
217  leafCapacity, dimension, variant, indexId );
218  else
219  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
220  leafCapacity, dimension, variant, indexId );
221  }
222 
224  SpatialIndex::IStorageManager *mStorage = nullptr;
225 
227  SpatialIndex::ISpatialIndex *mRTree = nullptr;
228 
229 };
230 
231 // -------------------------------------------------------------------------
232 
233 
235 {
236  d = new QgsSpatialIndexData;
237 }
238 
240 {
241  d = new QgsSpatialIndexData( fi, feedback );
242 }
243 
245 {
246  d = new QgsSpatialIndexData( source.getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) ), feedback );
247 }
248 
250  : d( other.d )
251 {
252 }
253 
255 {
256 }
257 
259 {
260  if ( this != &other )
261  d = other.d;
262  return *this;
263 }
264 
265 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle &rect )
266 {
267  double pt1[2] = { rect.xMinimum(), rect.yMinimum() },
268  pt2[2] = { rect.xMaximum(), rect.yMaximum() };
269  return SpatialIndex::Region( pt1, pt2, 2 );
270 }
271 
272 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id )
273 {
274  QgsRectangle rect;
275  if ( !featureInfo( f, rect, id ) )
276  return false;
277 
278  r = rectToRegion( rect );
279  return true;
280 }
281 
282 bool QgsSpatialIndex::featureInfo( const QgsFeature &f, QgsRectangle &rect, QgsFeatureId &id )
283 {
284  if ( !f.hasGeometry() )
285  return false;
286 
287  id = f.id();
288  rect = f.geometry().boundingBox();
289  return true;
290 }
291 
293 {
294  QgsRectangle rect;
295  QgsFeatureId id;
296  if ( !featureInfo( f, rect, id ) )
297  return false;
298 
299  return insertFeature( id, rect );
300 }
301 
303 {
304  SpatialIndex::Region r( rectToRegion( rect ) );
305 
306  // TODO: handle possible exceptions correctly
307  try
308  {
309  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
310  return true;
311  }
312  catch ( Tools::Exception &e )
313  {
314  Q_UNUSED( e );
315  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
316  }
317  catch ( const std::exception &e )
318  {
319  Q_UNUSED( e );
320  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
321  }
322  catch ( ... )
323  {
324  QgsDebugMsg( "unknown spatial index exception caught" );
325  }
326 
327  return false;
328 }
329 
331 {
332  SpatialIndex::Region r;
333  QgsFeatureId id;
334  if ( !featureInfo( f, r, id ) )
335  return false;
336 
337  // TODO: handle exceptions
338  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
339 }
340 
341 QList<QgsFeatureId> QgsSpatialIndex::intersects( const QgsRectangle &rect ) const
342 {
343  QList<QgsFeatureId> list;
344  QgisVisitor visitor( list );
345 
346  SpatialIndex::Region r = rectToRegion( rect );
347 
348  d->mRTree->intersectsWithQuery( r, visitor );
349 
350  return list;
351 }
352 
353 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
354 {
355  QList<QgsFeatureId> list;
356  QgisVisitor visitor( list );
357 
358  double pt[2] = { point.x(), point.y() };
359  Point p( pt, 2 );
360 
361  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
362 
363  return list;
364 }
365 
366 QAtomicInt QgsSpatialIndex::refs() const
367 {
368  return d->ref;
369 }
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:111
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:96
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:101
qint64 QgsFeatureId
Definition: qgsfeature.h:37
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:106
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!