QGIS API Documentation  2.17.0-Master (bf77d09)
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 
90 class QgsFeatureIteratorDataStream : public IDataStream
91 {
92  public:
95  : mFi( fi )
96  , mNextData( nullptr )
97  {
98  readNextEntry();
99  }
100 
102  {
103  delete mNextData;
104  }
105 
107  virtual IData* getNext() override
108  {
109  RTree::Data* ret = mNextData;
110  mNextData = nullptr;
111  readNextEntry();
112  return ret;
113  }
114 
116  virtual bool hasNext() override { return nullptr != mNextData; }
117 
119  virtual uint32_t size() override { Q_ASSERT( 0 && "not available" ); return 0; }
120 
122  virtual void rewind() override { Q_ASSERT( 0 && "not available" ); }
123 
124  protected:
126  {
127  QgsFeature f;
128  SpatialIndex::Region r;
129  QgsFeatureId id;
130  while ( mFi.nextFeature( f ) )
131  {
132  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
133  {
134  mNextData = new RTree::Data( 0, nullptr, r, id );
135  return;
136  }
137  }
138  }
139 
140  private:
141  QgsFeatureIterator mFi;
142  RTree::Data* mNextData;
143 };
144 
145 
152 {
153  public:
155  {
156  initTree();
157  }
158 
160  {
161  QgsFeatureIteratorDataStream fids( fi );
162  initTree( &fids );
163  }
164 
166  : QSharedData( other )
167  {
168  initTree();
169 
170  // copy R-tree data one by one (is there a faster way??)
171  double low[] = { DBL_MIN, DBL_MIN };
172  double high[] = { DBL_MAX, DBL_MAX };
173  SpatialIndex::Region query( low, high, 2 );
174  QgsSpatialIndexCopyVisitor visitor( mRTree );
175  other.mRTree->intersectsWithQuery( query, visitor );
176  }
177 
179  {
180  delete mRTree;
181  delete mStorage;
182  }
183 
184  void initTree( IDataStream* inputStream = nullptr )
185  {
186  // for now only memory manager
187  mStorage = StorageManager::createNewMemoryStorageManager();
188 
189  // R-Tree parameters
190  double fillFactor = 0.7;
191  unsigned long indexCapacity = 10;
192  unsigned long leafCapacity = 10;
193  unsigned long dimension = 2;
194  RTree::RTreeVariant variant = RTree::RV_RSTAR;
195 
196  // create R-tree
197  SpatialIndex::id_type indexId;
198 
199  if ( inputStream )
200  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
201  leafCapacity, dimension, variant, indexId );
202  else
203  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
204  leafCapacity, dimension, variant, indexId );
205  }
206 
208  SpatialIndex::IStorageManager* mStorage;
209 
211  SpatialIndex::ISpatialIndex* mRTree;
212 
213  private:
214 
215  QgsSpatialIndexData& operator=( const QgsSpatialIndexData& rh );
216 };
217 
218 // -------------------------------------------------------------------------
219 
220 
222 {
223  d = new QgsSpatialIndexData;
224 }
225 
227 {
228  d = new QgsSpatialIndexData( fi );
229 }
230 
232  : d( other.d )
233 {
234 }
235 
237 {
238 }
239 
241 {
242  if ( this != &other )
243  d = other.d;
244  return *this;
245 }
246 
247 SpatialIndex::Region QgsSpatialIndex::rectToRegion( const QgsRectangle& rect )
248 {
249  double pt1[2] = { rect.xMinimum(), rect.yMinimum() },
250  pt2[2] = { rect.xMaximum(), rect.yMaximum() };
251  return SpatialIndex::Region( pt1, pt2, 2 );
252 }
253 
254 bool QgsSpatialIndex::featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
255 {
256  if ( !f.constGeometry() )
257  return false;
258 
259  QgsGeometry g( *f.constGeometry() );
260 
261  id = f.id();
262  r = rectToRegion( g.boundingBox() );
263  return true;
264 }
265 
266 
268 {
269  SpatialIndex::Region r;
270  QgsFeatureId id;
271  if ( !featureInfo( f, r, id ) )
272  return false;
273 
274  // TODO: handle possible exceptions correctly
275  try
276  {
277  d->mRTree->insertData( 0, nullptr, r, FID_TO_NUMBER( id ) );
278  return true;
279  }
280  catch ( Tools::Exception &e )
281  {
282  Q_UNUSED( e );
283  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
284  }
285  catch ( const std::exception &e )
286  {
287  Q_UNUSED( e );
288  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
289  }
290  catch ( ... )
291  {
292  QgsDebugMsg( "unknown spatial index exception caught" );
293  }
294 
295  return false;
296 }
297 
299 {
300  SpatialIndex::Region r;
301  QgsFeatureId id;
302  if ( !featureInfo( f, r, id ) )
303  return false;
304 
305  // TODO: handle exceptions
306  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
307 }
308 
310 {
311  QList<QgsFeatureId> list;
312  QgisVisitor visitor( list );
313 
314  SpatialIndex::Region r = rectToRegion( rect );
315 
316  d->mRTree->intersectsWithQuery( r, visitor );
317 
318  return list;
319 }
320 
322 {
323  QList<QgsFeatureId> list;
324  QgisVisitor visitor( list );
325 
326  double pt[2] = { point.x(), point.y() };
327  Point p( pt, 2 );
328 
329  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
330 
331  return list;
332 }
333 
335 {
336  return d->ref;
337 }
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:185
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:193
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