QGIS API Documentation  3.16.0-Hannover (43b64b13f3)
qgstracer.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgstracer.cpp
3  --------------------------------------
4  Date : January 2016
5  Copyright : (C) 2016 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 "qgstracer.h"
17
18
19 #include "qgsfeatureiterator.h"
20 #include "qgsgeometry.h"
21 #include "qgsgeometryutils.h"
22 #include "qgsgeos.h"
23 #include "qgslogger.h"
24 #include "qgsvectorlayer.h"
25 #include "qgsexception.h"
26 #include "qgsrenderer.h"
27 #include "qgssettings.h"
29
30 #include <queue>
31 #include <vector>
32
33 typedef std::pair<int, double> DijkstraQueueItem; // first = vertex index, second = distance
34
35 // utility comparator for queue items based on distance
36 struct comp
37 {
39  {
40  return a.second > b.second;
41  }
42 };
43
44
45 // TODO: move to geometry utils
46 double distance2D( const QgsPolylineXY &coords )
47 {
48  int np = coords.count();
49  if ( np == 0 )
50  return 0;
51
52  double x0 = coords[0].x(), y0 = coords[0].y();
53  double x1, y1;
54  double dist = 0;
55  for ( int i = 1; i < np; ++i )
56  {
57  x1 = coords[i].x();
58  y1 = coords[i].y();
59  dist += std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
60  x0 = x1;
61  y0 = y1;
62  }
63  return dist;
64 }
65
66
67 // TODO: move to geometry utils
68 double closestSegment( const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon )
69 {
70  double sqrDist = std::numeric_limits<double>::max();
71  const QgsPointXY *pldata = pl.constData();
72  int plcount = pl.count();
73  double prevX = pldata[0].x(), prevY = pldata[0].y();
74  double segmentPtX, segmentPtY;
75  for ( int i = 1; i < plcount; ++i )
76  {
77  double currentX = pldata[i].x();
78  double currentY = pldata[i].y();
79  double testDist = QgsGeometryUtils::sqrDistToLine( pt.x(), pt.y(), prevX, prevY, currentX, currentY, segmentPtX, segmentPtY, epsilon );
80  if ( testDist < sqrDist )
81  {
82  sqrDist = testDist;
83  vertexAfter = i;
84  }
85  prevX = currentX;
86  prevY = currentY;
87  }
88  return sqrDist;
89 }
90
92
95 {
96  QgsTracerGraph() = default;
97
98  struct E // bidirectional edge
99  {
101  int v1, v2;
103  QVector<QgsPointXY> coords;
104
105  int otherVertex( int v0 ) const { return v1 == v0 ? v2 : v1; }
106  double weight() const { return distance2D( coords ); }
107  };
108
109  struct V
110  {
114  QVector<int> edges;
115  };
116
118  QVector<V> v;
120  QVector<E> e;
121
123  QSet<int> inactiveEdges;
125  int joinedVertices{ 0 };
126 };
127
128
129 QgsTracerGraph *makeGraph( const QVector<QgsPolylineXY> &edges )
130 {
131  QgsTracerGraph *g = new QgsTracerGraph();
132  g->joinedVertices = 0;
133  QHash<QgsPointXY, int> point2vertex;
134
135  const auto constEdges = edges;
136  for ( const QgsPolylineXY &line : constEdges )
137  {
138  QgsPointXY p1( line[0] );
139  QgsPointXY p2( line[line.count() - 1] );
140
141  int v1 = -1, v2 = -1;
142  // get or add vertex 1
143  if ( point2vertex.contains( p1 ) )
144  v1 = point2vertex.value( p1 );
145  else
146  {
147  v1 = g->v.count();
149  v.pt = p1;
150  g->v.append( v );
151  point2vertex[p1] = v1;
152  }
153
154  // get or add vertex 2
155  if ( point2vertex.contains( p2 ) )
156  v2 = point2vertex.value( p2 );
157  else
158  {
159  v2 = g->v.count();
161  v.pt = p2;
162  g->v.append( v );
163  point2vertex[p2] = v2;
164  }
165
168  e.v1 = v1;
169  e.v2 = v2;
170  e.coords = line;
171  g->e.append( e );
172
173  // link edge to vertices
174  int eIdx = g->e.count() - 1;
175  g->v[v1].edges << eIdx;
176  g->v[v2].edges << eIdx;
177  }
178
179  return g;
180 }
181
182
183 QVector<QgsPointXY> shortestPath( const QgsTracerGraph &g, int v1, int v2 )
184 {
185  if ( v1 == -1 || v2 == -1 )
186  return QVector<QgsPointXY>(); // invalid input
187
188  // priority queue to drive Dijkstra:
189  // first of the pair is vertex index, second is distance
190  std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >, comp > Q;
191
192  // shortest distances to each vertex
193  QVector<double> D( g.v.count(), std::numeric_limits<double>::max() );
194  D[v1] = 0;
195
196  // whether vertices have been already processed
197  QVector<bool> F( g.v.count() );
198
199  // using which edge there is shortest path to each vertex
200  QVector<int> S( g.v.count(), -1 );
201
202  int u = -1;
203  Q.push( DijkstraQueueItem( v1, 0 ) );
204
205  while ( !Q.empty() )
206  {
207  u = Q.top().first; // new vertex to visit
208  Q.pop();
209
210  if ( u == v2 )
211  break; // we can stop now, there won't be a shorter path
212
213  if ( F[u] )
214  continue; // ignore previously added path which is actually longer
215
216  const QgsTracerGraph::V &vu = g.v[u];
217  const int *vuEdges = vu.edges.constData();
218  int count = vu.edges.count();
219  for ( int i = 0; i < count; ++i )
220  {
221  const QgsTracerGraph::E &edge = g.e[ vuEdges[i] ];
222  int v = edge.otherVertex( u );
223  double w = edge.weight();
224  if ( !F[v] && D[u] + w < D[v] )
225  {
226  // found a shorter way to the vertex
227  D[v] = D[u] + w;
228  S[v] = vuEdges[i];
229  Q.push( DijkstraQueueItem( v, D[v] ) );
230  }
231  }
232  F[u] = true; // mark the vertex as processed (we know the fastest path to it)
233  }
234
235  if ( u != v2 ) // there's no path to the end vertex
236  return QVector<QgsPointXY>();
237
238  //qDebug("dist %f", D[u]);
239
240  QVector<QgsPointXY> points;
241  QList<int> path;
242  while ( S[u] != -1 )
243  {
244  path << S[u];
245  const QgsTracerGraph::E &e = g.e[S[u]];
246  QVector<QgsPointXY> edgePoints = e.coords;
247  if ( edgePoints[0] != g.v[u].pt )
248  std::reverse( edgePoints.begin(), edgePoints.end() );
249  if ( !points.isEmpty() )
250  points.remove( points.count() - 1 ); // chop last one (will be used from next edge)
251  points << edgePoints;
252  u = e.otherVertex( u );
253  }
254
255  std::reverse( path.begin(), path.end() );
256  //Q_FOREACH (int x, path)
257  // qDebug("e: %d", x);
258
259  std::reverse( points.begin(), points.end() );
260  return points;
261 }
262
263
264 int point2vertex( const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon = 1e-6 )
265 {
266  // TODO: use spatial index
267
268  for ( int i = 0; i < g.v.count(); ++i )
269  {
270  const QgsTracerGraph::V &v = g.v.at( i );
271  if ( v.pt == pt || ( std::fabs( v.pt.x() - pt.x() ) < epsilon && std::fabs( v.pt.y() - pt.y() ) < epsilon ) )
272  return i;
273  }
274
275  return -1;
276 }
277
278
279 int point2edge( const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon = 1e-6 )
280 {
281  for ( int i = 0; i < g.e.count(); ++i )
282  {
283  if ( g.inactiveEdges.contains( i ) )
284  continue; // ignore temporarily disabled edges
285
286  const QgsTracerGraph::E &e = g.e.at( i );
287  int vertexAfter = -1;
288  double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
289  if ( dist == 0 )
290  {
291  lineVertexAfter = vertexAfter;
292  return i;
293  }
294  }
295  return -1;
296 }
297
298
299 void splitLinestring( const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2 )
300 {
301  int count1 = lineVertexAfter;
302  int count2 = points.count() - lineVertexAfter;
303
304  for ( int i = 0; i < count1; ++i )
305  pts1 << points[i];
306  if ( points[lineVertexAfter - 1] != pt )
307  pts1 << pt; // repeat if not split exactly at that point
308
309  if ( pt != points[lineVertexAfter] )
310  pts2 << pt; // repeat if not split exactly at that point
311  for ( int i = 0; i < count2; ++i )
312  pts2 << points[i + lineVertexAfter];
313 }
314
315
317 {
318  // find edge where the point is
319  int lineVertexAfter;
320  int eIdx = point2edge( g, pt, lineVertexAfter );
321
322  //qDebug("e: %d", eIdx);
323
324  if ( eIdx == -1 )
325  return -1;
326
327  const QgsTracerGraph::E &e = g.e[eIdx];
328  QgsTracerGraph::V &v1 = g.v[e.v1];
329  QgsTracerGraph::V &v2 = g.v[e.v2];
330
331  QgsPolylineXY out1, out2;
332  splitLinestring( e.coords, pt, lineVertexAfter, out1, out2 );
333
334  int vIdx = g.v.count();
335  int e1Idx = g.e.count();
336  int e2Idx = e1Idx + 1;
337
338  // prepare new vertex and edges
339
341  v.pt = pt;
342  v.edges << e1Idx << e2Idx;
343
345  e1.v1 = e.v1;
346  e1.v2 = vIdx;
347  e1.coords = out1;
348
350  e2.v1 = vIdx;
351  e2.v2 = e.v2;
352  e2.coords = out2;
353
354  // update edge connectivity of existing vertices
355  v1.edges.replace( v1.edges.indexOf( eIdx ), e1Idx );
356  v2.edges.replace( v2.edges.indexOf( eIdx ), e2Idx );
357  g.inactiveEdges << eIdx;
358
359  // add new vertex and edges to the graph
360  g.v.append( v );
361  g.e.append( e1 );
362  g.e.append( e2 );
363  g.joinedVertices++;
364
365  return vIdx;
366 }
367
368
370 {
371  // try to use existing vertex in the graph
372  int v = point2vertex( g, pt );
373  if ( v != -1 )
374  return v;
375
376  // try to add the vertex to an edge (may fail if point is not on edge)
377  return joinVertexToGraph( g, pt );
378 }
379
380
382 {
383  // remove extra vertices and edges
384  g.v.resize( g.v.count() - g.joinedVertices );
385  g.e.resize( g.e.count() - g.joinedVertices * 2 );
386  g.joinedVertices = 0;
387
388  // fix vertices of deactivated edges
389  for ( int eIdx : qgis::as_const( g.inactiveEdges ) )
390  {
391  if ( eIdx >= g.e.count() )
392  continue;
393  const QgsTracerGraph::E &e = g.e[eIdx];
394  QgsTracerGraph::V &v1 = g.v[e.v1];
395  for ( int i = 0; i < v1.edges.count(); ++i )
396  {
397  if ( v1.edges[i] >= g.e.count() )
398  v1.edges.remove( i-- );
399  }
400  v1.edges << eIdx;
401
402  QgsTracerGraph::V &v2 = g.v[e.v2];
403  for ( int i = 0; i < v2.edges.count(); ++i )
404  {
405  if ( v2.edges[i] >= g.e.count() )
406  v2.edges.remove( i-- );
407  }
408  v2.edges << eIdx;
409  }
410
411  g.inactiveEdges.clear();
412 }
413
414
416 {
417  QgsGeometry geom = g;
418  // segmentize curved geometries - we will use noding algorithm from GEOS
419  // to find all intersections a bit later (so we need them segmentized anyway)
420  if ( QgsWkbTypes::isCurvedType( g.wkbType() ) )
421  {
422  QgsAbstractGeometry *segmentizedGeomV2 = g.constGet()->segmentize();
423  if ( !segmentizedGeomV2 )
424  return;
425
426  geom = QgsGeometry( segmentizedGeomV2 );
427  }
428
429  switch ( QgsWkbTypes::flatType( geom.wkbType() ) )
430  {
432  mpl << geom.asPolyline();
433  break;
434
436  {
437  const auto polygon = geom.asPolygon();
438  for ( const QgsPolylineXY &ring : polygon )
439  mpl << ring;
440  }
441  break;
442
444  {
445  const auto multiPolyline = geom.asMultiPolyline();
446  for ( const QgsPolylineXY &linestring : multiPolyline )
447  mpl << linestring;
448  }
449  break;
450
452  {
453  const auto multiPolygon = geom.asMultiPolygon();
454  for ( const QgsPolygonXY &polygon : multiPolygon )
455  {
456  for ( const QgsPolylineXY &ring : polygon )
457  mpl << ring;
458  }
459  }
460  break;
461
462  default:
463  break; // unknown type - do nothing
464  }
465 }
466
467 // -------------
468
469
470 QgsTracer::QgsTracer() = default;
471
472 bool QgsTracer::initGraph()
473 {
474  if ( mGraph )
475  return true; // already initialized
476
477  mHasTopologyProblem = false;
478
479  QgsFeature f;
480  QgsMultiPolylineXY mpl;
481
482  // extract linestrings
483
484  // TODO: use QgsPointLocator as a source for the linework
485
486  QElapsedTimer t1, t2, t2a, t3;
487
488  t1.start();
489  int featuresCounted = 0;
490  bool enableInvisibleFeature = QgsSettings().value( QStringLiteral( "/qgis/digitizing/snap_invisible_feature" ), false ).toBool();
491  for ( const QgsVectorLayer *vl : qgis::as_const( mLayers ) )
492  {
493  QgsFeatureRequest request;
494  bool filter = false;
495  std::unique_ptr< QgsFeatureRenderer > renderer;
496  std::unique_ptr<QgsRenderContext> ctx;
497
498  if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
499  {
500  renderer.reset( vl->renderer()->clone() );
501  ctx.reset( new QgsRenderContext( *mRenderContext.get() ) );
503
504  // setup scale for scale dependent visibility (rule based)
505  renderer->startRender( *ctx.get(), vl->fields() );
506  filter = renderer->capabilities() & QgsFeatureRenderer::Filter;
507  request.setSubsetOfAttributes( renderer->usedAttributes( *ctx.get() ), vl->fields() );
508  }
509  else
510  {
511  request.setNoAttributes();
512  }
513
514  request.setDestinationCrs( mCRS, mTransformContext );
515  if ( !mExtent.isEmpty() )
516  request.setFilterRect( mExtent );
517
518  QgsFeatureIterator fi = vl->getFeatures( request );
519  while ( fi.nextFeature( f ) )
520  {
521  if ( !f.hasGeometry() )
522  continue;
523
524  if ( filter )
525  {
526  ctx->expressionContext().setFeature( f );
527  if ( !renderer->willRenderFeature( f, *ctx.get() ) )
528  {
529  continue;
530  }
531  }
532
533  extractLinework( f.geometry(), mpl );
534
535  ++featuresCounted;
536  if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
537  return false;
538  }
539
540  if ( renderer )
541  {
542  renderer->stopRender( *ctx.get() );
543  }
544  }
545  int timeExtract = t1.elapsed();
546
547  // resolve intersections
548
549  t2.start();
550
551  int timeNodingCall = 0;
552
553 #if 0
554  // without noding - if data are known to be noded beforehand
555 #else
557
558  try
559  {
560  t2a.start();
561  // GEOSNode_r may throw an exception
562  geos::unique_ptr allGeomGeos( QgsGeos::asGeos( allGeom ) );
563  geos::unique_ptr allNoded( GEOSNode_r( QgsGeos::getGEOSHandler(), allGeomGeos.get() ) );
564  timeNodingCall = t2a.elapsed();
565
566  QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
567
568  mpl = noded.asMultiPolyline();
569  }
570  catch ( GEOSException &e )
571  {
572  // no big deal... we will just not have nicely noded linework, potentially
573  // missing some intersections
574
575  mHasTopologyProblem = true;
576
577  QgsDebugMsg( QStringLiteral( "Tracer Noding Exception: %1" ).arg( e.what() ) );
578  }
579 #endif
580
581  int timeNoding = t2.elapsed();
582
583  t3.start();
584
585  mGraph.reset( makeGraph( mpl ) );
586
587  int timeMake = t3.elapsed();
588
589  Q_UNUSED( timeExtract )
590  Q_UNUSED( timeNoding )
591  Q_UNUSED( timeNodingCall )
592  Q_UNUSED( timeMake )
593  QgsDebugMsg( QStringLiteral( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
594  .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
595
596  return true;
597 }
598
600 {
601  invalidateGraph();
602 }
603
604 void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
605 {
606  if ( mLayers == layers )
607  return;
608
609  for ( QgsVectorLayer *layer : qgis::as_const( mLayers ) )
610  {
612  disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
613  disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
614  disconnect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
615  disconnect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
616  disconnect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
617  disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
618  }
619
620  mLayers = layers;
621
622  for ( QgsVectorLayer *layer : layers )
623  {
625  connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
626  connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
627  connect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
628  connect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
629  connect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
630  connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
631  }
632
633  invalidateGraph();
634 }
635
637 {
638  mCRS = crs;
639  mTransformContext = context;
640  invalidateGraph();
641 }
642
643 void QgsTracer::setRenderContext( const QgsRenderContext *renderContext )
644 {
645  mRenderContext.reset( new QgsRenderContext( *renderContext ) );
646  invalidateGraph();
647 }
648
649 void QgsTracer::setExtent( const QgsRectangle &extent )
650 {
651  if ( mExtent == extent )
652  return;
653
654  mExtent = extent;
655  invalidateGraph();
656 }
657
658 void QgsTracer::setOffset( double offset )
659 {
660  mOffset = offset;
661 }
662
663 void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
664 {
666  joinStyle = mOffsetJoinStyle;
667  miterLimit = mOffsetMiterLimit;
668 }
669
670 void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
671 {
673  mOffsetJoinStyle = joinStyle;
674  mOffsetMiterLimit = miterLimit;
675 }
676
678 {
679  if ( mGraph )
680  return true;
681
682  // configuration from derived class?
683  configure();
684
685  return initGraph();
686 }
687
688
690 {
691  mGraph.reset( nullptr );
692 }
693
694 void QgsTracer::onFeatureAdded( QgsFeatureId fid )
695 {
696  Q_UNUSED( fid )
697  invalidateGraph();
698 }
699
700 void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
701 {
702  Q_UNUSED( fid )
703  invalidateGraph();
704 }
705
706 void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
707 {
708  Q_UNUSED( fid )
709  Q_UNUSED( geom )
710  invalidateGraph();
711 }
712
713 void QgsTracer::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
714 {
715  Q_UNUSED( fid )
716  Q_UNUSED( idx )
717  Q_UNUSED( value )
718  invalidateGraph();
719 }
720
721 void QgsTracer::onDataChanged( )
722 {
723  invalidateGraph();
724 }
725
726 void QgsTracer::onStyleChanged( )
727 {
728  invalidateGraph();
729 }
730
731 void QgsTracer::onLayerDestroyed( QObject *obj )
732 {
733  // remove the layer before it is completely invalid (static_cast should be the safest cast)
734  mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
735  invalidateGraph();
736 }
737
738 QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
739 {
740  init(); // does nothing if the graph exists already
741  if ( !mGraph )
742  {
743  if ( error ) *error = ErrTooManyFeatures;
744  return QVector<QgsPointXY>();
745  }
746
747  QElapsedTimer t;
748  t.start();
749  int v1 = pointInGraph( *mGraph, p1 );
750  int v2 = pointInGraph( *mGraph, p2 );
751  int tPrep = t.elapsed();
752
753  if ( v1 == -1 )
754  {
755  if ( error ) *error = ErrPoint1;
756  return QVector<QgsPointXY>();
757  }
758  if ( v2 == -1 )
759  {
760  if ( error ) *error = ErrPoint2;
761  return QVector<QgsPointXY>();
762  }
763
764  QElapsedTimer t2;
765  t2.start();
766  QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
767  int tPath = t2.elapsed();
768
769  Q_UNUSED( tPrep )
770  Q_UNUSED( tPath )
771  QgsDebugMsg( QStringLiteral( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
772
773  resetGraph( *mGraph );
774
775  if ( !points.isEmpty() && mOffset != 0 )
776  {
777  QVector<QgsPointXY> pointsInput( points );
778  QgsLineString linestring( pointsInput );
779  std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
780  std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
781  if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
782  {
783  points.clear();
784  for ( int i = 0; i < ls2->numPoints(); ++i )
785  points << QgsPointXY( ls2->pointN( i ) );
786
787  // sometimes (with negative offset?) the resulting curve is reversed
788  if ( points.count() >= 2 )
789  {
790  QgsPointXY res1 = points.first(), res2 = points.last();
791  double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
792  double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
793  if ( diffReversed < diffNormal )
794  std::reverse( points.begin(), points.end() );
795  }
796  }
797  }
798
799  if ( error )
800  *error = points.isEmpty() ? ErrNoPath : ErrNone;
801
802  return points;
803 }
804
806 {
807  init(); // does nothing if the graph exists already
808  if ( !mGraph )
809  return false;
810
811  if ( point2vertex( *mGraph, pt ) != -1 )
812  return true;
813
814  int lineVertexAfter;
815  int e = point2edge( *mGraph, pt, lineVertexAfter );
816  return e != -1;
817 }
QgsPointXY::distance
double distance(double x, double y) const SIP_HOLDGIL
Returns the distance between this point and a specified x, y coordinate.
Definition: qgspointxy.h:196
qgsexpressioncontextutils.h
QgsFeatureRenderer::Filter
@ Filter
Features may be filtered, i.e. some features may not be rendered (categorized, rule based ....
Definition: qgsrenderer.h:256
makeGraph
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
Definition: qgstracer.cpp:129
QgsPointXY::y
double y
Definition: qgspointxy.h:48
QgsCoordinateTransformContext
Contains information about the context in which a coordinate transform is executed.
Definition: qgscoordinatetransformcontext.h:58
QgsSettings::value
QVariant value(const QString &key, const QVariant &defaultValue=QVariant(), Section section=NoSection) const
Returns the value for setting key.
Definition: qgssettings.cpp:174
QgsPolygonXY
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item.
Definition: qgsgeometry.h:75
QgsWkbTypes::MultiPolygon
@ MultiPolygon
Definition: qgswkbtypes.h:78
QgsTracer::findShortestPath
QVector< QgsPointXY > findShortestPath(const QgsPointXY &p1, const QgsPointXY &p2, PathError *error=nullptr)
Given two points, find the shortest path and return points on the way.
Definition: qgstracer.cpp:738
QgsGeometry::fromMultiPolylineXY
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
Definition: qgsgeometry.cpp:209
QgsTracer::init
bool init()
Build the internal data structures.
Definition: qgstracer.cpp:677
QgsGeos::geometryFromGeos
static QgsGeometry geometryFromGeos(GEOSGeometry *geos)
Creates a new QgsGeometry object, feeding in a geometry in GEOS format.
Definition: qgsgeos.cpp:150
QgsPointXY::x
Definition: qgspointxy.h:47
crs
const QgsCoordinateReferenceSystem & crs
Definition: qgswfsgetfeature.cpp:51
QgsWkbTypes::flatType
static Type flatType(Type type) SIP_HOLDGIL
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:702
QgsPolylineXY
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:51
QgsTracerGraph::V::pt
QgsPointXY pt
location of the vertex
Definition: qgstracer.cpp:112
QgsWkbTypes::LineString
@ LineString
Definition: qgswkbtypes.h:73
qgsfeatureiterator.h
QgsTracerGraph::E::otherVertex
int otherVertex(int v0) const
Definition: qgstracer.cpp:105
QgsGeometryUtils::sqrDistToLine
static double sqrDistToLine(double ptX, double ptY, double x1, double y1, double x2, double y2, double &minDistX, double &minDistY, double epsilon) SIP_HOLDGIL
Returns the squared distance between a point and a line.
Definition: qgsgeometryutils.cpp:203
QgsExpressionContextUtils::layerScope
static QgsExpressionContextScope * layerScope(const QgsMapLayer *layer)
Creates a new scope which contains variables and functions relating to a QgsMapLayer.
Definition: qgsexpressioncontextutils.cpp:265
QgsFeature::geometry
QgsGeometry geometry
Definition: qgsfeature.h:67
QgsTracer::setOffset
void setOffset(double offset)
Set offset in map units that should be applied to the traced paths returned from findShortestPath().
Definition: qgstracer.cpp:658
QgsRenderContext
Contains information about the context of a rendering operation.
Definition: qgsrendercontext.h:58
QgsTracer::ErrNoPath
@ ErrNoPath
Points are not connected in the graph.
Definition: qgstracer.h:138
point2vertex
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
Definition: qgstracer.cpp:264
QgsTracer::offset
double offset() const
Gets offset in map units that should be applied to the traced paths returned from findShortestPath().
Definition: qgstracer.h:87
QgsSettings
This class is a composition of two QSettings instances:
Definition: qgssettings.h:62
QgsVectorLayer::featureDeleted
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
QgsFeatureRequest::setSubsetOfAttributes
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
Definition: qgsfeaturerequest.cpp:185
QgsDebugMsg
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
QgsLineString
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:44
QgsTracer::layers
QList< QgsVectorLayer * > layers() const
Gets layers used for tracing.
Definition: qgstracer.h:55
QgsTracerGraph::E::coords
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
Definition: qgstracer.cpp:103
closestSegment
double closestSegment(const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon)
Definition: qgstracer.cpp:68
extractLinework
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
Definition: qgstracer.cpp:415
QgsRectangle
A rectangle specified with double values.
Definition: qgsrectangle.h:42
QgsGeometry::asMultiPolyline
QgsMultiPolylineXY asMultiPolyline() const
Returns the contents of the geometry as a multi-linestring.
Definition: qgsgeometry.cpp:1664
QgsTracer::ErrPoint2
@ ErrPoint2
End point cannot be joined to the graph.
Definition: qgstracer.h:137
QgsTracerGraph::E
Definition: qgstracer.cpp:99
QgsFeatureRequest::expressionContext
QgsExpressionContext * expressionContext()
Returns the expression context used to evaluate filter expressions.
Definition: qgsfeaturerequest.h:428
geos::unique_ptr
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:79
QgsFeatureRequest::setFilterRect
QgsFeatureRequest & setFilterRect(const QgsRectangle &rectangle)
Sets the rectangle from which features will be taken.
Definition: qgsfeaturerequest.cpp:92
QgsTracer::invalidateGraph
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:689
QgsTracer::extent
QgsRectangle extent() const
Gets extent to which graph's features will be limited (empty extent means no limit)
Definition: qgstracer.h:78
QgsTracer::setRenderContext
void setRenderContext(const QgsRenderContext *renderContext)
Sets the renderContext used for tracing only on visible features.
Definition: qgstracer.cpp:643
QgsFeatureRequest
This class wraps a request for features to a vector layer (or directly its vector data provider).
Definition: qgsfeaturerequest.h:76
QgsTracer::setOffsetParameters
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:670
QgsWkbTypes::MultiLineString
@ MultiLineString
Definition: qgswkbtypes.h:77
QgsTracerGraph::V::edges
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:114
QgsGeos::asGeos
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0)
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
Definition: qgsgeos.cpp:163
QgsGeometry::asPolygon
QgsPolygonXY asPolygon() const
Returns the contents of the geometry as a polygon.
Definition: qgsgeometry.cpp:1605
DijkstraQueueItem
std::pair< int, double > DijkstraQueueItem
Definition: qgstracer.cpp:33
QgsTracer::setDestinationCrs
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
Definition: qgstracer.cpp:636
QgsTracerGraph::joinedVertices
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
Definition: qgstracer.cpp:125
QgsTracerGraph::V
Definition: qgstracer.cpp:110
QgsMapLayer::styleChanged
void styleChanged()
Signal emitted whenever a change affects the layer's style.
QgsTracerGraph::E::weight
double weight() const
Definition: qgstracer.cpp:106
QgsVectorLayer::attributeValueChanged
void attributeValueChanged(QgsFeatureId fid, int idx, const QVariant &value)
Emitted whenever an attribute value change is done in the edit buffer.
QgsTracerGraph::e
QVector< E > e
Edges of the graph.
Definition: qgstracer.cpp:120
QgsTracer::QgsTracer
QgsTracer()
Constructor for QgsTracer.
QgsTracerGraph::QgsTracerGraph
QgsTracerGraph()=default
QgsTracer::ErrTooManyFeatures
@ ErrTooManyFeatures
Max feature count threshold was reached while reading features.
Definition: qgstracer.h:135
QgsTracer::setExtent
void setExtent(const QgsRectangle &extent)
Sets extent to which graph's features will be limited (empty extent means no limit)
Definition: qgstracer.cpp:649
QgsTracerGraph::inactiveEdges
QSet< int > inactiveEdges
Temporarily removed edges.
Definition: qgstracer.cpp:123
QgsMultiPolylineXY
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:85
comp
Definition: qgstracer.cpp:37
joinVertexToGraph
int joinVertexToGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:316
QgsTracer::offsetParameters
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Gets extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:663
qgsrenderer.h
QgsTracerGraph::E::v2
int v2
Definition: qgstracer.cpp:101
QgsFeatureRequest::setNoAttributes
QgsFeatureRequest & setNoAttributes()
Set that no attributes will be fetched.
Definition: qgsfeaturerequest.cpp:192
QgsGeometry::constGet
const QgsAbstractGeometry * constGet() const SIP_HOLDGIL
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
Definition: qgsgeometry.cpp:128
point2edge
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
Definition: qgstracer.cpp:279
QgsCoordinateReferenceSystem
This class represents a coordinate reference system (CRS).
Definition: qgscoordinatereferencesystem.h:206
QgsAbstractGeometry
Abstract base class for all geometries.
Definition: qgsabstractgeometry.h:74
QgsGeos::getGEOSHandler
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2888
QgsAbstractGeometry::segmentize
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
Definition: qgsabstractgeometry.cpp:310
qgsgeometryutils.h
qgsvectorlayer.h
QgsPointXY
A class to represent a 2D point.
Definition: qgspointxy.h:44
QgsMapLayer::dataChanged
void dataChanged()
Data of layer changed.
QgsGeometry::createGeometryEngine
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry)
Creates and returns a new geometry engine.
Definition: qgsgeometry.cpp:3636
QgsWkbTypes::isCurvedType
static bool isCurvedType(Type type) SIP_HOLDGIL
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:881
qgsgeometry.h
QgsTracer::ErrNone
@ ErrNone
No error.
Definition: qgstracer.h:134
resetGraph
void resetGraph(QgsTracerGraph &g)
Definition: qgstracer.cpp:381
QgsFeatureIterator::nextFeature
bool nextFeature(QgsFeature &f)
Definition: qgsfeatureiterator.h:374
QgsGeometry
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:124
QgsTracerGraph
Simple graph structure for shortest path search.
Definition: qgstracer.cpp:95
QgsVectorLayer
Represents a vector layer which manages a vector based data sets.
Definition: qgsvectorlayer.h:387
QgsFeature::hasGeometry
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:199
splitLinestring
void splitLinestring(const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2)
Definition: qgstracer.cpp:299
QgsVectorLayer::geometryChanged
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Emitted whenever a geometry change is done in the edit buffer.
QgsTracer::configure
virtual void configure()
Allows derived classes to setup the settings just before the tracer is initialized.
Definition: qgstracer.h:158
QgsWkbTypes::Polygon
@ Polygon
Definition: qgswkbtypes.h:74
qgssettings.h
QgsTracerGraph::v
QVector< V > v
Vertices of the graph.
Definition: qgstracer.cpp:118
QgsGeometry::asPolyline
QgsPolylineXY asPolyline() const
Returns the contents of the geometry as a polyline.
Definition: qgsgeometry.cpp:1559
qgsexception.h
QgsFeature
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:56
QgsFeatureRequest::setDestinationCrs
QgsFeatureRequest & setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the destination crs for feature's geometries.
Definition: qgsfeaturerequest.cpp:258
qgstracer.h
distance2D
double distance2D(const QgsPolylineXY &coords)
Definition: qgstracer.cpp:46
QgsTracer::~QgsTracer
~QgsTracer() override
Definition: qgstracer.cpp:599
qgslogger.h
QgsTracerGraph::E::v1
int v1
vertices that the edge connects
Definition: qgstracer.cpp:101
QgsTracer::PathError
PathError
Possible errors that may happen when calling findShortestPath()
Definition: qgstracer.h:133
QgsTracer::isPointSnapped
bool isPointSnapped(const QgsPointXY &pt)
Find out whether the point is snapped to a vertex or edge (i.e. it can be used for tracing start/stop...
Definition: qgstracer.cpp:805
shortestPath
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
Definition: qgstracer.cpp:183
QgsFeatureIterator
Wrapper for iterator of features from vector data provider or vector layer.
Definition: qgsfeatureiterator.h:265
QgsRectangle::isEmpty
bool isEmpty() const
Returns true if the rectangle is empty.
Definition: qgsrectangle.h:437
QgsTracer::setLayers
void setLayers(const QList< QgsVectorLayer * > &layers)
Sets layers used for tracing.
Definition: qgstracer.cpp:604
comp::operator()
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b)
Definition: qgstracer.cpp:38
QgsGeometry::wkbType
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
Definition: qgsgeometry.cpp:345
QgsTracer::ErrPoint1
@ ErrPoint1
Start point cannot be joined to the graph.
Definition: qgstracer.h:136
qgsgeos.h
QgsGeometry::asMultiPolygon
QgsMultiPolygonXY asMultiPolygon() const
Returns the contents of the geometry as a multi-polygon.
Definition: qgsgeometry.cpp:1717
QgsFeatureId
qint64 QgsFeatureId
64 bit feature ids negative numbers are used for uncommitted/newly added features
Definition: qgsfeatureid.h:28
pointInGraph
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:369