QGIS API Documentation  3.2.0-Bonn (bc43194)
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 
27 #include <queue>
28 #include <vector>
29 
30 typedef std::pair<int, double> DijkstraQueueItem; // first = vertex index, second = distance
31 
32 // utility comparator for queue items based on distance
33 struct comp
34 {
36  {
37  return a.second > b.second;
38  }
39 };
40 
41 
42 // TODO: move to geometry utils
43 double distance2D( const QgsPolylineXY &coords )
44 {
45  int np = coords.count();
46  if ( np == 0 )
47  return 0;
48 
49  double x0 = coords[0].x(), y0 = coords[0].y();
50  double x1, y1;
51  double dist = 0;
52  for ( int i = 1; i < np; ++i )
53  {
54  x1 = coords[i].x();
55  y1 = coords[i].y();
56  dist += std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
57  x0 = x1;
58  y0 = y1;
59  }
60  return dist;
61 }
62 
63 
64 // TODO: move to geometry utils
65 double closestSegment( const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon )
66 {
67  double sqrDist = std::numeric_limits<double>::max();
68  const QgsPointXY *pldata = pl.constData();
69  int plcount = pl.count();
70  double prevX = pldata[0].x(), prevY = pldata[0].y();
71  double segmentPtX, segmentPtY;
72  for ( int i = 1; i < plcount; ++i )
73  {
74  double currentX = pldata[i].x();
75  double currentY = pldata[i].y();
76  double testDist = QgsGeometryUtils::sqrDistToLine( pt.x(), pt.y(), prevX, prevY, currentX, currentY, segmentPtX, segmentPtY, epsilon );
77  if ( testDist < sqrDist )
78  {
79  sqrDist = testDist;
80  vertexAfter = i;
81  }
82  prevX = currentX;
83  prevY = currentY;
84  }
85  return sqrDist;
86 }
87 
89 
92 {
93  QgsTracerGraph() = default;
94 
95  struct E // bidirectional edge
96  {
98  int v1, v2;
100  QVector<QgsPointXY> coords;
101 
102  int otherVertex( int v0 ) const { return v1 == v0 ? v2 : v1; }
103  double weight() const { return distance2D( coords ); }
104  };
105 
106  struct V
107  {
111  QVector<int> edges;
112  };
113 
115  QVector<V> v;
117  QVector<E> e;
118 
120  QSet<int> inactiveEdges;
122  int joinedVertices{ 0 };
123 };
124 
125 
126 QgsTracerGraph *makeGraph( const QVector<QgsPolylineXY> &edges )
127 {
128  QgsTracerGraph *g = new QgsTracerGraph();
129  g->joinedVertices = 0;
130  QHash<QgsPointXY, int> point2vertex;
131 
132  Q_FOREACH ( const QgsPolylineXY &line, edges )
133  {
134  QgsPointXY p1( line[0] );
135  QgsPointXY p2( line[line.count() - 1] );
136 
137  int v1 = -1, v2 = -1;
138  // get or add vertex 1
139  if ( point2vertex.contains( p1 ) )
140  v1 = point2vertex.value( p1 );
141  else
142  {
143  v1 = g->v.count();
145  v.pt = p1;
146  g->v.append( v );
147  point2vertex[p1] = v1;
148  }
149 
150  // get or add vertex 2
151  if ( point2vertex.contains( p2 ) )
152  v2 = point2vertex.value( p2 );
153  else
154  {
155  v2 = g->v.count();
157  v.pt = p2;
158  g->v.append( v );
159  point2vertex[p2] = v2;
160  }
161 
162  // add edge
164  e.v1 = v1;
165  e.v2 = v2;
166  e.coords = line;
167  g->e.append( e );
168 
169  // link edge to vertices
170  int eIdx = g->e.count() - 1;
171  g->v[v1].edges << eIdx;
172  g->v[v2].edges << eIdx;
173  }
174 
175  return g;
176 }
177 
178 
179 QVector<QgsPointXY> shortestPath( const QgsTracerGraph &g, int v1, int v2 )
180 {
181  if ( v1 == -1 || v2 == -1 )
182  return QVector<QgsPointXY>(); // invalid input
183 
184  // priority queue to drive Dijkstra:
185  // first of the pair is vertex index, second is distance
186  std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >, comp > Q;
187 
188  // shortest distances to each vertex
189  QVector<double> D( g.v.count(), std::numeric_limits<double>::max() );
190  D[v1] = 0;
191 
192  // whether vertices have been already processed
193  QVector<bool> F( g.v.count() );
194 
195  // using which edge there is shortest path to each vertex
196  QVector<int> S( g.v.count(), -1 );
197 
198  int u = -1;
199  Q.push( DijkstraQueueItem( v1, 0 ) );
200 
201  while ( !Q.empty() )
202  {
203  u = Q.top().first; // new vertex to visit
204  Q.pop();
205 
206  if ( u == v2 )
207  break; // we can stop now, there won't be a shorter path
208 
209  if ( F[u] )
210  continue; // ignore previously added path which is actually longer
211 
212  const QgsTracerGraph::V &vu = g.v[u];
213  const int *vuEdges = vu.edges.constData();
214  int count = vu.edges.count();
215  for ( int i = 0; i < count; ++i )
216  {
217  const QgsTracerGraph::E &edge = g.e[ vuEdges[i] ];
218  int v = edge.otherVertex( u );
219  double w = edge.weight();
220  if ( !F[v] && D[u] + w < D[v] )
221  {
222  // found a shorter way to the vertex
223  D[v] = D[u] + w;
224  S[v] = vuEdges[i];
225  Q.push( DijkstraQueueItem( v, D[v] ) );
226  }
227  }
228  F[u] = true; // mark the vertex as processed (we know the fastest path to it)
229  }
230 
231  if ( u != v2 ) // there's no path to the end vertex
232  return QVector<QgsPointXY>();
233 
234  //qDebug("dist %f", D[u]);
235 
236  QVector<QgsPointXY> points;
237  QList<int> path;
238  while ( S[u] != -1 )
239  {
240  path << S[u];
241  const QgsTracerGraph::E &e = g.e[S[u]];
242  QVector<QgsPointXY> edgePoints = e.coords;
243  if ( edgePoints[0] != g.v[u].pt )
244  std::reverse( edgePoints.begin(), edgePoints.end() );
245  if ( !points.isEmpty() )
246  points.remove( points.count() - 1 ); // chop last one (will be used from next edge)
247  points << edgePoints;
248  u = e.otherVertex( u );
249  }
250 
251  std::reverse( path.begin(), path.end() );
252  //Q_FOREACH (int x, path)
253  // qDebug("e: %d", x);
254 
255  std::reverse( points.begin(), points.end() );
256  return points;
257 }
258 
259 
260 int point2vertex( const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon = 1e-6 )
261 {
262  // TODO: use spatial index
263 
264  for ( int i = 0; i < g.v.count(); ++i )
265  {
266  const QgsTracerGraph::V &v = g.v.at( i );
267  if ( v.pt == pt || ( std::fabs( v.pt.x() - pt.x() ) < epsilon && std::fabs( v.pt.y() - pt.y() ) < epsilon ) )
268  return i;
269  }
270 
271  return -1;
272 }
273 
274 
275 int point2edge( const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon = 1e-6 )
276 {
277  int vertexAfter;
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  double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
286  if ( dist == 0 )
287  {
288  lineVertexAfter = vertexAfter; //NOLINT
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  Q_FOREACH ( int eIdx, 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  Q_FOREACH ( const QgsPolylineXY &ring, geom.asPolygon() )
434  mpl << ring;
435  break;
436 
438  Q_FOREACH ( const QgsPolylineXY &linestring, geom.asMultiPolyline() )
439  mpl << linestring;
440  break;
441 
443  Q_FOREACH ( const QgsPolygonXY &polygon, geom.asMultiPolygon() )
444  Q_FOREACH ( const QgsPolylineXY &ring, polygon )
445  mpl << ring;
446  break;
447 
448  default:
449  break; // unknown type - do nothing
450  }
451 }
452 
453 // -------------
454 
455 
456 QgsTracer::QgsTracer() = default;
457 
458 bool QgsTracer::initGraph()
459 {
460  if ( mGraph )
461  return true; // already initialized
462 
463  mHasTopologyProblem = false;
464 
465  QgsFeature f;
466  QgsMultiPolylineXY mpl;
467 
468  // extract linestrings
469 
470  // TODO: use QgsPointLocator as a source for the linework
471 
472  QTime t1, t2, t2a, t3;
473 
474  t1.start();
475  int featuresCounted = 0;
476  for ( QgsVectorLayer *vl : qgis::as_const( mLayers ) )
477  {
478  QgsFeatureRequest request;
480  request.setDestinationCrs( mCRS, mTransformContext );
481  if ( !mExtent.isEmpty() )
482  request.setFilterRect( mExtent );
483 
484  QgsFeatureIterator fi = vl->getFeatures( request );
485  while ( fi.nextFeature( f ) )
486  {
487  if ( !f.hasGeometry() )
488  continue;
489 
490  extractLinework( f.geometry(), mpl );
491 
492  ++featuresCounted;
493  if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
494  return false;
495  }
496  }
497  int timeExtract = t1.elapsed();
498 
499  // resolve intersections
500 
501  t2.start();
502 
503  int timeNodingCall = 0;
504 
505 #if 0
506  // without noding - if data are known to be noded beforehand
507 #else
509 
510  try
511  {
512  t2a.start();
513  // GEOSNode_r may throw an exception
514  geos::unique_ptr allGeomGeos( QgsGeos::asGeos( allGeom ) );
515  geos::unique_ptr allNoded( GEOSNode_r( QgsGeos::getGEOSHandler(), allGeomGeos.get() ) );
516  timeNodingCall = t2a.elapsed();
517 
518  QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
519 
520  mpl = noded.asMultiPolyline();
521  }
522  catch ( GEOSException &e )
523  {
524  // no big deal... we will just not have nicely noded linework, potentially
525  // missing some intersections
526 
527  mHasTopologyProblem = true;
528 
529  QgsDebugMsg( QString( "Tracer Noding Exception: %1" ).arg( e.what() ) );
530  }
531 #endif
532 
533  int timeNoding = t2.elapsed();
534 
535  t3.start();
536 
537  mGraph.reset( makeGraph( mpl ) );
538 
539  int timeMake = t3.elapsed();
540 
541  Q_UNUSED( timeExtract );
542  Q_UNUSED( timeNoding );
543  Q_UNUSED( timeNodingCall );
544  Q_UNUSED( timeMake );
545  QgsDebugMsg( QString( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
546  .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
547  return true;
548 }
549 
551 {
552  invalidateGraph();
553 }
554 
555 void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
556 {
557  if ( mLayers == layers )
558  return;
559 
560  Q_FOREACH ( QgsVectorLayer *layer, mLayers )
561  {
562  disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
563  disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
564  disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
565  disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
566  }
567 
568  mLayers = layers;
569 
570  Q_FOREACH ( QgsVectorLayer *layer, mLayers )
571  {
572  connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
573  connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
574  connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
575  connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
576  }
577 
578  invalidateGraph();
579 }
580 
582 {
583  mCRS = crs;
584  mTransformContext = context;
585  invalidateGraph();
586 }
587 
588 void QgsTracer::setExtent( const QgsRectangle &extent )
589 {
590  if ( mExtent == extent )
591  return;
592 
593  mExtent = extent;
594  invalidateGraph();
595 }
596 
597 void QgsTracer::setOffset( double offset )
598 {
599  mOffset = offset;
600 }
601 
602 void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
603 {
604  quadSegments = mOffsetSegments;
605  joinStyle = mOffsetJoinStyle;
606  miterLimit = mOffsetMiterLimit;
607 }
608 
609 void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
610 {
611  mOffsetSegments = quadSegments;
612  mOffsetJoinStyle = joinStyle;
613  mOffsetMiterLimit = miterLimit;
614 }
615 
617 {
618  if ( mGraph )
619  return true;
620 
621  // configuration from derived class?
622  configure();
623 
624  return initGraph();
625 }
626 
627 
629 {
630  mGraph.reset( nullptr );
631 }
632 
633 void QgsTracer::onFeatureAdded( QgsFeatureId fid )
634 {
635  Q_UNUSED( fid );
636  invalidateGraph();
637 }
638 
639 void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
640 {
641  Q_UNUSED( fid );
642  invalidateGraph();
643 }
644 
645 void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
646 {
647  Q_UNUSED( fid );
648  Q_UNUSED( geom );
649  invalidateGraph();
650 }
651 
652 void QgsTracer::onLayerDestroyed( QObject *obj )
653 {
654  // remove the layer before it is completely invalid (static_cast should be the safest cast)
655  mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
656  invalidateGraph();
657 }
658 
659 QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
660 {
661  init(); // does nothing if the graph exists already
662  if ( !mGraph )
663  {
664  if ( error ) *error = ErrTooManyFeatures;
665  return QVector<QgsPointXY>();
666  }
667 
668  QTime t;
669  t.start();
670  int v1 = pointInGraph( *mGraph, p1 );
671  int v2 = pointInGraph( *mGraph, p2 );
672  int tPrep = t.elapsed();
673 
674  if ( v1 == -1 )
675  {
676  if ( error ) *error = ErrPoint1;
677  return QVector<QgsPointXY>();
678  }
679  if ( v2 == -1 )
680  {
681  if ( error ) *error = ErrPoint2;
682  return QVector<QgsPointXY>();
683  }
684 
685  QTime t2;
686  t2.start();
687  QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
688  int tPath = t2.elapsed();
689 
690  Q_UNUSED( tPrep );
691  Q_UNUSED( tPath );
692  QgsDebugMsg( QString( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
693 
694  resetGraph( *mGraph );
695 
696  if ( !points.isEmpty() && mOffset != 0 )
697  {
698  QVector<QgsPointXY> pointsInput( points );
699  QgsLineString linestring( pointsInput );
700  std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
701  std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
702  if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
703  {
704  points.clear();
705  for ( int i = 0; i < ls2->numPoints(); ++i )
706  points << QgsPointXY( ls2->pointN( i ) );
707 
708  // sometimes (with negative offset?) the resulting curve is reversed
709  if ( points.count() >= 2 )
710  {
711  QgsPointXY res1 = points.first(), res2 = points.last();
712  double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
713  double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
714  if ( diffReversed < diffNormal )
715  std::reverse( points.begin(), points.end() );
716  }
717  }
718  }
719 
720  if ( error )
721  *error = points.isEmpty() ? ErrNoPath : ErrNone;
722 
723  return points;
724 }
725 
727 {
728  init(); // does nothing if the graph exists already
729  if ( !mGraph )
730  return false;
731 
732  if ( point2vertex( *mGraph, pt ) != -1 )
733  return true;
734 
735  int lineVertexAfter;
736  int e = point2edge( *mGraph, pt, lineVertexAfter );
737  return e != -1;
738 }
QVector< E > e
Edges of the graph.
Definition: qgstracer.cpp:117
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:40
~QgsTracer() override
Definition: qgstracer.cpp:550
double weight() const
Definition: qgstracer.cpp:103
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:366
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
Definition: qgstracer.cpp:100
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
Definition: qgstracer.cpp:260
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
Definition: qgstracer.cpp:122
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
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
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:588
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item...
Definition: qgsgeometry.h:66
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
Definition: qgstracer.cpp:126
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:104
void splitLinestring(const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2)
Definition: qgstracer.cpp:296
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:62
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:190
int joinVertexToGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:313
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
std::pair< int, double > DijkstraQueueItem
Definition: qgstracer.cpp:30
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2775
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:76
QgsMultiPolylineXY asMultiPolyline() const
Returns contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list.
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:609
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
Definition: qgstracer.cpp:581
QSet< int > inactiveEdges
Temporarily removed edges.
Definition: qgstracer.cpp:120
QgsPolygonXY asPolygon() const
Returns contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list...
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:123
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:597
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
Definition: qgstracer.cpp:275
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Is emitted whenever a geometry change is done in the edit buffer.
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
Definition: qgstracer.cpp:179
void featureAdded(QgsFeatureId fid)
Emitted when a new feature has been added to the layer.
Simple graph structure for shortest path search.
Definition: qgstracer.cpp:91
Abstract base class for all geometries.
Contains information about the context in which a coordinate transform is executed.
QgsGeometry geometry() const
Returns the geometry associated with this feature.
Definition: qgsfeature.cpp:101
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:378
double closestSegment(const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon)
Definition: qgstracer.cpp:65
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:43
QgsTracer()
Constructor for QgsTracer.
QVector< V > v
Vertices of the graph.
Definition: qgstracer.cpp:115
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:42
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:111
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:606
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:628
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
Definition: qgstracer.cpp:412
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:109
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:659
qint64 QgsFeatureId
Definition: qgsfeature.h:37
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:616
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Gets extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:602
QgsPolylineXY asPolyline() const
Returns contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list...
QList< int > QgsAttributeList
Definition: qgsfield.h:27
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:726
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:102
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b)
Definition: qgstracer.cpp:35
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:427
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
QgsMultiPolygonXY asMultiPolygon() const
Returns contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty list.
void setLayers(const QList< QgsVectorLayer *> &layers)
Sets layers used for tracing.
Definition: qgstracer.cpp:555
int v1
vertices that the edge connects
Definition: qgstracer.cpp:98