QGIS API Documentation  3.11.0-Master (68611307d7)
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 *
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 "qgspointlocator.h"
17 
18 #include "qgsfeatureiterator.h"
19 #include "qgsgeometry.h"
20 #include "qgsvectorlayer.h"
21 #include "qgswkbptr.h"
22 #include "qgis.h"
23 #include "qgslogger.h"
24 #include "qgsrenderer.h"
25 #include "qgsapplication.h"
28 #include "qgslinestring.h"
30 #include <spatialindex/SpatialIndex.h>
31 
32 #include <QLinkedListIterator>
33 #include <QtConcurrent>
34 
35 using namespace SpatialIndex;
36 
37 
38 
39 static SpatialIndex::Point point2point( const QgsPointXY &point )
40 {
41  double plow[2] = { point.x(), point.y() };
42  return Point( plow, 2 );
43 }
44 
45 
46 static SpatialIndex::Region rect2region( const QgsRectangle &rect )
47 {
48  double pLow[2] = { rect.xMinimum(), rect.yMinimum() };
49  double pHigh[2] = { rect.xMaximum(), rect.yMaximum() };
50  return SpatialIndex::Region( pLow, pHigh, 2 );
51 }
52 
53 
54 // Ahh.... another magic number. Taken from QgsVectorLayer::snapToGeometry() call to closestSegmentWithContext().
55 // The default epsilon used for sqrDistToSegment (1e-8) is too high when working with lat/lon coordinates
56 // I still do not fully understand why the sqrDistToSegment() code uses epsilon and if the square distance
57 // is lower than epsilon it will have a special logic...
58 static const double POINT_LOC_EPSILON = 1e-12;
59 
61 
62 
68 class QgsPointLocator_Stream : public IDataStream
69 {
70  public:
71  explicit QgsPointLocator_Stream( const QLinkedList<RTree::Data *> &dataList )
72  : mDataList( dataList )
73  , mIt( mDataList )
74  { }
75 
76  IData *getNext() override { return mIt.next(); }
77  bool hasNext() override { return mIt.hasNext(); }
78 
79  uint32_t size() override { Q_ASSERT( false && "not available" ); return 0; }
80  void rewind() override { Q_ASSERT( false && "not available" ); }
81 
82  private:
83  QLinkedList<RTree::Data *> mDataList;
84  QLinkedListIterator<RTree::Data *> mIt;
85 };
86 
87 
89 
90 
96 class QgsPointLocator_VisitorNearestVertex : public IVisitor
97 {
98  public:
100  : mLocator( pl )
101  , mBest( m )
102  , mSrcPoint( srcPoint )
103  , mFilter( filter )
104  {}
105 
106  void visitNode( const INode &n ) override { Q_UNUSED( n ) }
107  void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
108 
109  void visitData( const IData &d ) override
110  {
111  QgsFeatureId id = d.getIdentifier();
112  QgsGeometry *geom = mLocator->mGeoms.value( id );
113  int vertexIndex, beforeVertex, afterVertex;
114  double sqrDist;
115 
116  QgsPointXY pt = geom->closestVertex( mSrcPoint, vertexIndex, beforeVertex, afterVertex, sqrDist );
117  if ( sqrDist < 0 )
118  return; // probably empty geometry
119 
120  QgsPointLocator::Match m( QgsPointLocator::Vertex, mLocator->mLayer, id, std::sqrt( sqrDist ), pt, vertexIndex );
121  // in range queries the filter may reject some matches
122  if ( mFilter && !mFilter->acceptMatch( m ) )
123  return;
124 
125  if ( !mBest.isValid() || m.distance() < mBest.distance() )
126  mBest = m;
127  }
128 
129  private:
130  QgsPointLocator *mLocator = nullptr;
131  QgsPointLocator::Match &mBest;
132  QgsPointXY mSrcPoint;
133  QgsPointLocator::MatchFilter *mFilter = nullptr;
134 };
135 
136 
138 
139 
145 class QgsPointLocator_VisitorNearestEdge : public IVisitor
146 {
147  public:
149  : mLocator( pl )
150  , mBest( m )
151  , mSrcPoint( srcPoint )
152  , mFilter( filter )
153  {}
154 
155  void visitNode( const INode &n ) override { Q_UNUSED( n ) }
156  void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
157 
158  void visitData( const IData &d ) override
159  {
160  QgsFeatureId id = d.getIdentifier();
161  QgsGeometry *geom = mLocator->mGeoms.value( id );
162  QgsPointXY pt;
163  int afterVertex;
164  double sqrDist = geom->closestSegmentWithContext( mSrcPoint, pt, afterVertex, nullptr, POINT_LOC_EPSILON );
165  if ( sqrDist < 0 )
166  return;
167 
168  QgsPointXY edgePoints[2];
169  edgePoints[0] = geom->vertexAt( afterVertex - 1 );
170  edgePoints[1] = geom->vertexAt( afterVertex );
171  QgsPointLocator::Match m( QgsPointLocator::Edge, mLocator->mLayer, id, std::sqrt( sqrDist ), pt, afterVertex - 1, edgePoints );
172  // in range queries the filter may reject some matches
173  if ( mFilter && !mFilter->acceptMatch( m ) )
174  return;
175 
176  if ( !mBest.isValid() || m.distance() < mBest.distance() )
177  mBest = m;
178  }
179 
180  private:
181  QgsPointLocator *mLocator = nullptr;
182  QgsPointLocator::Match &mBest;
183  QgsPointXY mSrcPoint;
184  QgsPointLocator::MatchFilter *mFilter = nullptr;
185 };
186 
187 
189 
195 class QgsPointLocator_VisitorArea : public IVisitor
196 {
197  public:
200  : mLocator( pl )
201  , mList( list )
202  , mGeomPt( QgsGeometry::fromPointXY( origPt ) )
203  {}
204 
205  void visitNode( const INode &n ) override { Q_UNUSED( n ) }
206  void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
207 
208  void visitData( const IData &d ) override
209  {
210  QgsFeatureId id = d.getIdentifier();
211  QgsGeometry *g = mLocator->mGeoms.value( id );
212  if ( g->intersects( mGeomPt ) )
213  mList << QgsPointLocator::Match( QgsPointLocator::Area, mLocator->mLayer, id, 0, mGeomPt.asPoint() );
214  }
215  private:
216  QgsPointLocator *mLocator = nullptr;
218  QgsGeometry mGeomPt;
219 };
220 
221 
223 
224 // code adapted from
225 // http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
227 {
228  explicit _CohenSutherland( const QgsRectangle &rect ) : mRect( rect ) {}
229 
230  typedef int OutCode;
231 
232  static const int INSIDE = 0; // 0000
233  static const int LEFT = 1; // 0001
234  static const int RIGHT = 2; // 0010
235  static const int BOTTOM = 4; // 0100
236  static const int TOP = 8; // 1000
237 
239 
240  OutCode computeOutCode( double x, double y )
241  {
242  OutCode code = INSIDE; // initialized as being inside of clip window
243  if ( x < mRect.xMinimum() ) // to the left of clip window
244  code |= LEFT;
245  else if ( x > mRect.xMaximum() ) // to the right of clip window
246  code |= RIGHT;
247  if ( y < mRect.yMinimum() ) // below the clip window
248  code |= BOTTOM;
249  else if ( y > mRect.yMaximum() ) // above the clip window
250  code |= TOP;
251  return code;
252  }
253 
254  bool isSegmentInRect( double x0, double y0, double x1, double y1 )
255  {
256  // compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
257  OutCode outcode0 = computeOutCode( x0, y0 );
258  OutCode outcode1 = computeOutCode( x1, y1 );
259  bool accept = false;
260 
261  while ( true )
262  {
263  if ( !( outcode0 | outcode1 ) )
264  {
265  // Bitwise OR is 0. Trivially accept and get out of loop
266  accept = true;
267  break;
268  }
269  else if ( outcode0 & outcode1 )
270  {
271  // Bitwise AND is not 0. Trivially reject and get out of loop
272  break;
273  }
274  else
275  {
276  // failed both tests, so calculate the line segment to clip
277  // from an outside point to an intersection with clip edge
278  double x, y;
279 
280  // At least one endpoint is outside the clip rectangle; pick it.
281  OutCode outcodeOut = outcode0 ? outcode0 : outcode1;
282 
283  // Now find the intersection point;
284  // use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
285  if ( outcodeOut & TOP )
286  {
287  // point is above the clip rectangle
288  x = x0 + ( x1 - x0 ) * ( mRect.yMaximum() - y0 ) / ( y1 - y0 );
289  y = mRect.yMaximum();
290  }
291  else if ( outcodeOut & BOTTOM )
292  {
293  // point is below the clip rectangle
294  x = x0 + ( x1 - x0 ) * ( mRect.yMinimum() - y0 ) / ( y1 - y0 );
295  y = mRect.yMinimum();
296  }
297  else if ( outcodeOut & RIGHT )
298  {
299  // point is to the right of clip rectangle
300  y = y0 + ( y1 - y0 ) * ( mRect.xMaximum() - x0 ) / ( x1 - x0 );
301  x = mRect.xMaximum();
302  }
303  else if ( outcodeOut & LEFT )
304  {
305  // point is to the left of clip rectangle
306  y = y0 + ( y1 - y0 ) * ( mRect.xMinimum() - x0 ) / ( x1 - x0 );
307  x = mRect.xMinimum();
308  }
309  else
310  break;
311 
312  // Now we move outside point to intersection point to clip
313  // and get ready for next pass.
314  if ( outcodeOut == outcode0 )
315  {
316  x0 = x;
317  y0 = y;
318  outcode0 = computeOutCode( x0, y0 );
319  }
320  else
321  {
322  x1 = x;
323  y1 = y;
324  outcode1 = computeOutCode( x1, y1 );
325  }
326  }
327  }
328  return accept;
329  }
330 };
331 
332 
333 static QgsPointLocator::MatchList _geometrySegmentsInRect( QgsGeometry *geom, const QgsRectangle &rect, QgsVectorLayer *vl, QgsFeatureId fid )
334 {
335  // this code is stupidly based on QgsGeometry::closestSegmentWithContext
336  // we need iterator for segments...
337 
339 
340  // geom is converted to a MultiCurve
341  QgsGeometry straightGeom = geom->convertToType( QgsWkbTypes::LineGeometry, true );
342  // and convert to straight segemnt / converts curve to linestring
343  straightGeom.convertToStraightSegment();
344 
345  // so, you must have multilinestring
346  //
347  // Special case: Intersections cannot be done on an empty linestring like
348  // QgsGeometry(QgsLineString()) or QgsGeometry::fromWkt("LINESTRING EMPTY")
349  if ( straightGeom.isEmpty() || ( ( straightGeom.type() != QgsWkbTypes::LineGeometry ) && ( !straightGeom.isMultipart() ) ) )
350  return lst;
351 
352  _CohenSutherland cs( rect );
353 
354  int pointIndex = 0;
355  for ( auto part = straightGeom.const_parts_begin(); part != straightGeom.const_parts_end(); ++part )
356  {
357  // Checking for invalid linestrings
358  // A linestring should/(must?) have at least two points
359  if ( qgsgeometry_cast<QgsLineString *>( *part )->numPoints() < 2 )
360  continue;
361 
362  QgsAbstractGeometry::vertex_iterator it = ( *part )->vertices_begin();
363  QgsPointXY prevPoint( *it );
364  it++;
365  while ( it != ( *part )->vertices_end() )
366  {
367  QgsPointXY thisPoint( *it );
368  if ( cs.isSegmentInRect( prevPoint.x(), prevPoint.y(), thisPoint.x(), thisPoint.y() ) )
369  {
370  QgsPointXY edgePoints[2];
371  edgePoints[0] = prevPoint;
372  edgePoints[1] = thisPoint;
373  lst << QgsPointLocator::Match( QgsPointLocator::Edge, vl, fid, 0, QgsPointXY(), pointIndex - 1, edgePoints );
374  }
375  prevPoint = QgsPointXY( *it );
376  it++;
377  pointIndex += 1;
378 
379  }
380  }
381  return lst;
382 }
383 
389 class QgsPointLocator_VisitorEdgesInRect : public IVisitor
390 {
391  public:
393  : mLocator( pl )
394  , mList( lst )
395  , mSrcRect( srcRect )
396  , mFilter( filter )
397  {}
398 
399  void visitNode( const INode &n ) override { Q_UNUSED( n ) }
400  void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
401 
402  void visitData( const IData &d ) override
403  {
404  QgsFeatureId id = d.getIdentifier();
405  QgsGeometry *geom = mLocator->mGeoms.value( id );
406 
407  const auto segmentsInRect {_geometrySegmentsInRect( geom, mSrcRect, mLocator->mLayer, id )};
408  for ( const QgsPointLocator::Match &m : segmentsInRect )
409  {
410  // in range queries the filter may reject some matches
411  if ( mFilter && !mFilter->acceptMatch( m ) )
412  continue;
413 
414  mList << m;
415  }
416  }
417 
418  private:
419  QgsPointLocator *mLocator = nullptr;
421  QgsRectangle mSrcRect;
422  QgsPointLocator::MatchFilter *mFilter = nullptr;
423 };
424 
426 
434 {
435  public:
438  : mLocator( pl )
439  , mList( lst )
440  , mSrcRect( srcRect )
441  , mFilter( filter )
442  {}
443 
444  void visitNode( const INode &n ) override { Q_UNUSED( n ) }
445  void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
446 
447  void visitData( const IData &d ) override
448  {
449  QgsFeatureId id = d.getIdentifier();
450  const QgsGeometry *geom = mLocator->mGeoms.value( id );
451 
452  for ( QgsAbstractGeometry::vertex_iterator it = geom->vertices_begin(); it != geom->vertices_end(); ++it )
453  {
454  if ( mSrcRect.contains( *it ) )
455  {
456  QgsPointLocator::Match m( QgsPointLocator::Vertex, mLocator->mLayer, id, 0, *it, geom->vertexNrFromVertexId( it.vertexId() ) );
457 
458  // in range queries the filter may reject some matches
459  if ( mFilter && !mFilter->acceptMatch( m ) )
460  continue;
461 
462  mList << m;
463  }
464  }
465  }
466 
467  private:
468  QgsPointLocator *mLocator = nullptr;
470  QgsRectangle mSrcRect;
471  QgsPointLocator::MatchFilter *mFilter = nullptr;
472 };
473 
474 
476 #include <QStack>
477 
483 class QgsPointLocator_DumpTree : public SpatialIndex::IQueryStrategy
484 {
485  private:
486  QStack<id_type> ids;
487 
488  public:
489 
490  void getNextEntry( const IEntry &entry, id_type &nextEntry, bool &hasNext ) override
491  {
492  const INode *n = dynamic_cast<const INode *>( &entry );
493  if ( !n )
494  return;
495 
496  QgsDebugMsgLevel( QStringLiteral( "NODE: %1" ).arg( n->getIdentifier() ), 4 );
497  if ( n->getLevel() > 0 )
498  {
499  // inner nodes
500  for ( uint32_t cChild = 0; cChild < n->getChildrenCount(); cChild++ )
501  {
502  QgsDebugMsgLevel( QStringLiteral( "- CH: %1" ).arg( n->getChildIdentifier( cChild ) ), 4 );
503  ids.push( n->getChildIdentifier( cChild ) );
504  }
505  }
506  else
507  {
508  // leaves
509  for ( uint32_t cChild = 0; cChild < n->getChildrenCount(); cChild++ )
510  {
511  QgsDebugMsgLevel( QStringLiteral( "- L: %1" ).arg( n->getChildIdentifier( cChild ) ), 4 );
512  }
513  }
514 
515  if ( ! ids.empty() )
516  {
517  nextEntry = ids.back();
518  ids.pop();
519  hasNext = true;
520  }
521  else
522  hasNext = false;
523  }
524 };
525 
527 
528 
530  : mLayer( layer )
531 {
532  if ( destCRS.isValid() )
533  {
534  mTransform = QgsCoordinateTransform( layer->crs(), destCRS, transformContext );
535  }
536 
537  setExtent( extent );
538 
539  mStorage.reset( StorageManager::createNewMemoryStorageManager() );
540 
541  connect( mLayer, &QgsVectorLayer::featureAdded, this, &QgsPointLocator::onFeatureAdded );
542  connect( mLayer, &QgsVectorLayer::featureDeleted, this, &QgsPointLocator::onFeatureDeleted );
543  connect( mLayer, &QgsVectorLayer::geometryChanged, this, &QgsPointLocator::onGeometryChanged );
544  connect( mLayer, &QgsVectorLayer::attributeValueChanged, this, &QgsPointLocator::onAttributeValueChanged );
546 }
547 
548 
550 {
551  // don't delete a locator if there is an indexing task running on it
552  mIsDestroying = true;
553  if ( mIsIndexing )
555 
556  destroyIndex();
557 }
558 
560 {
561  return mTransform.isValid() ? mTransform.destinationCrs() : QgsCoordinateReferenceSystem();
562 }
563 
565 {
566  if ( mIsIndexing )
567  // already indexing, return!
568  return;
569 
570  mExtent.reset( extent ? new QgsRectangle( *extent ) : nullptr );
571 
572  destroyIndex();
573 }
574 
576 {
577  if ( mIsIndexing )
578  // already indexing, return!
579  return;
580 
581  disconnect( mLayer, &QgsVectorLayer::styleChanged, this, &QgsPointLocator::destroyIndex );
582 
583  destroyIndex();
584  mContext.reset( nullptr );
585 
586  if ( context )
587  {
588  mContext = std::unique_ptr<QgsRenderContext>( new QgsRenderContext( *context ) );
590  }
591 
592 }
593 
594 void QgsPointLocator::onInitTaskFinished()
595 {
596  // Check that we don't call this method twice, when calling waitForFinished
597  // for instance (because of taskCompleted signal)
598  if ( !mIsIndexing )
599  return;
600 
601  if ( mIsDestroying )
602  return;
603 
604  mIsIndexing = false;
605  mRenderer.reset();
606  mSource.reset();
607 
608  // treat added and deleted feature while indexing
609  for ( QgsFeatureId fid : mAddedFeatures )
610  onFeatureAdded( fid );
611  mAddedFeatures.clear();
612 
613  for ( QgsFeatureId fid : mDeletedFeatures )
614  onFeatureDeleted( fid );
615  mDeletedFeatures.clear();
616 
617  emit initFinished( mInitTask->isBuildOK() );
618 }
619 
620 bool QgsPointLocator::init( int maxFeaturesToIndex, bool relaxed )
621 {
622  const QgsWkbTypes::GeometryType geomType = mLayer->geometryType();
623  if ( geomType == QgsWkbTypes::NullGeometry // nothing to index
624  || hasIndex()
625  || mIsIndexing ) // already indexing, return!
626  return true;
627 
628  mRenderer.reset( mLayer->renderer() ? mLayer->renderer()->clone() : nullptr );
629  mSource.reset( new QgsVectorLayerFeatureSource( mLayer ) );
630 
631  if ( mContext )
632  {
633  mContext->expressionContext() << QgsExpressionContextUtils::layerScope( mLayer );
634  }
635 
636  mIsIndexing = true;
637 
638  if ( relaxed )
639  {
640  mInitTask = new QgsPointLocatorInitTask( this );
641  connect( mInitTask, &QgsPointLocatorInitTask::taskTerminated, this, &QgsPointLocator::onInitTaskFinished );
642  connect( mInitTask, &QgsPointLocatorInitTask::taskCompleted, this, &QgsPointLocator::onInitTaskFinished );
643  QgsApplication::taskManager()->addTask( mInitTask );
644  return true;
645  }
646  else
647  {
648  const bool ok = rebuildIndex( maxFeaturesToIndex );
649  mIsIndexing = false;
650  emit initFinished( ok );
651  return ok;
652  }
653 }
654 
656 {
657  mInitTask->waitForFinished();
658 
659  if ( !mIsDestroying )
660  onInitTaskFinished();
661 }
662 
664 {
665  return mIsIndexing || mRTree || mIsEmptyLayer;
666 }
667 
668 bool QgsPointLocator::prepare( bool relaxed )
669 {
670  if ( mIsIndexing )
671  {
672  if ( relaxed )
673  return false;
674  else
676  }
677 
678  if ( !mRTree )
679  {
680  init( -1, relaxed );
681  if ( ( relaxed && mIsIndexing ) || !mRTree ) // relaxed mode and currently indexing or still invalid?
682  return false;
683  }
684 
685  return true;
686 }
687 
688 bool QgsPointLocator::rebuildIndex( int maxFeaturesToIndex )
689 {
690  QElapsedTimer t;
691  t.start();
692 
693  QgsDebugMsg( QStringLiteral( "RebuildIndex start : %1" ).arg( mSource->id() ) );
694 
695  destroyIndex();
696 
697  QLinkedList<RTree::Data *> dataList;
698  QgsFeature f;
699 
700  QgsFeatureRequest request;
701  request.setNoAttributes();
702 
703  if ( mExtent )
704  {
705  QgsRectangle rect = *mExtent;
706  if ( mTransform.isValid() )
707  {
708  try
709  {
711  }
712  catch ( const QgsException &e )
713  {
714  Q_UNUSED( e )
715  // See https://github.com/qgis/QGIS/issues/20749
716  QgsDebugMsg( QStringLiteral( "could not transform bounding box to map, skipping the snap filter (%1)" ).arg( e.what() ) );
717  }
718  }
719  request.setFilterRect( rect );
720  }
721 
722  bool filter = false;
723  QgsRenderContext *ctx = nullptr;
724  if ( mContext )
725  {
726  ctx = mContext.get();
727  if ( mRenderer )
728  {
729  // setup scale for scale dependent visibility (rule based)
730  mRenderer->startRender( *ctx, mSource->fields() );
731  filter = mRenderer->capabilities() & QgsFeatureRenderer::Filter;
732  request.setSubsetOfAttributes( mRenderer->usedAttributes( *ctx ), mSource->fields() );
733  }
734  }
735 
736  QgsFeatureIterator fi = mSource->getFeatures( request );
737  int indexedCount = 0;
738 
739  while ( fi.nextFeature( f ) )
740  {
741  if ( !f.hasGeometry() )
742  continue;
743 
744  if ( filter && ctx && mRenderer )
745  {
746  ctx->expressionContext().setFeature( f );
747  if ( !mRenderer->willRenderFeature( f, *ctx ) )
748  {
749  continue;
750  }
751  }
752 
753  if ( mTransform.isValid() )
754  {
755  try
756  {
757  QgsGeometry transformedGeometry = f.geometry();
758  transformedGeometry.transform( mTransform );
759  f.setGeometry( transformedGeometry );
760  }
761  catch ( const QgsException &e )
762  {
763  Q_UNUSED( e )
764  // See https://github.com/qgis/QGIS/issues/20749
765  QgsDebugMsg( QStringLiteral( "could not transform geometry to map, skipping the snap for it (%1)" ).arg( e.what() ) );
766  continue;
767  }
768  }
769 
770  const QgsRectangle bbox = f.geometry().boundingBox();
771  if ( bbox.isFinite() )
772  {
773  SpatialIndex::Region r( rect2region( bbox ) );
774  dataList << new RTree::Data( 0, nullptr, r, f.id() );
775 
776  if ( mGeoms.contains( f.id() ) )
777  delete mGeoms.take( f.id() );
778  mGeoms[f.id()] = new QgsGeometry( f.geometry() );
779  ++indexedCount;
780  }
781 
782  if ( maxFeaturesToIndex != -1 && indexedCount > maxFeaturesToIndex )
783  {
784  qDeleteAll( dataList );
785  destroyIndex();
786  return false;
787  }
788  }
789 
790  // R-Tree parameters
791  double fillFactor = 0.7;
792  unsigned long indexCapacity = 10;
793  unsigned long leafCapacity = 10;
794  unsigned long dimension = 2;
795  RTree::RTreeVariant variant = RTree::RV_RSTAR;
796  SpatialIndex::id_type indexId;
797 
798  if ( dataList.isEmpty() )
799  {
800  mIsEmptyLayer = true;
801  return true; // no features
802  }
803 
804  QgsPointLocator_Stream stream( dataList );
805  mRTree.reset( RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, stream, *mStorage, fillFactor, indexCapacity,
806  leafCapacity, dimension, variant, indexId ) );
807 
808  if ( ctx && mRenderer )
809  {
810  mRenderer->stopRender( *ctx );
811  }
812 
813  QgsDebugMsg( QStringLiteral( "RebuildIndex end : %1 ms (%2)" ).arg( t.elapsed() ).arg( mSource->id() ) );
814 
815  return true;
816 }
817 
818 
820 {
821  mRTree.reset();
822 
823  mIsEmptyLayer = false;
824 
825  qDeleteAll( mGeoms );
826 
827  mGeoms.clear();
828 }
829 
830 void QgsPointLocator::onFeatureAdded( QgsFeatureId fid )
831 {
832  if ( mIsIndexing )
833  {
834  // will modify index once current indexing is finished
835  mAddedFeatures << fid;
836  return;
837  }
838 
839  if ( !mRTree )
840  {
841  if ( mIsEmptyLayer )
842  {
843  // layer is not empty any more, let's build the index
844  mIsEmptyLayer = false;
845  init();
846  }
847  return; // nothing to do if we are not initialized yet
848  }
849 
850  QgsFeature f;
851  if ( mLayer->getFeatures( QgsFeatureRequest( fid ) ).nextFeature( f ) )
852  {
853  if ( !f.hasGeometry() )
854  return;
855 
856  if ( mContext )
857  {
858  std::unique_ptr< QgsFeatureRenderer > renderer( mLayer->renderer() ? mLayer->renderer()->clone() : nullptr );
859  QgsRenderContext *ctx = nullptr;
860 
861  mContext->expressionContext() << QgsExpressionContextUtils::layerScope( mLayer );
862  ctx = mContext.get();
863  if ( renderer && ctx )
864  {
865  bool pass = false;
866  renderer->startRender( *ctx, mLayer->fields() );
867 
868  ctx->expressionContext().setFeature( f );
869  if ( !renderer->willRenderFeature( f, *ctx ) )
870  {
871  pass = true;
872  }
873 
874  renderer->stopRender( *ctx );
875  if ( pass )
876  return;
877  }
878  }
879 
880  if ( mTransform.isValid() )
881  {
882  try
883  {
884  QgsGeometry transformedGeom = f.geometry();
885  transformedGeom.transform( mTransform );
886  f.setGeometry( transformedGeom );
887  }
888  catch ( const QgsException &e )
889  {
890  Q_UNUSED( e )
891  // See https://github.com/qgis/QGIS/issues/20749
892  QgsDebugMsg( QStringLiteral( "could not transform geometry to map, skipping the snap for it (%1)" ).arg( e.what() ) );
893  return;
894  }
895  }
896 
897  const QgsRectangle bbox = f.geometry().boundingBox();
898  if ( bbox.isFinite() )
899  {
900  SpatialIndex::Region r( rect2region( bbox ) );
901  mRTree->insertData( 0, nullptr, r, f.id() );
902 
903  if ( mGeoms.contains( f.id() ) )
904  delete mGeoms.take( f.id() );
905  mGeoms[fid] = new QgsGeometry( f.geometry() );
906  }
907  }
908 }
909 
910 void QgsPointLocator::onFeatureDeleted( QgsFeatureId fid )
911 {
912  if ( mIsIndexing )
913  {
914  if ( mAddedFeatures.contains( fid ) )
915  {
916  mAddedFeatures.remove( fid );
917  }
918  else
919  {
920  // will modify index once current indexing is finished
921  mDeletedFeatures << fid;
922  }
923  return;
924  }
925 
926  if ( !mRTree )
927  return; // nothing to do if we are not initialized yet
928 
929  if ( mGeoms.contains( fid ) )
930  {
931  mRTree->deleteData( rect2region( mGeoms[fid]->boundingBox() ), fid );
932  delete mGeoms.take( fid );
933  }
934 
935 }
936 
937 void QgsPointLocator::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
938 {
939  Q_UNUSED( geom )
940  onFeatureDeleted( fid );
941  onFeatureAdded( fid );
942 }
943 
944 void QgsPointLocator::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
945 {
946  Q_UNUSED( idx )
947  Q_UNUSED( value )
948  if ( mContext )
949  {
950  onFeatureDeleted( fid );
951  onFeatureAdded( fid );
952  }
953 }
954 
955 
956 QgsPointLocator::Match QgsPointLocator::nearestVertex( const QgsPointXY &point, double tolerance, MatchFilter *filter, bool relaxed )
957 {
958  if ( !prepare( relaxed ) )
959  return Match();
960 
961  Match m;
962  QgsPointLocator_VisitorNearestVertex visitor( this, m, point, filter );
963  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
964  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
965  if ( m.isValid() && m.distance() > tolerance )
966  return Match(); // make sure that only match strictly within the tolerance is returned
967  return m;
968 }
969 
970 QgsPointLocator::Match QgsPointLocator::nearestEdge( const QgsPointXY &point, double tolerance, MatchFilter *filter, bool relaxed )
971 {
972  if ( !prepare( relaxed ) )
973  return Match();
974 
975  QgsWkbTypes::GeometryType geomType = mLayer->geometryType();
976  if ( geomType == QgsWkbTypes::PointGeometry )
977  return Match();
978 
979  Match m;
980  QgsPointLocator_VisitorNearestEdge visitor( this, m, point, filter );
981  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
982  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
983  if ( m.isValid() && m.distance() > tolerance )
984  return Match(); // make sure that only match strictly within the tolerance is returned
985  return m;
986 }
987 
988 QgsPointLocator::Match QgsPointLocator::nearestArea( const QgsPointXY &point, double tolerance, MatchFilter *filter, bool relaxed )
989 {
990  if ( !prepare( relaxed ) )
991  return Match();
992 
993  MatchList mlist = pointInPolygon( point );
994  if ( !mlist.isEmpty() && mlist.at( 0 ).isValid() )
995  {
996  return mlist.at( 0 );
997  }
998 
999  if ( tolerance == 0 )
1000  {
1001  return Match();
1002  }
1003 
1004  // discard point and line layers to keep only polygons
1005  QgsWkbTypes::GeometryType geomType = mLayer->geometryType();
1006  if ( geomType == QgsWkbTypes::PointGeometry || geomType == QgsWkbTypes::LineGeometry )
1007  return Match();
1008 
1009  // use edges for adding tolerance
1010  Match m = nearestEdge( point, tolerance, filter );
1011  if ( m.isValid() )
1012  return Match( Area, m.layer(), m.featureId(), m.distance(), m.point() );
1013  else
1014  return Match();
1015 }
1016 
1017 
1019 {
1020  if ( !prepare( relaxed ) )
1021  return MatchList();
1022 
1023  QgsWkbTypes::GeometryType geomType = mLayer->geometryType();
1024  if ( geomType == QgsWkbTypes::PointGeometry )
1025  return MatchList();
1026 
1027  MatchList lst;
1028  QgsPointLocator_VisitorEdgesInRect visitor( this, lst, rect, filter );
1029  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
1030 
1031  return lst;
1032 }
1033 
1035 {
1036  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
1037  return edgesInRect( rect, filter, relaxed );
1038 }
1039 
1041 {
1042  if ( !prepare( relaxed ) )
1043  return MatchList();
1044 
1045  MatchList lst;
1046  QgsPointLocator_VisitorVerticesInRect visitor( this, lst, rect, filter );
1047  mRTree->intersectsWithQuery( rect2region( rect ), visitor );
1048 
1049  return lst;
1050 }
1051 
1053 {
1054  QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
1055  return verticesInRect( rect, filter, relaxed );
1056 }
1057 
1059 {
1060  if ( !prepare( relaxed ) )
1061  return MatchList();
1062 
1063  QgsWkbTypes::GeometryType geomType = mLayer->geometryType();
1064  if ( geomType == QgsWkbTypes::PointGeometry || geomType == QgsWkbTypes::LineGeometry )
1065  return MatchList();
1066 
1067  MatchList lst;
1068  QgsPointLocator_VisitorArea visitor( this, point, lst );
1069  mRTree->intersectsWithQuery( point2point( point ), visitor );
1070  return lst;
1071 }
#define LEFT(x)
Definition: priorityqueue.h:38
The class defines interface for querying point location:
QgsFeatureId id
Definition: qgsfeature.h:64
Wrapper for iterator of features from vector data provider or vector layer.
void initFinished(bool ok)
Emitted whenever index has been built and initialization is finished.
double closestSegmentWithContext(const QgsPointXY &point, QgsPointXY &minDistPoint, int &afterVertex, int *leftOf=nullptr, double epsilon=DEFAULT_SEGMENT_EPSILON) const
Searches for the closest segment of geometry to the given point.
void visitData(std::vector< const IData *> &v) override
A rectangle specified with double values.
Definition: qgsrectangle.h:41
bool isMultipart() const
Returns true if WKB of the geometry is of WKBMulti* type.
OperationResult transform(const QgsCoordinateTransform &ct, QgsCoordinateTransform::TransformDirection direction=QgsCoordinateTransform::ForwardTransform, bool transformZ=false) SIP_THROW(QgsCsException)
Transforms this geometry as described by the coordinate transform ct.
MatchList verticesInRect(const QgsRectangle &rect, QgsPointLocator::MatchFilter *filter=nullptr, bool relaxed=false)
Find vertices within a specified recangle This method is either blocking or non blocking according to...
QgsVectorLayer * layer() const
The vector layer where the snap occurred.
Match nearestVertex(const QgsPointXY &point, double tolerance, QgsPointLocator::MatchFilter *filter=nullptr, bool relaxed=false)
Find nearest vertex to the specified point - up to distance specified by tolerance Optional filter ma...
uint32_t size() override
void visitData(const IData &d) override
void setFeature(const QgsFeature &feature)
Convenience function for setting a feature for the context.
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
bool hasIndex() const
Indicate whether the data have been already indexed.
Features may be filtered, i.e. some features may not be rendered (categorized, rule based ...
Definition: qgsrenderer.h:256
double y
Definition: qgspointxy.h:48
QgsPointLocator_VisitorArea(QgsPointLocator *pl, const QgsPointXY &origPt, QgsPointLocator::MatchList &list)
constructor
A class to represent a 2D point.
Definition: qgspointxy.h:43
QgsAbstractGeometry::const_part_iterator const_parts_end() const
Returns STL-style iterator pointing to the imaginary part after the last part of the geometry...
QgsAbstractGeometry::const_part_iterator const_parts_begin() const
Returns STL-style const iterator pointing to the first part of the geometry.
qint64 QgsFeatureId
Definition: qgsfeatureid.h:25
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
MatchList pointInPolygon(const QgsPointXY &point, bool relaxed=false)
find out if the point is in any polygons This method is either blocking or non blocking according to ...
QgsCoordinateReferenceSystem destinationCrs() const
Gets destination CRS - may be an invalid QgsCoordinateReferenceSystem if not doing OTF reprojection...
QgsWkbTypes::GeometryType geometryType() const
Returns point, line or polygon.
QgsCoordinateReferenceSystem destinationCrs() const
Returns the destination coordinate reference system, which the transform will transform coordinates t...
QgsPointLocator_VisitorVerticesInRect(QgsPointLocator *pl, QgsPointLocator::MatchList &lst, const QgsRectangle &srcRect, QgsPointLocator::MatchFilter *filter=nullptr)
Constructs the visitor.
class QList< QgsPointLocator::Match > MatchList
Helper class used when traversing the index looking for edges - builds a list of matches.
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:122
bool rebuildIndex(int maxFeaturesToIndex=-1)
void visitNode(const INode &n) override
Match nearestEdge(const QgsPointXY &point, double tolerance, QgsPointLocator::MatchFilter *filter=nullptr, bool relaxed=false)
Find nearest edge to the specified point - up to distance specified by tolerance Optional filter may ...
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:55
Interface that allows rejection of some matches in intersection queries (e.g.
void waitForIndexingFinished()
If the point locator has been initialized relaxedly and is currently indexing, this methods waits for...
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:197
void visitData(std::vector< const IData *> &v) override
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
void convertToStraightSegment(double tolerance=M_PI/180., QgsAbstractGeometry::SegmentationToleranceType toleranceType=QgsAbstractGeometry::MaximumAngle)
Converts the geometry to straight line segments, if it is a curved geometry type. ...
bool isValid() const
Returns true if the coordinate transform is valid, ie both the source and destination CRS have been s...
void styleChanged()
Signal emitted whenever a change affects the layer&#39;s style.
QgsPointLocator_Stream(const QLinkedList< RTree::Data *> &dataList)
QString what() const
Definition: qgsexception.h:48
QgsPointXY closestVertex(const QgsPointXY &point, int &atVertex, int &beforeVertex, int &afterVertex, double &sqrDist) const
Returns the vertex closest to the given point, the corresponding vertex index, squared distance snap ...
bool intersects(const QgsRectangle &rectangle) const
Returns true if this geometry exactly intersects with a rectangle.
static QgsTaskManager * taskManager()
Returns the application&#39;s task manager, used for managing application wide background task handling...
~QgsPointLocator() override
QgsFields fields() const FINAL
Returns the list of fields of this layer.
#define QgsDebugMsgLevel(str, level)
Definition: qgslogger.h:39
QgsPointLocator_VisitorNearestVertex(QgsPointLocator *pl, QgsPointLocator::Match &m, const QgsPointXY &srcPoint, QgsPointLocator::MatchFilter *filter=nullptr)
OutCode computeOutCode(double x, double y)
QgsFeatureRequest & setNoAttributes()
Set that no attributes will be fetched.
void setRenderContext(const QgsRenderContext *context)
Configure render context - if not nullptr, it will use to index only visible feature.
Snapped to a vertex. Can be a vertex of the geometry or an intersection.
long addTask(QgsTask *task, int priority=0)
Adds a task to the manager.
Helper class to dump the R-index nodes and their content.
This class wraps a request for features to a vector layer (or directly its vector data provider)...
bool isSegmentInRect(double x0, double y0, double x1, double y1)
QgsFeatureRequest & setFilterRect(const QgsRectangle &rectangle)
Sets the rectangle from which features will be taken.
bool isEmpty() const
Returns true if the geometry is empty (eg a linestring with no vertices, or a collection with no geom...
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Emitted whenever a geometry change is done in the edit buffer.
void visitNode(const INode &n) override
void setExtent(const QgsRectangle *extent)
Configure extent - if not nullptr, it will index only that area.
Helper class used when traversing the index with areas - builds a list of matches.
QgsFeatureRenderer * renderer()
Returns renderer.
void attributeValueChanged(QgsFeatureId fid, int idx, const QVariant &value)
Emitted whenever an attribute value change is done in the edit buffer.
void featureAdded(QgsFeatureId fid)
Emitted when a new feature has been added to the layer.
Contains information about the context in which a coordinate transform is executed.
The vertex_iterator class provides STL-style iterator for vertices.
void visitData(const IData &d) override
Helper class used when traversing the index looking for vertices - builds a list of matches...
const QgsRectangle * extent() const
Gets extent of the area point locator covers - if nullptr then it caches the whole layer...
void visitData(std::vector< const IData *> &v) override
void visitNode(const INode &n) override
bool isFinite() const
Returns true if the rectangle has finite boundaries.
Definition: qgsrectangle.h:516
double x
Definition: qgspointxy.h:47
MatchList edgesInRect(const QgsRectangle &rect, QgsPointLocator::MatchFilter *filter=nullptr, bool relaxed=false)
Find edges within a specified recangle Optional filter may discard unwanted matches.
Partial snapshot of vector layer&#39;s state (only the members necessary for access to features) ...
IData * getNext() override
void visitData(std::vector< const IData *> &v) override
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:177
QgsExpressionContext & expressionContext()
Gets the expression context.
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:162
GeometryType
The geometry types are used to group QgsWkbTypes::Type in a coarse way.
Definition: qgswkbtypes.h:139
QgsPointLocator(QgsVectorLayer *layer, const QgsCoordinateReferenceSystem &destinationCrs=QgsCoordinateReferenceSystem(), const QgsCoordinateTransformContext &transformContext=QgsCoordinateTransformContext(), const QgsRectangle *extent=nullptr)
Construct point locator for a layer.
QgsPointXY point() const
for vertex / edge match coords depending on what class returns it (geom.cache: layer coords...
Contains information about the context of a rendering operation.
QgsPoint vertexAt(int atVertex) const
Returns coordinates of a vertex.
void visitData(std::vector< const IData *> &v) override
Transform from destination to source CRS.
QgsPointLocator_VisitorNearestEdge(QgsPointLocator *pl, QgsPointLocator::Match &m, const QgsPointXY &srcPoint, QgsPointLocator::MatchFilter *filter=nullptr)
Helper class for bulk loading of R-trees.
int vertexNrFromVertexId(QgsVertexId id) const
Returns the vertex number corresponding to a vertex id.
#define RIGHT(x)
Definition: priorityqueue.h:39
void visitData(const IData &d) override
void visitNode(const INode &n) override
bool init(int maxFeaturesToIndex=-1, bool relaxed=false)
Prepare the index for queries.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
This class represents a coordinate reference system (CRS).
_CohenSutherland(const QgsRectangle &rect)
void setGeometry(const QgsGeometry &geometry)
Set the feature&#39;s geometry.
Definition: qgsfeature.cpp:137
void getNextEntry(const IEntry &entry, id_type &nextEntry, bool &hasNext) override
void visitData(const IData &d) override
Class for doing transforms between two map coordinate systems.
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:167
Match nearestArea(const QgsPointXY &point, double tolerance, QgsPointLocator::MatchFilter *filter=nullptr, bool relaxed=false)
Find nearest area to the specified point - up to distance specified by tolerance Optional filter may ...
friend class QgsPointLocatorInitTask
void dataChanged()
Data of layer changed.
Helper class used when traversing the index looking for vertices - builds a list of matches...
Snapped to an edge.
double distance() const
for vertex / edge match units depending on what class returns it (geom.cache: layer units...
QgsGeometry convertToType(QgsWkbTypes::GeometryType destType, bool destMultipart=false) const
Try to convert the geometry to the requested type.
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:172
QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest()) const FINAL
Queries the layer for features specified in request.
Helper class used when traversing the index looking for edges - builds a list of matches.
void visitNode(const INode &n) override
QgsWkbTypes::GeometryType type
Definition: qgsgeometry.h:126
QgsGeometry geometry
Definition: qgsfeature.h:67
static QgsExpressionContextScope * layerScope(const QgsMapLayer *layer)
Creates a new scope which contains variables and functions relating to a QgsMapLayer.
QgsFeatureId featureId() const
The id of the feature to which the snapped geometry belongs.
bool nextFeature(QgsFeature &f)
Represents a vector layer which manages a vector based data sets.
QgsAbstractGeometry::vertex_iterator vertices_end() const
Returns STL-style iterator pointing to the imaginary vertex after the last vertex of the geometry...
Defines a QGIS exception class.
Definition: qgsexception.h:34
QgsAbstractGeometry::vertex_iterator vertices_begin() const
Returns STL-style iterator pointing to the first vertex of the geometry.
void visitData(const IData &d) override
Snapped to an area.
virtual QgsFeatureRenderer * clone() const =0
Create a deep copy of this renderer.
QgsPointLocator_VisitorEdgesInRect(QgsPointLocator *pl, QgsPointLocator::MatchList &lst, const QgsRectangle &srcRect, QgsPointLocator::MatchFilter *filter=nullptr)
QgsRectangle transformBoundingBox(const QgsRectangle &rectangle, TransformDirection direction=ForwardTransform, bool handle180Crossover=false) const SIP_THROW(QgsCsException)
Transforms a rectangle from the source CRS to the destination CRS.
QgsCoordinateReferenceSystem crs
Definition: qgsmaplayer.h:86
bool isValid() const
Returns whether this CRS is correctly initialized and usable.