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