QGIS API Documentation
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 
24 #include "SpatialIndex.h"
25 
26 using namespace SpatialIndex;
27 
28 
29 
35 class QgisVisitor : public SpatialIndex::IVisitor
36 {
37  public:
38  explicit QgisVisitor( QList<QgsFeatureId> & list )
39  : mList( list ) {}
40 
41  void visitNode( const INode& n ) override
42  { Q_UNUSED( n ); }
43 
44  void visitData( const IData& d ) override
45  {
46  mList.append( d.getIdentifier() );
47  }
48 
49  void visitData( std::vector<const IData*>& v ) override
50  { Q_UNUSED( v ); }
51 
52  private:
53  QList<QgsFeatureId>& mList;
54 };
55 
60 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
61 {
62  public:
63  explicit QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex* newIndex )
64  : mNewIndex( newIndex ) {}
65 
66  void visitNode( const INode& n ) override
67  { Q_UNUSED( n ); }
68 
69  void visitData( const IData& d ) override
70  {
71  SpatialIndex::IShape* shape;
72  d.getShape( &shape );
73  mNewIndex->insertData( 0, nullptr, *shape, d.getIdentifier() );
74  delete shape;
75  }
76 
77  void visitData( std::vector<const IData*>& v ) override
78  { Q_UNUSED( v ); }
79 
80  private:
81  SpatialIndex::ISpatialIndex* mNewIndex;
82 };
83 
84 
89 class QgsFeatureIteratorDataStream : public IDataStream
90 {
91  public:
94  : mFi( fi )
95  , mNextData( nullptr )
96  {
97  readNextEntry();
98  }
99 
101  {
102  delete mNextData;
103  }
104 
106  virtual IData* getNext() override
107  {
108  RTree::Data* ret = mNextData;
109  mNextData = nullptr;
110  readNextEntry();
111  return ret;
112  }
113 
115  virtual bool hasNext() override { return nullptr != mNextData; }
116 
118  virtual uint32_t size() override { Q_ASSERT( 0 && "not available" ); return 0; }
119 
121  virtual void rewind() override { Q_ASSERT( 0 && "not available" ); }
122 
123  protected:
125  {
126  QgsFeature f;
127  SpatialIndex::Region r;
128  QgsFeatureId id;
129  while ( mFi.nextFeature( f ) )
130  {
131  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
132  {
133  mNextData = new RTree::Data( 0, nullptr, r, id );
134  return;
135  }
136  }
137  }
138 
139  private:
140  QgsFeatureIterator mFi;
141  RTree::Data* mNextData;
142 };
143 
144 
150 {
151  public:
153  {
154  initTree();
155  }
156 
158  {
159  QgsFeatureIteratorDataStream fids( fi );
160  initTree( &fids );
161  }
162 
164  : QSharedData( other )
165  {
166  initTree();
167 
168  // copy R-tree data one by one (is there a faster way??)
169  double low[] = { DBL_MIN, DBL_MIN };
170  double high[] = { DBL_MAX, DBL_MAX };
171  SpatialIndex::Region query( low, high, 2 );
172  QgsSpatialIndexCopyVisitor visitor( mRTree );
173  other.mRTree->intersectsWithQuery( query, visitor );
174  }
175 
177  {
178  delete mRTree;
179  delete mStorage;
180  }
181 
182  void initTree( IDataStream* inputStream = nullptr )
183  {
184  // for now only memory manager
185  mStorage = StorageManager::createNewMemoryStorageManager();
186 
187  // R-Tree parameters
188  double fillFactor = 0.7;
189  unsigned long indexCapacity = 10;
190  unsigned long leafCapacity = 10;
191  unsigned long dimension = 2;
192  RTree::RTreeVariant variant = RTree::RV_RSTAR;
193 
194  // create R-tree
195  SpatialIndex::id_type indexId;
196 
197  if ( inputStream )
198  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
199  leafCapacity, dimension, variant, indexId );
200  else
201  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
202  leafCapacity, dimension, variant, indexId );
203  }
204 
206  SpatialIndex::IStorageManager* mStorage;
207 
209  SpatialIndex::ISpatialIndex* mRTree;
210 
211  private:
212 
213  QgsSpatialIndexData& operator=( const QgsSpatialIndexData& rh );
214 };
215 
216 // -------------------------------------------------------------------------
217 
218 
220 {
221  d = new QgsSpatialIndexData;
222 }
223 
225 {
226  d = new QgsSpatialIndexData( fi );
227 }
228 
230  : d( other.d )
231 {
232 }
233 
235 {
236 }
237 
239 {
240  if ( this != &other )
241  d = other.d;
242  return *this;
243 }
244 
245 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle& rect )
246 {
247  double pt1[2], pt2[2];
248  pt1[0] = rect.xMinimum();
249  pt1[1] = rect.yMinimum();
250  pt2[0] = rect.xMaximum();
251  pt2[1] = rect.yMaximum();
252  return SpatialIndex::Region( pt1, pt2, 2 );
253 }
254 
255 bool QgsSpatialIndex::featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
256 {
257  if ( !f.constGeometry() )
258  return false;
259 
260  QgsGeometry g( *f.constGeometry() );
261 
262  id = f.id();
263  r = rectToRegion( g.boundingBox() );
264  return true;
265 }
266 
267 
269 {
270  SpatialIndex::Region r;
271  QgsFeatureId id;
272  if ( !featureInfo( f, r, id ) )
273  return false;
274 
275  // TODO: handle possible exceptions correctly
276  try
277  {
278  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
279  return true;
280  }
281  catch ( Tools::Exception &e )
282  {
283  Q_UNUSED( e );
284  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
285  }
286  catch ( const std::exception &e )
287  {
288  Q_UNUSED( e );
289  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
290  }
291  catch ( ... )
292  {
293  QgsDebugMsg( "unknown spatial index exception caught" );
294  }
295 
296  return false;
297 }
298 
300 {
301  SpatialIndex::Region r;
302  QgsFeatureId id;
303  if ( !featureInfo( f, r, id ) )
304  return false;
305 
306  // TODO: handle exceptions
307  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
308 }
309 
311 {
312  QList<QgsFeatureId> list;
313  QgisVisitor visitor( list );
314 
315  SpatialIndex::Region r = rectToRegion( rect );
316 
317  d->mRTree->intersectsWithQuery( r, visitor );
318 
319  return list;
320 }
321 
323 {
324  QList<QgsFeatureId> list;
325  QgisVisitor visitor( list );
326 
327  double pt[2];
328  pt[0] = point.x();
329  pt[1] = point.y();
330  Point p( pt, 2 );
331 
332  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
333 
334  return list;
335 }
336 
338 {
339  return d->ref;
340 }
QgsFeatureId id() const
Get the feature ID for this feature.
Definition: qgsfeature.cpp:65
Wrapper for iterator of features from vector data provider or vector layer.
virtual uint32_t size() override
returns the total number of entries available in the stream.
A rectangle specified with double values.
Definition: qgsrectangle.h:35
virtual bool hasNext() override
returns true if there are more items in the stream.
SpatialIndex::IStorageManager * mStorage
Storage manager.
QgsSpatialIndex & operator=(const QgsSpatialIndex &other)
Implement assignment operator.
SpatialIndex::ISpatialIndex * mRTree
R-tree containing spatial index.
QList< QgsFeatureId > intersects(const QgsRectangle &rect) const
Returns features that intersect the specified rectangle.
bool deleteFeature(const QgsFeature &f)
Remove feature from index.
double yMaximum() const
Get the y maximum value (top side of rectangle)
Definition: qgsrectangle.h:197
#define QgsDebugMsg(str)
Definition: qgslogger.h:33
QgsSpatialIndexData(const QgsFeatureIterator &fi)
void visitData(std::vector< const IData * > &v) override
void visitNode(const INode &n) override
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:76
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:187
QgsSpatialIndexCopyVisitor(SpatialIndex::ISpatialIndex *newIndex)
virtual void rewind() override
sets the stream pointer to the first entry, if possible.
static SpatialIndex::Region rectToRegion(const QgsRectangle &rect)
void visitData(std::vector< const IData * > &v) override
double x() const
Get the x value of the point.
Definition: qgspoint.h:180
QgsSpatialIndexData(const QgsSpatialIndexData &other)
void visitNode(const INode &n) override
QgisVisitor(QList< QgsFeatureId > &list)
QgsFeatureIteratorDataStream(const QgsFeatureIterator &fi)
constructor - needs to load all data to a vector for later access when bulk loading ...
double yMinimum() const
Get the y minimum value (bottom side of rectangle)
Definition: qgsrectangle.h:202
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:187
#define FID_TO_NUMBER(fid)
Definition: qgsfeature.h:88
Data of spatial index that may be implicitly shared.
void visitData(const IData &d) override
QgsSpatialIndex()
Constructor - creates R-tree.
Utility class for bulk loading of R-trees.
A class to represent a point.
Definition: qgspoint.h:117
QList< QgsFeatureId > nearestNeighbor(const QgsPoint &point, int neighbors) const
Returns nearest neighbors (their count is specified by second parameter)
QAtomicInt refs() const
get reference count - just for debugging!
void visitData(const IData &d) override
bool insertFeature(const QgsFeature &f)
Add feature to index.
~QgsSpatialIndex()
Destructor finalizes work with spatial index.
Custom visitor that adds found features to list.
const QgsGeometry * constGeometry() const
Gets a const pointer to the geometry object associated with this feature.
Definition: qgsfeature.cpp:82
qint64 QgsFeatureId
Definition: qgsfeature.h:31
double y() const
Get the y value of the point.
Definition: qgspoint.h:188
static bool featureInfo(const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id)
virtual IData * getNext() override
returns a pointer to the next entry in the stream or 0 at the end of the stream.
double xMinimum() const
Get the x minimum value (left side of rectangle)
Definition: qgsrectangle.h:192