QGIS API Documentation  2.11.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
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 
30 // custom visitor that adds found features to list
31 class QgisVisitor : public SpatialIndex::IVisitor
32 {
33  public:
35  : mList( list ) {}
36 
37  void visitNode( const INode& n ) override
38  { Q_UNUSED( n ); }
39 
40  void visitData( const IData& d ) override
41  {
42  mList.append( d.getIdentifier() );
43  }
44 
45  void visitData( std::vector<const IData*>& v ) override
46  { Q_UNUSED( v ); }
47 
48  private:
49  QList<QgsFeatureId>& mList;
50 };
51 
52 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
53 {
54  public:
55  QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex* newIndex )
56  : mNewIndex( newIndex ) {}
57 
58  void visitNode( const INode& n ) override
59  { Q_UNUSED( n ); }
60 
61  void visitData( const IData& d ) override
62  {
63  SpatialIndex::IShape* shape;
64  d.getShape( &shape );
65  mNewIndex->insertData( 0, 0, *shape, d.getIdentifier() );
66  delete shape;
67  }
68 
69  void visitData( std::vector<const IData*>& v ) override
70  { Q_UNUSED( v ); }
71 
72  private:
73  SpatialIndex::ISpatialIndex* mNewIndex;
74 };
75 
76 
78 class QgsFeatureIteratorDataStream : public IDataStream
79 {
80  public:
82  QgsFeatureIteratorDataStream( const QgsFeatureIterator& fi ) : mFi( fi ), mNextData( 0 )
83  {
84  readNextEntry();
85  }
86 
88  {
89  delete mNextData;
90  }
91 
93  virtual IData* getNext() override
94  {
95  RTree::Data* ret = mNextData;
96  mNextData = 0;
97  readNextEntry();
98  return ret;
99  }
100 
102  virtual bool hasNext() override { return mNextData != 0; }
103 
105  virtual uint32_t size() override { Q_ASSERT( 0 && "not available" ); return 0; }
106 
108  virtual void rewind() override { Q_ASSERT( 0 && "not available" ); }
109 
110  protected:
112  {
113  QgsFeature f;
114  SpatialIndex::Region r;
115  QgsFeatureId id;
116  while ( mFi.nextFeature( f ) )
117  {
118  if ( QgsSpatialIndex::featureInfo( f, r, id ) )
119  {
120  mNextData = new RTree::Data( 0, 0, r, id );
121  return;
122  }
123  }
124  }
125 
126  private:
127  QgsFeatureIterator mFi;
128  RTree::Data* mNextData;
129 };
130 
131 
134 {
135  public:
137  {
138  initTree();
139  }
140 
142  {
143  QgsFeatureIteratorDataStream fids( fi );
144  initTree( &fids );
145  }
146 
148  : QSharedData( other )
149  {
150  initTree();
151 
152  // copy R-tree data one by one (is there a faster way??)
153  double low[] = { DBL_MIN, DBL_MIN };
154  double high[] = { DBL_MAX, DBL_MAX };
155  SpatialIndex::Region query( low, high, 2 );
156  QgsSpatialIndexCopyVisitor visitor( mRTree );
157  other.mRTree->intersectsWithQuery( query, visitor );
158  }
159 
161  {
162  delete mRTree;
163  delete mStorage;
164  }
165 
166  void initTree( IDataStream* inputStream = 0 )
167  {
168  // for now only memory manager
169  mStorage = StorageManager::createNewMemoryStorageManager();
170 
171  // R-Tree parameters
172  double fillFactor = 0.7;
173  unsigned long indexCapacity = 10;
174  unsigned long leafCapacity = 10;
175  unsigned long dimension = 2;
176  RTree::RTreeVariant variant = RTree::RV_RSTAR;
177 
178  // create R-tree
179  SpatialIndex::id_type indexId;
180 
181  if ( inputStream )
182  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity,
183  leafCapacity, dimension, variant, indexId );
184  else
185  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
186  leafCapacity, dimension, variant, indexId );
187  }
188 
190  SpatialIndex::IStorageManager* mStorage;
191 
193  SpatialIndex::ISpatialIndex* mRTree;
194 };
195 
196 // -------------------------------------------------------------------------
197 
198 
200 {
201  d = new QgsSpatialIndexData;
202 }
203 
205 {
206  d = new QgsSpatialIndexData( fi );
207 }
208 
210  : d( other.d )
211 {
212 }
213 
215 {
216 }
217 
219 {
220  if ( this != &other )
221  d = other.d;
222  return *this;
223 }
224 
226 {
227  double pt1[2], pt2[2];
228  pt1[0] = rect.xMinimum();
229  pt1[1] = rect.yMinimum();
230  pt2[0] = rect.xMaximum();
231  pt2[1] = rect.yMaximum();
232  return Region( pt1, pt2, 2 );
233 }
234 
235 bool QgsSpatialIndex::featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
236 {
237  if ( !f.constGeometry() )
238  return false;
239 
240  QgsGeometry g( *f.constGeometry() );
241 
242  id = f.id();
243  r = rectToRegion( g.boundingBox() );
244  return true;
245 }
246 
247 
249 {
250  Region r;
251  QgsFeatureId id;
252  if ( !featureInfo( f, r, id ) )
253  return false;
254 
255  // TODO: handle possible exceptions correctly
256  try
257  {
258  d->mRTree->insertData( 0, 0, r, FID_TO_NUMBER( id ) );
259  return true;
260  }
261  catch ( Tools::Exception &e )
262  {
263  Q_UNUSED( e );
264  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
265  }
266  catch ( const std::exception &e )
267  {
268  Q_UNUSED( e );
269  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
270  }
271  catch ( ... )
272  {
273  QgsDebugMsg( "unknown spatial index exception caught" );
274  }
275 
276  return false;
277 }
278 
280 {
281  Region r;
282  QgsFeatureId id;
283  if ( !featureInfo( f, r, id ) )
284  return false;
285 
286  // TODO: handle exceptions
287  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
288 }
289 
291 {
292  QList<QgsFeatureId> list;
293  QgisVisitor visitor( list );
294 
295  Region r = rectToRegion( rect );
296 
297  d->mRTree->intersectsWithQuery( r, visitor );
298 
299  return list;
300 }
301 
303 {
304  QList<QgsFeatureId> list;
305  QgisVisitor visitor( list );
306 
307  double pt[2];
308  pt[0] = point.x();
309  pt[1] = point.y();
310  Point p( pt, 2 );
311 
312  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
313 
314  return list;
315 }
316 
318 {
319  return d->ref;
320 }
QgsFeatureId id() const
Get the feature ID for this feature.
Definition: qgsfeature.cpp:51
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
static SpatialIndex::Region rectToRegion(QgsRectangle rect)
SpatialIndex::ISpatialIndex * mRTree
R-tree containing spatial index.
void initTree(IDataStream *inputStream=0)
bool deleteFeature(const QgsFeature &f)
remove feature from index
double yMaximum() const
Get the y maximum value (top side of rectangle)
Definition: qgsrectangle.h:192
#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:75
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:119
QgsSpatialIndexCopyVisitor(SpatialIndex::ISpatialIndex *newIndex)
virtual void rewind() override
sets the stream pointer to the first entry, if possible.
QList< QgsFeatureId > intersects(QgsRectangle rect) const
returns features that intersect the specified rectangle
void visitData(std::vector< const IData * > &v) override
double x() const
Definition: qgspoint.h:126
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:197
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:182
#define FID_TO_NUMBER(fid)
Definition: qgsfeature.h:88
Data of spatial index that may be implicitly shared.
QList< QgsFeatureId > nearestNeighbor(QgsPoint point, int neighbors) const
returns nearest neighbors (their count is specified by second parameter)
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:63
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
const QgsGeometry * constGeometry() const
Gets a const pointer to the geometry object associated with this feature.
Definition: qgsfeature.cpp:68
qint64 QgsFeatureId
Definition: qgsfeature.h:31
double y() const
Definition: qgspoint.h:134
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:187