QGIS API Documentation  2.8.2-Wien
qgspointlocator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgspointlocator.cpp
3  --------------------------------------
4  Date : November 2014
5  Copyright : (C) 2014 by Martin Dobias
6  Email : wonder dot sk at gmail dot com
7  ***************************************************************************
8  * *
9  * This program is free software; you can redistribute it and/or modify *
11  * the Free Software Foundation; either version 2 of the License, or *
12  * (at your option) any later version. *
13  * *
14  ***************************************************************************/
15
16 #include "qgspointlocator.h"
17
18 #include "qgsgeometry.h"
19 #include "qgsvectorlayer.h"
20
21 #include <spatialindex/SpatialIndex.h>
22
24
25 using namespace SpatialIndex;
26
27
28
29 static SpatialIndex::Point point2point( const QgsPoint& point )
30 {
31  double plow[2];
32  plow[0] = point.x();
33  plow[1] = point.y();
34  return Point( plow, 2 );
35 }
36
37
38 static SpatialIndex::Region rect2region( const QgsRectangle& rect )
39 {
40  double pLow[2], pHigh[2];
41  pLow[0] = rect.xMinimum();
42  pLow[1] = rect.yMinimum();
43  pHigh[0] = rect.xMaximum();
44  pHigh[1] = rect.yMaximum();
45  return SpatialIndex::Region( pLow, pHigh, 2 );
46 }
47
48
49 // Ahh.... another magic number. Taken from QgsVectorLayer::snapToGeometry() call to closestSegmentWithContext().
50 // The default epsilon used for sqrDistToSegment (1e-8) is too high when working with lat/lon coordinates
51 // I still do not fully understand why the sqrDistToSegment() code uses epsilon and if the square distance
52 // is lower than epsilon it will have a special logic...
53 static const double POINT_LOC_EPSILON = 1e-12;
54
56
57
59 class QgsPointLocator_Stream : public IDataStream
60 {
61  public:
62  QgsPointLocator_Stream( const QLinkedList<RTree::Data*>& dataList ) : mDataList( dataList ), mIt( mDataList ) { }
64
65  virtual IData* getNext() override { return mIt.next(); }
66  virtual bool hasNext() override { return mIt.hasNext(); }
67
68  virtual uint32_t size() override { Q_ASSERT( 0 && "not available" ); return 0; }
69  virtual void rewind() override { Q_ASSERT( 0 && "not available" ); }
70
71  private:
74 };
75
76
78
79
81 class QgsPointLocator_VisitorNearestVertex : public IVisitor
82 {
83  public:
85  : mLocator( pl ), mBest( m ), mSrcPoint( srcPoint ), mFilter( filter ) {}
86
87  void visitNode( const INode& n ) override { Q_UNUSED( n ); }
88  void visitData( std::vector<const IData*>& v ) override { Q_UNUSED( v ); }
89
90  void visitData( const IData& d ) override
91  {
92  QgsFeatureId id = d.getIdentifier();
93  QgsGeometry* geom = mLocator->mGeoms.value( id );
94  int vertexIndex, beforeVertex, afterVertex;
95  double sqrDist;
96  QgsPoint pt = geom->closestVertex( mSrcPoint, vertexIndex, beforeVertex, afterVertex, sqrDist );
97
98  QgsPointLocator::Match m( QgsPointLocator::Vertex, mLocator->mLayer, id, sqrt( sqrDist ), pt, vertexIndex );
99  // in range queries the filter may reject some matches
100  if ( mFilter && !mFilter->acceptMatch( m ) )
101  return;
102
103  if ( !mBest.isValid() || m.distance() < mBest.distance() )
104  mBest = m;
105  }
106
107  private:
108  QgsPointLocator* mLocator;
109  QgsPointLocator::Match& mBest;
110  QgsPoint mSrcPoint;
112 };
113
114
116
117
119 class QgsPointLocator_VisitorNearestEdge : public IVisitor
120 {
121  public:
123  : mLocator( pl ), mBest( m ), mSrcPoint( srcPoint ), mFilter( filter ) {}
124
125  void visitNode( const INode& n ) override { Q_UNUSED( n ); }
126  void visitData( std::vector<const IData*>& v ) override { Q_UNUSED( v ); }
127
128  void visitData( const IData& d ) override
129  {
130  QgsFeatureId id = d.getIdentifier();
131  QgsGeometry* geom = mLocator->mGeoms.value( id );
132  QgsPoint pt;
133  int afterVertex;
134  double sqrDist = geom->closestSegmentWithContext( mSrcPoint, pt, afterVertex, 0, POINT_LOC_EPSILON );
135  if ( sqrDist < 0 )
136  return;
137
138  QgsPoint edgePoints[2];
139  edgePoints[0] = geom->vertexAt( afterVertex - 1 );
140  edgePoints[1] = geom->vertexAt( afterVertex );
141  QgsPointLocator::Match m( QgsPointLocator::Edge, mLocator->mLayer, id, sqrt( sqrDist ), pt, afterVertex - 1, edgePoints );
142  // in range queries the filter may reject some matches
143  if ( mFilter && !mFilter->acceptMatch( m ) )
144  return;
145
146  if ( !mBest.isValid() || m.distance() < mBest.distance() )
147  mBest = m;
148  }
149
150  private:
151  QgsPointLocator* mLocator;
152  QgsPointLocator::Match& mBest;
153  QgsPoint mSrcPoint;
155 };
156
157
159
160
162 class QgsPointLocator_VisitorArea : public IVisitor
163 {
164  public:
167  : mLocator( pl ), mList( list ), mGeomPt( QgsGeometry::fromPoint( origPt ) ) {}
168
169  ~QgsPointLocator_VisitorArea() { delete mGeomPt; }
170
171  void visitNode( const INode& n ) override { Q_UNUSED( n ); }
172  void visitData( std::vector<const IData*>& v ) override { Q_UNUSED( v ); }
173
174  void visitData( const IData& d ) override
175  {
176  QgsFeatureId id = d.getIdentifier();
177  QgsGeometry* g = mLocator->mGeoms.value( id );
178  if ( g->intersects( mGeomPt ) )
179  mList << QgsPointLocator::Match( QgsPointLocator::Area, mLocator->mLayer, id, 0, QgsPoint() );
180  }
181  private:
182  QgsPointLocator* mLocator;
184  QgsGeometry* mGeomPt;
185 };
186
187
189
191 // http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
193 {
194  _CohenSutherland( const QgsRectangle& rect ) : mRect( rect ) {}
195
196  typedef int OutCode;
197
198  static const int INSIDE = 0; // 0000
199  static const int LEFT = 1; // 0001
200  static const int RIGHT = 2; // 0010
201  static const int BOTTOM = 4; // 0100
202  static const int TOP = 8; // 1000
203
205
206  OutCode computeOutCode( double x, double y )
207  {
208  OutCode code = INSIDE; // initialised as being inside of clip window
209  if ( x < mRect.xMinimum() ) // to the left of clip window
210  code |= LEFT;
211  else if ( x > mRect.xMaximum() ) // to the right of clip window
212  code |= RIGHT;
213  if ( y < mRect.yMinimum() ) // below the clip window
214  code |= BOTTOM;
215  else if ( y > mRect.yMaximum() ) // above the clip window
216  code |= TOP;
217  return code;
218  }
219
220  bool isSegmentInRect( double x0, double y0, double x1, double y1 )
221  {
222  // compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
223  OutCode outcode0 = computeOutCode( x0, y0 );
224  OutCode outcode1 = computeOutCode( x1, y1 );
225  bool accept = false;
226
227  while ( true )
228  {
229  if ( !( outcode0 | outcode1 ) )
230  {
231  // Bitwise OR is 0. Trivially accept and get out of loop
232  accept = true;
233  break;
234  }
235  else if ( outcode0 & outcode1 )
236  {
237  // Bitwise AND is not 0. Trivially reject and get out of loop
238  break;
239  }
240  else
241  {
242  // failed both tests, so calculate the line segment to clip
243  // from an outside point to an intersection with clip edge
244  double x, y;
245
246  // At least one endpoint is outside the clip rectangle; pick it.
247  OutCode outcodeOut = outcode0 ? outcode0 : outcode1;
248
249  // Now find the intersection point;
250  // use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
251  if ( outcodeOut & TOP )
252  { // point is above the clip rectangle
253  x = x0 + ( x1 - x0 ) * ( mRect.yMaximum() - y0 ) / ( y1 - y0 );
254  y = mRect.yMaximum();
255  }
256  else if ( outcodeOut & BOTTOM )
257  { // point is below the clip rectangle
258  x = x0 + ( x1 - x0 ) * ( mRect.yMinimum() - y0 ) / ( y1 - y0 );
259  y = mRect.yMinimum();
260  }
261  else if ( outcodeOut & RIGHT )
262  { // point is to the right of clip rectangle
263  y = y0 + ( y1 - y0 ) * ( mRect.xMaximum() - x0 ) / ( x1 - x0 );
264  x = mRect.xMaximum();
265  }
266  else if ( outcodeOut & LEFT )
267  { // point is to the left of clip rectangle
268  y = y0 + ( y1 - y0 ) * ( mRect.xMinimum() - x0 ) / ( x1 - x0 );
269  x = mRect.xMinimum();
270  }
271
272  // Now we move outside point to intersection point to clip
273  // and get ready for next pass.
274  if ( outcodeOut == outcode0 )
275  {
276  x0 = x;
277  y0 = y;
278  outcode0 = computeOutCode( x0, y0 );
279  }
280  else
281  {
282  x1 = x;
283  y1 = y;
284  outcode1 = computeOutCode( x1, y1 );
285  }
286  }
287  }
288  return accept;
289  }
290 };
291
292
294 {
295  // this code is stupidly based on QgsGeometry::closestSegmentWithContext
296  // we need iterator for segments...
297
299  unsigned char* wkb = const_cast<unsigned char*>( geom->asWkb() ); // we're not changing wkb, just need non-const for QgsWkbPtr
300  if ( !wkb )
301  return lst;
302
303  _CohenSutherland cs( rect );
304
305  QgsWkbPtr wkbPtr( wkb + 1 );
306  QGis::WkbType wkbType;
307  wkbPtr >> wkbType;
308
309  bool hasZValue = false;
310  switch ( wkbType )
311  {
312  case QGis::WKBPoint25D:
313  case QGis::WKBPoint:
315  case QGis::WKBMultiPoint:
316  {
317  // Points have no lines
318  return lst;
319  }
320
322  hasZValue = true;
323  //intentional fall-through
324  case QGis::WKBLineString:
325  {
326  int nPoints;
327  wkbPtr >> nPoints;
328
329  double prevx = 0.0, prevy = 0.0;
330  for ( int index = 0; index < nPoints; ++index )
331  {
332  double thisx, thisy;
333  wkbPtr >> thisx >> thisy;
334  if ( hasZValue )
335  wkbPtr += sizeof( double );
336
337  if ( index > 0 )
338  {
339  if ( cs.isSegmentInRect( prevx, prevy, thisx, thisy ) )
340  {
341  QgsPoint edgePoints[2];
342  edgePoints[0].set( prevx, prevy );
343  edgePoints[1].set( thisx, thisy );
344  lst << QgsPointLocator::Match( QgsPointLocator::Edge, vl, fid, 0, QgsPoint(), index - 1, edgePoints );
345  }
346  }
347
348  prevx = thisx;
349  prevy = thisy;
350  }
351  break;
352  }
353
355  hasZValue = true;
356  //intentional fall-through
358  {
359  int nLines;
360  wkbPtr >> nLines;
361  for ( int linenr = 0, pointIndex = 0; linenr < nLines; ++linenr )
362  {
363  wkbPtr += 1 + sizeof( int );
364  int nPoints;
365  wkbPtr >> nPoints;
366
367  double prevx = 0.0, prevy = 0.0;
368  for ( int pointnr = 0; pointnr < nPoints; ++pointnr )
369  {
370  double thisx, thisy;
371  wkbPtr >> thisx >> thisy;
372  if ( hasZValue )
373  wkbPtr += sizeof( double );
374
375  if ( pointnr > 0 )
376  {
377  if ( cs.isSegmentInRect( prevx, prevy, thisx, thisy ) )
378  {
379  QgsPoint edgePoints[2];
380  edgePoints[0].set( prevx, prevy );
381  edgePoints[1].set( thisx, thisy );
382  lst << QgsPointLocator::Match( QgsPointLocator::Edge, vl, fid, 0, QgsPoint(), pointIndex - 1, edgePoints );
383  }
384  }
385
386  prevx = thisx;
387  prevy = thisy;
388  ++pointIndex;
389  }
390  }
391  break;
392  }
393
394  case QGis::WKBPolygon25D:
395  hasZValue = true;
396  //intentional fall-through
397  case QGis::WKBPolygon:
398  {
399  int nRings;
400  wkbPtr >> nRings;
401
402  for ( int ringnr = 0, pointIndex = 0; ringnr < nRings; ++ringnr )//loop over rings
403  {
404  int nPoints;
405  wkbPtr >> nPoints;
406
407  double prevx = 0.0, prevy = 0.0;
408  for ( int pointnr = 0; pointnr < nPoints; ++pointnr )//loop over points in a ring
409  {
410  double thisx, thisy;
411  wkbPtr >> thisx >> thisy;
412  if ( hasZValue )
413  wkbPtr += sizeof( double );
414
415  if ( pointnr > 0 )
416  {
417  if ( cs.isSegmentInRect( prevx, prevy, thisx, thisy ) )
418  {
419  QgsPoint edgePoints[2];
420  edgePoints[0].set( prevx, prevy );
421  edgePoints[1].set( thisx, thisy );
422  lst << QgsPointLocator::Match( QgsPointLocator::Edge, vl, fid, 0, QgsPoint(), pointIndex - 1, edgePoints );
423  }
424  }
425
426  prevx = thisx;
427  prevy = thisy;
428  ++pointIndex;
429  }
430  }
431  break;
432  }
433
435  hasZValue = true;
436  //intentional fall-through
438  {
439  int nPolygons;
440  wkbPtr >> nPolygons;
441  for ( int polynr = 0, pointIndex = 0; polynr < nPolygons; ++polynr )
442  {
443  wkbPtr += 1 + sizeof( int );
444  int nRings;
445  wkbPtr >> nRings;
446  for ( int ringnr = 0; ringnr < nRings; ++ringnr )
447  {
448  int nPoints;
449  wkbPtr >> nPoints;
450
451  double prevx = 0.0, prevy = 0.0;
452  for ( int pointnr = 0; pointnr < nPoints; ++pointnr )
453  {
454  double thisx, thisy;
455  wkbPtr >> thisx >> thisy;
456  if ( hasZValue )
457  wkbPtr += sizeof( double );
458
459  if ( pointnr > 0 )
460  {
461  if ( cs.isSegmentInRect( prevx, prevy, thisx, thisy ) )
462  {
463  QgsPoint edgePoints[2];
464  edgePoints[0].set( prevx, prevy );
465  edgePoints[1].set( thisx, thisy );
466  lst << QgsPointLocator::Match( QgsPointLocator::Edge, vl, fid, 0, QgsPoint(), pointIndex - 1, edgePoints );
467  }
468  }
469
470  prevx = thisx;
471  prevy = thisy;
472  ++pointIndex;
473  }
474  }
475  }
476  break;
477  }
478
479  case QGis::WKBUnknown:
480  default:
481  return lst;
482  break;
483  } // switch (wkbType)
484
485  return lst;
486 }
487
489 class QgsPointLocator_VisitorEdgesInRect : public IVisitor
490 {
491  public:
493  : mLocator( pl ), mList( lst ), mSrcRect( srcRect ), mFilter( filter ) {}
494
495  void visitNode( const INode& n ) override { Q_UNUSED( n ); }
496  void visitData( std::vector<const IData*>& v ) override { Q_UNUSED( v ); }
497
498  void visitData( const IData& d ) override
499  {
500  QgsFeatureId id = d.getIdentifier();
501  QgsGeometry* geom = mLocator->mGeoms.value( id );
502
503  foreach ( const QgsPointLocator::Match& m, _geometrySegmentsInRect( geom, mSrcRect, mLocator->mLayer, id ) )
504  {
505  // in range queries the filter may reject some matches
506  if ( mFilter && !mFilter->acceptMatch( m ) )
507  continue;
508
509  mList << m;
510  }
511  }
512
513  private:
514  QgsPointLocator* mLocator;
516  QgsRectangle mSrcRect;
518 };
519
520
521
523 #include <QStack>
524
526 class QgsPointLocator_DumpTree : public SpatialIndex::IQueryStrategy
527 {
528  private:
529  QStack<id_type> ids;
530
531  public:
532
533  void getNextEntry( const IEntry& entry, id_type& nextEntry, bool& hasNext ) override
534  {
535  const INode* n = dynamic_cast<const INode*>( &entry );
536  if ( !n )
537  return;
538
539  qDebug( "NODE: %ld", n->getIdentifier() );
540  if ( n->getLevel() > 0 )
541  {
542  // inner nodes
543  for ( uint32_t cChild = 0; cChild < n->getChildrenCount(); cChild++ )
544  {
545  qDebug( "- CH: %ld", n->getChildIdentifier( cChild ) );
546  ids.push( n->getChildIdentifier( cChild ) );
547  }
548  }
549  else
550  {
551  // leaves
552  for ( uint32_t cChild = 0; cChild < n->getChildrenCount(); cChild++ )
553  {
554  qDebug( "- L: %ld", n->getChildIdentifier( cChild ) );
555  }
556  }
557
558  if ( ! ids.empty() )
559  {
560  nextEntry = ids.back(); ids.pop();
561  hasNext = true;
562  }
563  else
564  hasNext = false;
565  }
566 };
567
569
570
572  : mStorage( 0 )
573  , mRTree( 0 )
574  , mIsEmptyLayer( false )
575  , mTransform( 0 )
576  , mLayer( layer )
577  , mExtent( 0 )
578 {
579  if ( destCRS )
580  {
581  mTransform = new QgsCoordinateTransform( layer->crs(), *destCRS );
582  }
583
584  if ( extent )
585  {
586  mExtent = new QgsRectangle( *extent );
587  }
588
589  mStorage = StorageManager::createNewMemoryStorageManager();
590
591  connect( mLayer, SIGNAL( featureAdded( QgsFeatureId ) ), this, SLOT( onFeatureAdded( QgsFeatureId ) ) );
592  connect( mLayer, SIGNAL( featureDeleted( QgsFeatureId ) ), this, SLOT( onFeatureDeleted( QgsFeatureId ) ) );
593  connect( mLayer, SIGNAL( geometryChanged( QgsFeatureId, QgsGeometry& ) ), this, SLOT( onGeometryChanged( QgsFeatureId, QgsGeometry& ) ) );
594 }
595
596
598 {
599  destroyIndex();
600  delete mStorage;
601  delete mTransform;
602  delete mExtent;
603 }
604
605
606 bool QgsPointLocator::init( int maxFeaturesToIndex )
607 {
608  return hasIndex() ? true : rebuildIndex( maxFeaturesToIndex );
609 }
610
612 {
613  return mRTree != 0 || mIsEmptyLayer;
614 }
615
616
617
618 bool QgsPointLocator::rebuildIndex( int maxFeaturesToIndex )
619 {
620  destroyIndex();
621
623  QgsFeature f;
624  QGis::GeometryType geomType = mLayer->geometryType();
625  if ( geomType == QGis::NoGeometry )
626  return true; // nothing to index
627
628  QgsFeatureRequest request;
630  if ( mExtent )
631  {
632  QgsRectangle rect = *mExtent;
633  if ( mTransform )
634  {
635  try {
637  } catch (const QgsException& e) {
638  // See http://hub.qgis.org/issues/12634
639  QgsDebugMsg( QString("could not transform bounding box to map, skipping the snap filter (%1)").arg(e.what()) );
640  }
641  }
642  request.setFilterRect( rect );
643  }
644  QgsFeatureIterator fi = mLayer->getFeatures( request );
645  int indexedCount = 0;
646  while ( fi.nextFeature( f ) )
647  {
648  if ( !f.geometry() )
649  continue;
650
651  if ( mTransform )
652  {
653  try {
654  f.geometry()->transform( *mTransform );
655  } catch (const QgsException& e) {
656  // See http://hub.qgis.org/issues/12634
657  QgsDebugMsg( QString("could not transform geometry to map, skipping the snap for it (%1)").arg(e.what()) );
658  continue;
659  }
660  }
661
662  SpatialIndex::Region r( rect2region( f.geometry()->boundingBox() ) );
663  dataList << new RTree::Data( 0, 0, r, f.id() );
664  mGeoms[f.id()] = new QgsGeometry( *f.geometry() );
665  ++indexedCount;
666
667  if ( maxFeaturesToIndex != -1 && indexedCount > maxFeaturesToIndex )
668  {
669  qDeleteAll( dataList );
670  destroyIndex();
671  return false;
672  }
673  }
674
675  // R-Tree parameters
676  double fillFactor = 0.7;
677  unsigned long indexCapacity = 10;
678  unsigned long leafCapacity = 10;
679  unsigned long dimension = 2;
680  RTree::RTreeVariant variant = RTree::RV_RSTAR;
681  SpatialIndex::id_type indexId;
682
683  if ( dataList.isEmpty() )
684  {
685  mIsEmptyLayer = true;
686  return true; // no features
687  }
688
689  QgsPointLocator_Stream stream( dataList );
690  mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, stream, *mStorage, fillFactor, indexCapacity,
691  leafCapacity, dimension, variant, indexId );
692  return true;
693 }
694
695
697 {
698  delete mRTree;
699  mRTree = 0;
700
701  mIsEmptyLayer = false;
702
703  foreach ( QgsGeometry* g, mGeoms )
704  delete g;
705  mGeoms.clear();
706 }
707
708 void QgsPointLocator::onFeatureAdded( QgsFeatureId fid )
709 {
710  if ( !mRTree )
711  {
712  if ( mIsEmptyLayer )
713  rebuildIndex(); // first feature - let's built the index
714  return; // nothing to do if we are not initialized yet
715  }
716
717  QgsFeature f;
718  if ( mLayer->getFeatures( QgsFeatureRequest( fid ) ).nextFeature( f ) )
719  {
720  if ( !f.geometry() )
721  return;
722
723  if ( mTransform )
724  {
725  try {
726  f.geometry()->transform( *mTransform );
727  } catch (const QgsException& e) {
728  // See http://hub.qgis.org/issues/12634
729  QgsDebugMsg( QString("could not transform geometry to map, skipping the snap for it (%1)").arg(e.what()) );
730  return;
731  }
732  }
733
734  SpatialIndex::Region r( rect2region( f.geometry()->boundingBox() ) );
735  mRTree->insertData( 0, 0, r, f.id() );
736  mGeoms[fid] = new QgsGeometry( *f.geometry() );
737  }
738 }
739
740 void QgsPointLocator::onFeatureDeleted( QgsFeatureId fid )
741 {
742  if ( !mRTree )
743  return; // nothing to do if we are not initialized yet
744
745  if ( mGeoms.contains( fid ) )
746  {
747  mRTree->deleteData( rect2region( mGeoms[fid]->boundingBox() ), fid );
748  mGeoms.remove( fid );
749  }
750 }
751
752 void QgsPointLocator::onGeometryChanged( QgsFeatureId fid, QgsGeometry& geom )
753 {
754  Q_UNUSED( geom );
755  onFeatureDeleted( fid );
757 }
758
759
761 {
762  if ( !mRTree )
763  {
764  init();
765  if ( !mRTree ) // still invalid?
766  return Match();
767  }
768
769  Match m;
770  QgsPointLocator_VisitorNearestVertex visitor( this, m, point, filter );
771  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
772  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
773  if ( m.isValid() && m.distance() > tolerance )
774  return Match(); // // make sure that only match strictly within the tolerance is returned
775  return m;
776 }
777
779 {
780  if ( !mRTree )
781  {
782  init();
783  if ( !mRTree ) // still invalid?
784  return Match();
785  }
786
787  Match m;
788  QgsPointLocator_VisitorNearestEdge visitor( this, m, point, filter );
789  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
790  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
791  if ( m.isValid() && m.distance() > tolerance )
792  return Match(); // // make sure that only match strictly within the tolerance is returned
793  return m;
794 }
795
797 {
798  if ( !mRTree )
799  {
800  init();
801  if ( !mRTree ) // still invalid?
802  return MatchList();
803  }
804
805  MatchList lst;
806  QgsPointLocator_VisitorEdgesInRect visitor( this, lst, rect, filter );
807  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
808
809  return lst;
810 }
811
813 {
814  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
815  return edgesInRect( rect, filter );
816 }
817
818
820 {
821  if ( !mRTree )
822  {
823  init();
824  if ( !mRTree ) // still invalid?
825  return MatchList();
826  }
827
828  MatchList lst;
829  QgsPointLocator_VisitorArea visitor( this, point, lst );
830  mRTree->intersectsWithQuery( point2point( point ), visitor );
831  return lst;
832 }