QGIS API Documentation  2.3.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups 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 "qgsrectangle.h"
21 #include "qgslogger.h"
22 
23 #include "SpatialIndex.h"
24 
25 using namespace SpatialIndex;
26 
27 
28 
29 // custom visitor that adds found features to list
30 class QgisVisitor : public SpatialIndex::IVisitor
31 {
32  public:
33  QgisVisitor( QList<QgsFeatureId> & list )
34  : mList( list ) {}
35 
36  void visitNode( const INode& n )
37  { Q_UNUSED( n ); }
38 
39  void visitData( const IData& d )
40  {
41  mList.append( d.getIdentifier() );
42  }
43 
44  void visitData( std::vector<const IData*>& v )
45  { Q_UNUSED( v ); }
46 
47  private:
48  QList<QgsFeatureId>& mList;
49 };
50 
51 class QgsSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
52 {
53  public:
54  QgsSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex* newIndex )
55  : mNewIndex( newIndex ) {}
56 
57  void visitNode( const INode& n )
58  { Q_UNUSED( n ); }
59 
60  void visitData( const IData& d )
61  {
62  SpatialIndex::IShape* shape;
63  d.getShape( &shape );
64  mNewIndex->insertData( 0, 0, *shape, d.getIdentifier() );
65  delete shape;
66  }
67 
68  void visitData( std::vector<const IData*>& v )
69  { Q_UNUSED( v ); }
70 
71  private:
72  SpatialIndex::ISpatialIndex* mNewIndex;
73 };
74 
75 
77 class QgsSpatialIndexData : public QSharedData
78 {
79  public:
81  {
82  initTree();
83  }
84 
86  : QSharedData( other )
87  {
88  initTree();
89 
90  // copy R-tree data one by one (is there a faster way??)
91  double low[] = { DBL_MIN, DBL_MIN };
92  double high[] = { DBL_MAX, DBL_MAX };
93  SpatialIndex::Region query( low, high, 2 );
94  QgsSpatialIndexCopyVisitor visitor( mRTree );
95  other.mRTree->intersectsWithQuery( query, visitor );
96  }
97 
99  {
100  delete mRTree;
101  delete mStorage;
102  }
103 
104  void initTree()
105  {
106  // for now only memory manager
107  mStorage = StorageManager::createNewMemoryStorageManager();
108 
109  // R-Tree parameters
110  double fillFactor = 0.7;
111  unsigned long indexCapacity = 10;
112  unsigned long leafCapacity = 10;
113  unsigned long dimension = 2;
114  RTree::RTreeVariant variant = RTree::RV_RSTAR;
115 
116  // create R-tree
117  SpatialIndex::id_type indexId;
118  mRTree = RTree::createNewRTree( *mStorage, fillFactor, indexCapacity,
119  leafCapacity, dimension, variant, indexId );
120  }
121 
123  SpatialIndex::IStorageManager* mStorage;
124 
126  SpatialIndex::ISpatialIndex* mRTree;
127 };
128 
129 // -------------------------------------------------------------------------
130 
131 
133 {
134  d = new QgsSpatialIndexData;
135 }
136 
138  : d( other.d )
139 {
140 }
141 
143 {
144 }
145 
147 {
148  if ( this != &other )
149  d = other.d;
150  return *this;
151 }
152 
154 {
155  double pt1[2], pt2[2];
156  pt1[0] = rect.xMinimum();
157  pt1[1] = rect.yMinimum();
158  pt2[0] = rect.xMaximum();
159  pt2[1] = rect.yMaximum();
160  return Region( pt1, pt2, 2 );
161 }
162 
163 bool QgsSpatialIndex::featureInfo( const QgsFeature& f, SpatialIndex::Region& r, QgsFeatureId &id )
164 {
165  QgsGeometry *g = f.geometry();
166  if ( !g )
167  return false;
168 
169  id = f.id();
170  r = rectToRegion( g->boundingBox() );
171  return true;
172 }
173 
174 
176 {
177  Region r;
178  QgsFeatureId id;
179  if ( !featureInfo( f, r, id ) )
180  return false;
181 
182  // TODO: handle possible exceptions correctly
183  try
184  {
185  d->mRTree->insertData( 0, 0, r, FID_TO_NUMBER( id ) );
186  return true;
187  }
188  catch ( Tools::Exception &e )
189  {
190  Q_UNUSED( e );
191  QgsDebugMsg( QString( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
192  }
193  catch ( const std::exception &e )
194  {
195  Q_UNUSED( e );
196  QgsDebugMsg( QString( "std::exception caught: " ).arg( e.what() ) );
197  }
198  catch ( ... )
199  {
200  QgsDebugMsg( "unknown spatial index exception caught" );
201  }
202 
203  return false;
204 }
205 
207 {
208  Region r;
209  QgsFeatureId id;
210  if ( !featureInfo( f, r, id ) )
211  return false;
212 
213  // TODO: handle exceptions
214  return d->mRTree->deleteData( r, FID_TO_NUMBER( id ) );
215 }
216 
217 QList<QgsFeatureId> QgsSpatialIndex::intersects( QgsRectangle rect ) const
218 {
219  QList<QgsFeatureId> list;
220  QgisVisitor visitor( list );
221 
222  Region r = rectToRegion( rect );
223 
224  d->mRTree->intersectsWithQuery( r, visitor );
225 
226  return list;
227 }
228 
229 QList<QgsFeatureId> QgsSpatialIndex::nearestNeighbor( QgsPoint point, int neighbors ) const
230 {
231  QList<QgsFeatureId> list;
232  QgisVisitor visitor( list );
233 
234  double pt[2];
235  pt[0] = point.x();
236  pt[1] = point.y();
237  Point p( pt, 2 );
238 
239  d->mRTree->nearestNeighborQuery( neighbors, p, visitor );
240 
241  return list;
242 }
243 
245 {
246  return d->ref;
247 }
QgsFeatureId id() const
Get the feature id for this feature.
Definition: qgsfeature.cpp:100
A rectangle specified with double values.
Definition: qgsrectangle.h:35
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.
bool deleteFeature(const QgsFeature &f)
remove feature from index
double yMaximum() const
Get the y maximum value (top side of rectangle)
Definition: qgsrectangle.h:189
#define QgsDebugMsg(str)
Definition: qgslogger.h:36
SpatialIndex::ISpatialIndex * mNewIndex
QgsGeometry * geometry() const
Get the geometry object associated with this feature.
Definition: qgsfeature.cpp:112
QSharedDataPointer< QgsSpatialIndexData > d
void visitNode(const INode &n)
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:114
QgsSpatialIndexCopyVisitor(SpatialIndex::ISpatialIndex *newIndex)
QList< QgsFeatureId > intersects(QgsRectangle rect) const
returns features that intersect the specified rectangle
double x() const
Definition: qgspoint.h:110
QgsSpatialIndexData(const QgsSpatialIndexData &other)
QList< QgsFeatureId > & mList
QgisVisitor(QList< QgsFeatureId > &list)
double yMinimum() const
Get the y minimum value (bottom side of rectangle)
Definition: qgsrectangle.h:194
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:179
#define FID_TO_NUMBER(fid)
Definition: qgsfeature.h:82
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)
QgsSpatialIndex()
constructor - creates R-tree
void visitData(std::vector< const IData * > &v)
A class to represent a point geometry.
Definition: qgspoint.h:63
void visitData(const IData &d)
void visitData(const IData &d)
QgsRectangle boundingBox()
Returns the bounding box of this feature.
bool insertFeature(const QgsFeature &f)
add feature to index
~QgsSpatialIndex()
destructor finalizes work with spatial index
int refs() const
get reference count - just for debugging!
void visitData(std::vector< const IData * > &v)
qint64 QgsFeatureId
Definition: qgsfeature.h:30
double y() const
Definition: qgspoint.h:118
void visitNode(const INode &n)
bool featureInfo(const QgsFeature &f, SpatialIndex::Region &r, QgsFeatureId &id)
double xMinimum() const
Get the x minimum value (left side of rectangle)
Definition: qgsrectangle.h:184