QGIS API Documentation  3.2.0-Bonn (bc43194)
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 #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().setSubsetOfAttributes( QgsAttributeList() ) ), 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  return true;
300 }
301 
303 {
304  QgsRectangle rect;
305  QgsFeatureId id;
306  if ( !featureInfo( f, rect, id ) )
307  return false;
308 
309  return insertFeature( id, rect );
310 }
311 
313 {
314  SpatialIndex::Region r( rectToRegion( rect ) );
315 
316  QMutexLocker locker( &d->mMutex );
317 
318  // TODO: handle possible exceptions correctly
319  try
320  {
321  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
322  return true;
323  }
324  catch ( Tools::Exception &e )
325  {
326  Q_UNUSED( e );
327  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
328  }
329  catch ( const std::exception &e )
330  {
331  Q_UNUSED( e );
332  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
333  }
334  catch ( ... )
335  {
336  QgsDebugMsg( "unknown spatial index exception caught" );
337  }
338 
339  return false;
340 }
341 
343 {
344  SpatialIndex::Region r;
345  QgsFeatureId id;
346  if ( !featureInfo( f, r, id ) )
347  return false;
348 
349  QMutexLocker locker( &d->mMutex );
350  // TODO: handle exceptions
351  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
352 }
353 
354 QList<QgsFeatureId> QgsSpatialIndex::intersects( const QgsRectangle &rect ) const
355 {
356  QList<QgsFeatureId> list;
357  QgisVisitor visitor( list );
358 
359  SpatialIndex::Region r = rectToRegion( rect );
360 
361  QMutexLocker locker( &d->mMutex );
362  d->mRTree->intersectsWithQuery( r, visitor );
363 
364  return list;
365 }
366 
367 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
368 {
369  QList<QgsFeatureId> list;
370  QgisVisitor visitor( list );
371 
372  double pt[2] = { point.x(), point.y() };
373  Point p( pt, 2 );
374 
375  QMutexLocker locker( &d->mMutex );
376  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
377 
378  return list;
379 }
380 
381 QAtomicInt QgsSpatialIndex::refs() const
382 {
383  return d->ref;
384 }
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:40
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 to a point.
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
double y
Definition: qgspointxy.h:48
A class to represent a 2D point.
Definition: qgspointxy.h:43
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
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: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 for QgsSpatialIndex.
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:176
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:161
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.
~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:166
qint64 QgsFeatureId
Definition: qgsfeature.h:37
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:171
QList< int > QgsAttributeList
Definition: qgsfield.h:27
QList< QgsFeatureId > intersects(const QgsRectangle &rectangle) const
Returns a list of features with a bounding box which intersects the specified rectangle.
virtual QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest()) const =0
Returns an iterator for the features in the source.
QAtomicInt refs() const
Gets reference count - just for debugging!