QGIS API Documentation  3.0.2-Girona (307d082)
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( allGeom.exportToGeos() );
515  geos::unique_ptr allNoded( GEOSNode_r( QgsGeometry::getGEOSHandler(), allGeomGeos.get() ) );
516  timeNodingCall = t2a.elapsed();
517 
518  QgsGeometry noded;
519  noded.fromGeos( allNoded.release() );
520 
521  mpl = noded.asMultiPolyline();
522  }
523  catch ( GEOSException &e )
524  {
525  // no big deal... we will just not have nicely noded linework, potentially
526  // missing some intersections
527 
528  mHasTopologyProblem = true;
529 
530  QgsDebugMsg( QString( "Tracer Noding Exception: %1" ).arg( e.what() ) );
531  }
532 #endif
533 
534  int timeNoding = t2.elapsed();
535 
536  t3.start();
537 
538  mGraph.reset( makeGraph( mpl ) );
539 
540  int timeMake = t3.elapsed();
541 
542  Q_UNUSED( timeExtract );
543  Q_UNUSED( timeNoding );
544  Q_UNUSED( timeNodingCall );
545  Q_UNUSED( timeMake );
546  QgsDebugMsg( QString( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
547  .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
548  return true;
549 }
550 
552 {
553  invalidateGraph();
554 }
555 
556 void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
557 {
558  if ( mLayers == layers )
559  return;
560 
561  Q_FOREACH ( QgsVectorLayer *layer, mLayers )
562  {
563  disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
564  disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
565  disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
566  disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
567  }
568 
569  mLayers = layers;
570 
571  Q_FOREACH ( QgsVectorLayer *layer, mLayers )
572  {
573  connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
574  connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
575  connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
576  connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
577  }
578 
579  invalidateGraph();
580 }
581 
583 {
584  mCRS = crs;
585  mTransformContext = context;
586  invalidateGraph();
587 }
588 
589 void QgsTracer::setExtent( const QgsRectangle &extent )
590 {
591  if ( mExtent == extent )
592  return;
593 
594  mExtent = extent;
595  invalidateGraph();
596 }
597 
598 void QgsTracer::setOffset( double offset )
599 {
600  mOffset = offset;
601 }
602 
603 void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
604 {
605  quadSegments = mOffsetSegments;
606  joinStyle = mOffsetJoinStyle;
607  miterLimit = mOffsetMiterLimit;
608 }
609 
610 void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
611 {
612  mOffsetSegments = quadSegments;
613  mOffsetJoinStyle = joinStyle;
614  mOffsetMiterLimit = miterLimit;
615 }
616 
618 {
619  if ( mGraph )
620  return true;
621 
622  // configuration from derived class?
623  configure();
624 
625  return initGraph();
626 }
627 
628 
630 {
631  mGraph.reset( nullptr );
632 }
633 
634 void QgsTracer::onFeatureAdded( QgsFeatureId fid )
635 {
636  Q_UNUSED( fid );
637  invalidateGraph();
638 }
639 
640 void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
641 {
642  Q_UNUSED( fid );
643  invalidateGraph();
644 }
645 
646 void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
647 {
648  Q_UNUSED( fid );
649  Q_UNUSED( geom );
650  invalidateGraph();
651 }
652 
653 void QgsTracer::onLayerDestroyed( QObject *obj )
654 {
655  // remove the layer before it is completely invalid (static_cast should be the safest cast)
656  mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
657  invalidateGraph();
658 }
659 
660 QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
661 {
662  init(); // does nothing if the graph exists already
663  if ( !mGraph )
664  {
665  if ( error ) *error = ErrTooManyFeatures;
666  return QVector<QgsPointXY>();
667  }
668 
669  QTime t;
670  t.start();
671  int v1 = pointInGraph( *mGraph, p1 );
672  int v2 = pointInGraph( *mGraph, p2 );
673  int tPrep = t.elapsed();
674 
675  if ( v1 == -1 )
676  {
677  if ( error ) *error = ErrPoint1;
678  return QVector<QgsPointXY>();
679  }
680  if ( v2 == -1 )
681  {
682  if ( error ) *error = ErrPoint2;
683  return QVector<QgsPointXY>();
684  }
685 
686  QTime t2;
687  t2.start();
688  QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
689  int tPath = t2.elapsed();
690 
691  Q_UNUSED( tPrep );
692  Q_UNUSED( tPath );
693  QgsDebugMsg( QString( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
694 
695  resetGraph( *mGraph );
696 
697  if ( !points.isEmpty() && mOffset != 0 )
698  {
699  QVector<QgsPointXY> pointsInput( points );
700  QgsLineString linestring( pointsInput );
701  std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
702  std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
703  if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
704  {
705  points.clear();
706  for ( int i = 0; i < ls2->numPoints(); ++i )
707  points << QgsPointXY( ls2->pointN( i ) );
708 
709  // sometimes (with negative offset?) the resulting curve is reversed
710  if ( points.count() >= 2 )
711  {
712  QgsPointXY res1 = points.first(), res2 = points.last();
713  double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
714  double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
715  if ( diffReversed < diffNormal )
716  std::reverse( points.begin(), points.end() );
717  }
718  }
719  }
720 
721  if ( error )
722  *error = points.isEmpty() ? ErrNoPath : ErrNone;
723 
724  return points;
725 }
726 
728 {
729  init(); // does nothing if the graph exists already
730  if ( !mGraph )
731  return false;
732 
733  if ( point2vertex( *mGraph, pt ) != -1 )
734  return true;
735 
736  int lineVertexAfter;
737  int e = point2edge( *mGraph, pt, lineVertexAfter );
738  return e != -1;
739 }
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:39
~QgsTracer() override
Definition: qgstracer.cpp:551
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)
Set extent to which graph&#39;s features will be limited (empty extent means no limit) ...
Definition: qgstracer.cpp:589
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item...
Definition: qgsgeometry.h:73
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:111
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
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:83
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:610
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
Definition: qgstracer.cpp:582
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:74
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)...
void fromGeos(GEOSGeometry *geos)
Set the geometry, feeding in a geometry in GEOS format.
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:598
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.cpp:78
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:49
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:111
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
static bool isCurvedType(Type type)
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:606
GEOSGeometry * exportToGeos(double precision=0) const
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:629
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:41
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:660
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:617
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Get extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:603
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:727
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)
Set layers used for tracing.
Definition: qgstracer.cpp:556
int v1
vertices that the edge connects
Definition: qgstracer.cpp:98