QGIS API Documentation  3.8.0-Zanzibar (11aff65)
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 *
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 "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
166  // add edge
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  int vertexAfter;
282
283  for ( int i = 0; i < g.e.count(); ++i )
284  {
285  if ( g.inactiveEdges.contains( i ) )
286  continue; // ignore temporarily disabled edges
287
288  const QgsTracerGraph::E &e = g.e.at( i );
289  double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
290  if ( dist == 0 )
291  {
292  lineVertexAfter = vertexAfter; //NOLINT
293  return i;
294  }
295  }
296  return -1;
297 }
298
299
300 void splitLinestring( const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2 )
301 {
302  int count1 = lineVertexAfter;
303  int count2 = points.count() - lineVertexAfter;
304
305  for ( int i = 0; i < count1; ++i )
306  pts1 << points[i];
307  if ( points[lineVertexAfter - 1] != pt )
308  pts1 << pt; // repeat if not split exactly at that point
309
310  if ( pt != points[lineVertexAfter] )
311  pts2 << pt; // repeat if not split exactly at that point
312  for ( int i = 0; i < count2; ++i )
313  pts2 << points[i + lineVertexAfter];
314 }
315
316
318 {
319  // find edge where the point is
320  int lineVertexAfter;
321  int eIdx = point2edge( g, pt, lineVertexAfter );
322
323  //qDebug("e: %d", eIdx);
324
325  if ( eIdx == -1 )
326  return -1;
327
328  const QgsTracerGraph::E &e = g.e[eIdx];
329  QgsTracerGraph::V &v1 = g.v[e.v1];
330  QgsTracerGraph::V &v2 = g.v[e.v2];
331
332  QgsPolylineXY out1, out2;
333  splitLinestring( e.coords, pt, lineVertexAfter, out1, out2 );
334
335  int vIdx = g.v.count();
336  int e1Idx = g.e.count();
337  int e2Idx = e1Idx + 1;
338
339  // prepare new vertex and edges
340
342  v.pt = pt;
343  v.edges << e1Idx << e2Idx;
344
346  e1.v1 = e.v1;
347  e1.v2 = vIdx;
348  e1.coords = out1;
349
351  e2.v1 = vIdx;
352  e2.v2 = e.v2;
353  e2.coords = out2;
354
355  // update edge connectivity of existing vertices
356  v1.edges.replace( v1.edges.indexOf( eIdx ), e1Idx );
357  v2.edges.replace( v2.edges.indexOf( eIdx ), e2Idx );
358  g.inactiveEdges << eIdx;
359
360  // add new vertex and edges to the graph
361  g.v.append( v );
362  g.e.append( e1 );
363  g.e.append( e2 );
364  g.joinedVertices++;
365
366  return vIdx;
367 }
368
369
371 {
372  // try to use existing vertex in the graph
373  int v = point2vertex( g, pt );
374  if ( v != -1 )
375  return v;
376
377  // try to add the vertex to an edge (may fail if point is not on edge)
378  return joinVertexToGraph( g, pt );
379 }
380
381
383 {
384  // remove extra vertices and edges
385  g.v.resize( g.v.count() - g.joinedVertices );
386  g.e.resize( g.e.count() - g.joinedVertices * 2 );
387  g.joinedVertices = 0;
388
389  // fix vertices of deactivated edges
390  for ( int eIdx : qgis::as_const( g.inactiveEdges ) )
391  {
392  if ( eIdx >= g.e.count() )
393  continue;
394  const QgsTracerGraph::E &e = g.e[eIdx];
395  QgsTracerGraph::V &v1 = g.v[e.v1];
396  for ( int i = 0; i < v1.edges.count(); ++i )
397  {
398  if ( v1.edges[i] >= g.e.count() )
399  v1.edges.remove( i-- );
400  }
401  v1.edges << eIdx;
402
403  QgsTracerGraph::V &v2 = g.v[e.v2];
404  for ( int i = 0; i < v2.edges.count(); ++i )
405  {
406  if ( v2.edges[i] >= g.e.count() )
407  v2.edges.remove( i-- );
408  }
409  v2.edges << eIdx;
410  }
411
412  g.inactiveEdges.clear();
413 }
414
415
417 {
418  QgsGeometry geom = g;
419  // segmentize curved geometries - we will use noding algorithm from GEOS
420  // to find all intersections a bit later (so we need them segmentized anyway)
421  if ( QgsWkbTypes::isCurvedType( g.wkbType() ) )
422  {
423  QgsAbstractGeometry *segmentizedGeomV2 = g.constGet()->segmentize();
424  if ( !segmentizedGeomV2 )
425  return;
426
427  geom = QgsGeometry( segmentizedGeomV2 );
428  }
429
430  switch ( QgsWkbTypes::flatType( geom.wkbType() ) )
431  {
433  mpl << geom.asPolyline();
434  break;
435
437  {
438  const auto polygon = geom.asPolygon();
439  for ( const QgsPolylineXY &ring : polygon )
440  mpl << ring;
441  }
442  break;
443
445  {
446  const auto multiPolyline = geom.asMultiPolyline();
447  for ( const QgsPolylineXY &linestring : multiPolyline )
448  mpl << linestring;
449  }
450  break;
451
453  {
454  const auto multiPolygon = geom.asMultiPolygon();
455  for ( const QgsPolygonXY &polygon : multiPolygon )
456  {
457  for ( const QgsPolylineXY &ring : polygon )
458  mpl << ring;
459  }
460  }
461  break;
462
463  default:
464  break; // unknown type - do nothing
465  }
466 }
467
468 // -------------
469
470
471 QgsTracer::QgsTracer() = default;
472
473 bool QgsTracer::initGraph()
474 {
475  if ( mGraph )
476  return true; // already initialized
477
478  mHasTopologyProblem = false;
479
480  QgsFeature f;
481  QgsMultiPolylineXY mpl;
482
483  // extract linestrings
484
485  // TODO: use QgsPointLocator as a source for the linework
486
487  QTime t1, t2, t2a, t3;
488
489  t1.start();
490  int featuresCounted = 0;
491  bool enableInvisibleFeature = QgsSettings().value( QStringLiteral( "/qgis/digitizing/snap_invisible_feature" ), false ).toBool();
492  for ( const QgsVectorLayer *vl : qgis::as_const( mLayers ) )
493  {
494  QgsFeatureRequest request;
495  bool filter = false;
496  std::unique_ptr< QgsFeatureRenderer > renderer;
497  std::unique_ptr<QgsRenderContext> ctx;
498
499  if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
500  {
501  renderer.reset( vl->renderer()->clone() );
502  ctx.reset( new QgsRenderContext( *mRenderContext.get() ) );
504
505  // setup scale for scale dependent visibility (rule based)
506  renderer->startRender( *ctx.get(), vl->fields() );
507  filter = renderer->capabilities() & QgsFeatureRenderer::Filter;
508  request.setSubsetOfAttributes( renderer->usedAttributes( *ctx.get() ), vl->fields() );
509  }
510  else
511  {
512  request.setNoAttributes();
513  }
514
515  request.setDestinationCrs( mCRS, mTransformContext );
516  if ( !mExtent.isEmpty() )
517  request.setFilterRect( mExtent );
518
519  QgsFeatureIterator fi = vl->getFeatures( request );
520  while ( fi.nextFeature( f ) )
521  {
522  if ( !f.hasGeometry() )
523  continue;
524
525  if ( filter )
526  {
527  ctx->expressionContext().setFeature( f );
528  if ( !renderer->willRenderFeature( f, *ctx.get() ) )
529  {
530  continue;
531  }
532  }
533
534  extractLinework( f.geometry(), mpl );
535
536  ++featuresCounted;
537  if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
538  return false;
539  }
540
541  if ( renderer )
542  {
543  renderer->stopRender( *ctx.get() );
544  }
545  }
546  int timeExtract = t1.elapsed();
547
548  // resolve intersections
549
550  t2.start();
551
552  int timeNodingCall = 0;
553
554 #if 0
555  // without noding - if data are known to be noded beforehand
556 #else
558
559  try
560  {
561  t2a.start();
562  // GEOSNode_r may throw an exception
563  geos::unique_ptr allGeomGeos( QgsGeos::asGeos( allGeom ) );
564  geos::unique_ptr allNoded( GEOSNode_r( QgsGeos::getGEOSHandler(), allGeomGeos.get() ) );
565  timeNodingCall = t2a.elapsed();
566
567  QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
568
569  mpl = noded.asMultiPolyline();
570  }
571  catch ( GEOSException &e )
572  {
573  // no big deal... we will just not have nicely noded linework, potentially
574  // missing some intersections
575
576  mHasTopologyProblem = true;
577
578  QgsDebugMsg( QStringLiteral( "Tracer Noding Exception: %1" ).arg( e.what() ) );
579  }
580 #endif
581
582  int timeNoding = t2.elapsed();
583
584  t3.start();
585
586  mGraph.reset( makeGraph( mpl ) );
587
588  int timeMake = t3.elapsed();
589
590  Q_UNUSED( timeExtract )
591  Q_UNUSED( timeNoding )
592  Q_UNUSED( timeNodingCall )
593  Q_UNUSED( timeMake )
594  QgsDebugMsg( QStringLiteral( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
595  .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
596
597  return true;
598 }
599
601 {
602  invalidateGraph();
603 }
604
605 void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
606 {
607  if ( mLayers == layers )
608  return;
609
610  for ( QgsVectorLayer *layer : qgis::as_const( mLayers ) )
611  {
612  disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
613  disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
614  disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
615  disconnect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
616  disconnect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
617  disconnect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
618  disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
619  }
620
621  mLayers = layers;
622
623  for ( QgsVectorLayer *layer : layers )
624  {
625  connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
626  connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
627  connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
628  connect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
629  connect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
630  connect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
631  connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
632  }
633
634  invalidateGraph();
635 }
636
638 {
639  mCRS = crs;
640  mTransformContext = context;
641  invalidateGraph();
642 }
643
644 void QgsTracer::setRenderContext( const QgsRenderContext *renderContext )
645 {
646  mRenderContext.reset( new QgsRenderContext( *renderContext ) );
647  invalidateGraph();
648 }
649
650 void QgsTracer::setExtent( const QgsRectangle &extent )
651 {
652  if ( mExtent == extent )
653  return;
654
655  mExtent = extent;
656  invalidateGraph();
657 }
658
659 void QgsTracer::setOffset( double offset )
660 {
661  mOffset = offset;
662 }
663
664 void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
665 {
666  quadSegments = mOffsetSegments;
667  joinStyle = mOffsetJoinStyle;
668  miterLimit = mOffsetMiterLimit;
669 }
670
671 void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
672 {
673  mOffsetSegments = quadSegments;
674  mOffsetJoinStyle = joinStyle;
675  mOffsetMiterLimit = miterLimit;
676 }
677
679 {
680  if ( mGraph )
681  return true;
682
683  // configuration from derived class?
684  configure();
685
686  return initGraph();
687 }
688
689
691 {
692  mGraph.reset( nullptr );
693 }
694
695 void QgsTracer::onFeatureAdded( QgsFeatureId fid )
696 {
697  Q_UNUSED( fid )
698  invalidateGraph();
699 }
700
701 void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
702 {
703  Q_UNUSED( fid )
704  invalidateGraph();
705 }
706
707 void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
708 {
709  Q_UNUSED( fid )
710  Q_UNUSED( geom )
711  invalidateGraph();
712 }
713
714 void QgsTracer::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
715 {
716  Q_UNUSED( fid )
717  Q_UNUSED( idx )
718  Q_UNUSED( value )
719  invalidateGraph();
720 }
721
722 void QgsTracer::onDataChanged( )
723 {
724  invalidateGraph();
725 }
726
727 void QgsTracer::onStyleChanged( )
728 {
729  invalidateGraph();
730 }
731
732 void QgsTracer::onLayerDestroyed( QObject *obj )
733 {
734  // remove the layer before it is completely invalid (static_cast should be the safest cast)
735  mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
736  invalidateGraph();
737 }
738
739 QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
740 {
741  init(); // does nothing if the graph exists already
742  if ( !mGraph )
743  {
744  if ( error ) *error = ErrTooManyFeatures;
745  return QVector<QgsPointXY>();
746  }
747
748  QTime t;
749  t.start();
750  int v1 = pointInGraph( *mGraph, p1 );
751  int v2 = pointInGraph( *mGraph, p2 );
752  int tPrep = t.elapsed();
753
754  if ( v1 == -1 )
755  {
756  if ( error ) *error = ErrPoint1;
757  return QVector<QgsPointXY>();
758  }
759  if ( v2 == -1 )
760  {
761  if ( error ) *error = ErrPoint2;
762  return QVector<QgsPointXY>();
763  }
764
765  QTime t2;
766  t2.start();
767  QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
768  int tPath = t2.elapsed();
769
770  Q_UNUSED( tPrep )
771  Q_UNUSED( tPath )
772  QgsDebugMsg( QStringLiteral( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
773
774  resetGraph( *mGraph );
775
776  if ( !points.isEmpty() && mOffset != 0 )
777  {
778  QVector<QgsPointXY> pointsInput( points );
779  QgsLineString linestring( pointsInput );
780  std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
781  std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
782  if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
783  {
784  points.clear();
785  for ( int i = 0; i < ls2->numPoints(); ++i )
786  points << QgsPointXY( ls2->pointN( i ) );
787
788  // sometimes (with negative offset?) the resulting curve is reversed
789  if ( points.count() >= 2 )
790  {
791  QgsPointXY res1 = points.first(), res2 = points.last();
792  double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
793  double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
794  if ( diffReversed < diffNormal )
795  std::reverse( points.begin(), points.end() );
796  }
797  }
798  }
799
800  if ( error )
801  *error = points.isEmpty() ? ErrNoPath : ErrNone;
802
803  return points;
804 }
805
807 {
808  init(); // does nothing if the graph exists already
809  if ( !mGraph )
810  return false;
811
812  if ( point2vertex( *mGraph, pt ) != -1 )
813  return true;
814
815  int lineVertexAfter;
816  int e = point2edge( *mGraph, pt, lineVertexAfter );
817  return e != -1;
818 }
QVector< E > e
Edges of the graph.
Definition: qgstracer.cpp:120
QgsFeatureRequest & setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the destination crs for feature&#39;s geometries.
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
Definition: qgsrectangle.h:41
~QgsTracer() override
Definition: qgstracer.cpp:600
double weight() const
Definition: qgstracer.cpp:106
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:370
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
Definition: qgstracer.cpp:103
This class is a composition of two QSettings instances:
Definition: qgssettings.h:58
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
Definition: qgstracer.cpp:264
void setRenderContext(const QgsRenderContext *renderContext)
Sets the renderContext used for tracing only on visible features.
Definition: qgstracer.cpp:644
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
Definition: qgstracer.cpp:125
QVariant value(const QString &key, const QVariant &defaultValue=QVariant(), Section section=NoSection) const
Returns the value for setting key.
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
Features may be filtered, i.e. some features may not be rendered (categorized, rule based ...
Definition: qgsrenderer.h:244
QgsWkbTypes::Type wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
double y
Definition: qgspointxy.h:48
A class to represent a 2D point.
Definition: qgspointxy.h:43
QgsExpressionContext * expressionContext()
Returns the expression context used to evaluate filter expressions.
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
void setExtent(const QgsRectangle &extent)
Sets extent to which graph&#39;s features will be limited (empty extent means no limit) ...
Definition: qgstracer.cpp:650
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item...
Definition: qgsgeometry.h:73
qint64 QgsFeatureId
Definition: qgsfeatureid.h:25
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
Definition: qgstracer.cpp:129
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:111
void splitLinestring(const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2)
Definition: qgstracer.cpp:300
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:55
const QgsCoordinateReferenceSystem & crs
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:197
int joinVertexToGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:317
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
std::pair< int, double > DijkstraQueueItem
Definition: qgstracer.cpp:33
void styleChanged()
Signal emitted whenever a change affects the layer&#39;s style.
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2815
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:83
QgsMultiPolylineXY asMultiPolyline() const
Returns the contents of the geometry as a multi-linestring.
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:671
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
Definition: qgstracer.cpp:637
QSet< int > inactiveEdges
Temporarily removed edges.
Definition: qgstracer.cpp:123
QgsFeatureRequest & setNoAttributes()
Set that no attributes will be fetched.
QgsPolygonXY asPolygon() const
Returns the contents of the geometry as a polygon.
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:79
PathError
Possible errors that may happen when calling findShortestPath()
Definition: qgstracer.h:132
This class wraps a request for features to a vector layer (or directly its vector data provider)...
QgsFeatureRequest & setFilterRect(const QgsRectangle &rectangle)
Sets the rectangle from which features will be taken.
void setOffset(double offset)
Set offset in map units that should be applied to the traced paths returned from findShortestPath().
Definition: qgstracer.cpp:659
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
Definition: qgstracer.cpp:279
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Emitted whenever a geometry change is done in the edit buffer.
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
Definition: qgstracer.cpp:183
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.
Simple graph structure for shortest path search.
Definition: qgstracer.cpp:94
Abstract base class for all geometries.
Contains information about the context in which a coordinate transform is executed.
double distance(double x, double y) const
Returns the distance between this point and a specified x, y coordinate.
Definition: qgspointxy.h:190
double x
Definition: qgspointxy.h:47
void resetGraph(QgsTracerGraph &g)
Definition: qgstracer.cpp:382
double closestSegment(const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon)
Definition: qgstracer.cpp:68
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry)
Creates and returns a new geometry engine.
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
double distance2D(const QgsPolylineXY &coords)
Definition: qgstracer.cpp:46
QgsTracer()
Constructor for QgsTracer.
QVector< V > v
Vertices of the graph.
Definition: qgstracer.cpp:118
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:49
Contains information about the context of a rendering operation.
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:114
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:166
static bool isCurvedType(Type type)
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:609
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:690
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
Definition: qgstracer.cpp:416
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:43
QgsPointXY pt
location of the vertex
Definition: qgstracer.cpp:112
This class represents a coordinate reference system (CRS).
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:739
void dataChanged()
Data of layer changed.
static double sqrDistToLine(double ptX, double ptY, double x1, double y1, double x2, double y2, double &minDistX, double &minDistY, double epsilon)
Returns the squared distance between a point and a line.
bool init()
Build the internal data structures.
Definition: qgstracer.cpp:678
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Gets extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:664
QgsPolylineXY asPolyline() const
Returns the contents of the geometry as a polyline.
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.
bool nextFeature(QgsFeature &f)
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:806
static QgsGeometry geometryFromGeos(GEOSGeometry *geos)
Creates a new QgsGeometry object, feeding in a geometry in GEOS format.
Definition: qgsgeos.cpp:153
int otherVertex(int v0) const
Definition: qgstracer.cpp:105
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b)
Definition: qgstracer.cpp:38
Represents a vector layer which manages a vector based data sets.
static Type flatType(Type type)
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:430
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
QgsMultiPolygonXY asMultiPolygon() const
Returns the contents of the geometry as a multi-polygon.
void setLayers(const QList< QgsVectorLayer *> &layers)
Sets layers used for tracing.
Definition: qgstracer.cpp:605
int v1
vertices that the edge connects
Definition: qgstracer.cpp:101