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