QGIS API Documentation  2.18.21-Las Palmas (9fba24a)
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 #include "qgsgeometry.h"
19 #include "qgsgeometryutils.h"
20 #include "qgsgeos.h"
21 #include "qgslogger.h"
22 #include "qgsvectorlayer.h"
23 
24 #include <queue>
25 #include <vector>
26 
27 typedef std::pair<int, double> DijkstraQueueItem; // first = vertex index, second = distance
28 
29 // utility comparator for queue items based on distance
30 struct comp
31 {
33  {
34  return a.second > b.second;
35  }
36 };
37 
38 
39 // TODO: move to geometry utils
40 double distance2D( const QgsPolyline& coords )
41 {
42  int np = coords.count();
43  if ( np == 0 )
44  return 0;
45 
46  double x0 = coords[0].x(), y0 = coords[0].y();
47  double x1, y1;
48  double dist = 0;
49  for ( int i = 1; i < np; ++i )
50  {
51  x1 = coords[i].x();
52  y1 = coords[i].y();
53  dist += sqrt(( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
54  x0 = x1;
55  y0 = y1;
56  }
57  return dist;
58 }
59 
60 
61 // TODO: move to geometry utils
62 double closestSegment( const QgsPolyline& pl, const QgsPoint& pt, int& vertexAfter, double epsilon )
63 {
64  double sqrDist = std::numeric_limits<double>::max();
65  const QgsPoint* pldata = pl.constData();
66  int plcount = pl.count();
67  double prevX = pldata[0].x(), prevY = pldata[0].y();
68  double segmentPtX, segmentPtY;
69  for ( int i = 1; i < plcount; ++i )
70  {
71  double currentX = pldata[i].x();
72  double currentY = pldata[i].y();
73  double testDist = QgsGeometryUtils::sqrDistToLine( pt.x(), pt.y(), prevX, prevY, currentX, currentY, segmentPtX, segmentPtY, epsilon );
74  if ( testDist < sqrDist )
75  {
76  sqrDist = testDist;
77  vertexAfter = i;
78  }
79  prevX = currentX;
80  prevY = currentY;
81  }
82  return sqrDist;
83 }
84 
86 
89 {
90  QgsTracerGraph() : joinedVertices( 0 ) {}
91 
92  struct E // bidirectional edge
93  {
95  int v1, v2;
98 
99  int otherVertex( int v0 ) const { return v1 == v0 ? v2 : v1; }
100  double weight() const { return distance2D( coords ); }
101  };
102 
103  struct V
104  {
109  };
110 
115 
120 };
121 
122 
124 {
125  QgsTracerGraph *g = new QgsTracerGraph();
126  g->joinedVertices = 0;
128 
129  Q_FOREACH ( const QgsPolyline& line, edges )
130  {
131  QgsPoint p1( line[0] );
132  QgsPoint p2( line[line.count() - 1] );
133 
134  int v1 = -1, v2 = -1;
135  // get or add vertex 1
136  if ( point2vertex.contains( p1 ) )
137  v1 = point2vertex.value( p1 );
138  else
139  {
140  v1 = g->v.count();
142  v.pt = p1;
143  g->v.append( v );
144  point2vertex[p1] = v1;
145  }
146 
147  // get or add vertex 2
148  if ( point2vertex.contains( p2 ) )
149  v2 = point2vertex.value( p2 );
150  else
151  {
152  v2 = g->v.count();
154  v.pt = p2;
155  g->v.append( v );
156  point2vertex[p2] = v2;
157  }
158 
159  // add edge
161  e.v1 = v1;
162  e.v2 = v2;
163  e.coords = line;
164  g->e.append( e );
165 
166  // link edge to vertices
167  int eIdx = g->e.count() - 1;
168  g->v[v1].edges << eIdx;
169  g->v[v2].edges << eIdx;
170  }
171 
172  return g;
173 }
174 
175 
176 QVector<QgsPoint> shortestPath( const QgsTracerGraph& g, int v1, int v2 )
177 {
178  if ( v1 == -1 || v2 == -1 )
179  return QVector<QgsPoint>(); // invalid input
180 
181  // priority queue to drive Dijkstra:
182  // first of the pair is vertex index, second is distance
183  std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >, comp > Q;
184 
185  // shortest distances to each vertex
187  D[v1] = 0;
188 
189  // whether vertices have been already processed
190  QVector<bool> F( g.v.count() );
191 
192  // using which edge there is shortest path to each vertex
193  QVector<int> S( g.v.count(), -1 );
194 
195  int u = -1;
196  Q.push( DijkstraQueueItem( v1, 0 ) );
197 
198  while ( !Q.empty() )
199  {
200  u = Q.top().first; // new vertex to visit
201  Q.pop();
202 
203  if ( u == v2 )
204  break; // we can stop now, there won't be a shorter path
205 
206  if ( F[u] )
207  continue; // ignore previously added path which is actually longer
208 
209  const QgsTracerGraph::V& vu = g.v[u];
210  const int* vuEdges = vu.edges.constData();
211  int count = vu.edges.count();
212  for ( int i = 0; i < count; ++i )
213  {
214  const QgsTracerGraph::E& edge = g.e[ vuEdges[i] ];
215  int v = edge.otherVertex( u );
216  double w = edge.weight();
217  if ( !F[v] && D[u] + w < D[v] )
218  {
219  // found a shorter way to the vertex
220  D[v] = D[u] + w;
221  S[v] = vuEdges[i];
222  Q.push( DijkstraQueueItem( v, D[v] ) );
223  }
224  }
225  F[u] = 1; // mark the vertex as processed (we know the fastest path to it)
226  }
227 
228  if ( u != v2 ) // there's no path to the end vertex
229  return QVector<QgsPoint>();
230 
231  //qDebug("dist %f", D[u]);
232 
233  QVector<QgsPoint> points;
234  QList<int> path;
235  while ( S[u] != -1 )
236  {
237  path << S[u];
238  const QgsTracerGraph::E& e = g.e[S[u]];
239  QVector<QgsPoint> edgePoints = e.coords;
240  if ( edgePoints[0] != g.v[u].pt )
241  std::reverse( edgePoints.begin(), edgePoints.end() );
242  if ( !points.isEmpty() )
243  points.remove( points.count() - 1 ); // chop last one (will be used from next edge)
244  points << edgePoints;
245  u = e.otherVertex( u );
246  }
247 
248  std::reverse( path.begin(), path.end() );
249  //Q_FOREACH (int x, path)
250  // qDebug("e: %d", x);
251 
252  std::reverse( points.begin(), points.end() );
253  return points;
254 }
255 
256 
257 int point2vertex( const QgsTracerGraph& g, const QgsPoint& pt, double epsilon = 1e-6 )
258 {
259  // TODO: use spatial index
260 
261  for ( int i = 0; i < g.v.count(); ++i )
262  {
263  const QgsTracerGraph::V& v = g.v.at( i );
264  if ( v.pt == pt || ( fabs( v.pt.x() - pt.x() ) < epsilon && fabs( v.pt.y() - pt.y() ) < epsilon ) )
265  return i;
266  }
267 
268  return -1;
269 }
270 
271 
272 int point2edge( const QgsTracerGraph& g, const QgsPoint& pt, int& lineVertexAfter, double epsilon = 1e-6 )
273 {
274  int vertexAfter;
275 
276  for ( int i = 0; i < g.e.count(); ++i )
277  {
278  if ( g.inactiveEdges.contains( i ) )
279  continue; // ignore temporarily disabled edges
280 
281  const QgsTracerGraph::E& e = g.e.at( i );
282  double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
283  if ( dist == 0 )
284  {
285  lineVertexAfter = vertexAfter;
286  return i;
287  }
288  }
289  return -1;
290 }
291 
292 
293 void splitLinestring( const QgsPolyline& points, const QgsPoint& pt, int lineVertexAfter, QgsPolyline& pts1, QgsPolyline& pts2 )
294 {
295  int count1 = lineVertexAfter;
296  int count2 = points.count() - lineVertexAfter;
297 
298  for ( int i = 0; i < count1; ++i )
299  pts1 << points[i];
300  if ( points[lineVertexAfter-1] != pt )
301  pts1 << pt; // repeat if not split exactly at that point
302 
303  if ( pt != points[lineVertexAfter] )
304  pts2 << pt; // repeat if not split exactly at that point
305  for ( int i = 0; i < count2; ++i )
306  pts2 << points[i + lineVertexAfter];
307 }
308 
309 
311 {
312  // find edge where the point is
313  int lineVertexAfter;
314  int eIdx = point2edge( g, pt, lineVertexAfter );
315 
316  //qDebug("e: %d", eIdx);
317 
318  if ( eIdx == -1 )
319  return -1;
320 
321  const QgsTracerGraph::E& e = g.e[eIdx];
322  QgsTracerGraph::V& v1 = g.v[e.v1];
323  QgsTracerGraph::V& v2 = g.v[e.v2];
324 
325  QgsPolyline out1, out2;
326  splitLinestring( e.coords, pt, lineVertexAfter, out1, out2 );
327 
328  int vIdx = g.v.count();
329  int e1Idx = g.e.count();
330  int e2Idx = e1Idx + 1;
331 
332  // prepare new vertex and edges
333 
335  v.pt = pt;
336  v.edges << e1Idx << e2Idx;
337 
339  e1.v1 = e.v1;
340  e1.v2 = vIdx;
341  e1.coords = out1;
342 
344  e2.v1 = vIdx;
345  e2.v2 = e.v2;
346  e2.coords = out2;
347 
348  // update edge connectivity of existing vertices
349  v1.edges.replace( v1.edges.indexOf( eIdx ), e1Idx );
350  v2.edges.replace( v2.edges.indexOf( eIdx ), e2Idx );
351  g.inactiveEdges << eIdx;
352 
353  // add new vertex and edges to the graph
354  g.v.append( v );
355  g.e.append( e1 );
356  g.e.append( e2 );
357  g.joinedVertices++;
358 
359  return vIdx;
360 }
361 
362 
364 {
365  // try to use existing vertex in the graph
366  int v = point2vertex( g, pt );
367  if ( v != -1 )
368  return v;
369 
370  // try to add the vertex to an edge (may fail if point is not on edge)
371  return joinVertexToGraph( g, pt );
372 }
373 
374 
376 {
377  // remove extra vertices and edges
378  g.v.resize( g.v.count() - g.joinedVertices );
379  g.e.resize( g.e.count() - g.joinedVertices * 2 );
380  g.joinedVertices = 0;
381 
382  // fix vertices of deactivated edges
383  Q_FOREACH ( int eIdx, g.inactiveEdges )
384  {
385  if ( eIdx >= g.e.count() )
386  continue;
387  const QgsTracerGraph::E& e = g.e[eIdx];
388  QgsTracerGraph::V& v1 = g.v[e.v1];
389  for ( int i = 0; i < v1.edges.count(); ++i )
390  {
391  if ( v1.edges[i] >= g.e.count() )
392  v1.edges.remove( i-- );
393  }
394  v1.edges << eIdx;
395 
396  QgsTracerGraph::V& v2 = g.v[e.v2];
397  for ( int i = 0; i < v2.edges.count(); ++i )
398  {
399  if ( v2.edges[i] >= g.e.count() )
400  v2.edges.remove( i-- );
401  }
402  v2.edges << eIdx;
403  }
404 
405  g.inactiveEdges.clear();
406 }
407 
408 
410 {
411  // segmentize curved geometries - we will use noding algorithm from GEOS
412  // to find all intersections a bit later (so we need them segmentized anyway)
413  QScopedPointer<QgsGeometry> segmentizedGeom;
414  if ( QgsWKBTypes::isCurvedType( g->geometry()->wkbType() ) )
415  {
416  QgsAbstractGeometryV2* segmentizedGeomV2 = g->geometry()->segmentize();
417  if ( !segmentizedGeomV2 )
418  return;
419 
420  // temporarily replace the original geometry by our segmentized one
421  segmentizedGeom.reset( new QgsGeometry( segmentizedGeomV2 ) );
422  g = segmentizedGeom.data();
423  }
424 
425  switch ( QgsWKBTypes::flatType( g->geometry()->wkbType() ) )
426  {
428  mpl << g->asPolyline();
429  break;
430 
432  Q_FOREACH ( const QgsPolyline& ring, g->asPolygon() )
433  mpl << ring;
434  break;
435 
437  Q_FOREACH ( const QgsPolyline& linestring, g->asMultiPolyline() )
438  mpl << linestring;
439  break;
440 
442  Q_FOREACH ( const QgsPolygon& polygon, g->asMultiPolygon() )
443  Q_FOREACH ( const QgsPolyline& ring, polygon )
444  mpl << ring;
445  break;
446 
447  default:
448  break; // unknown type - do nothing
449  }
450 }
451 
452 // -------------
453 
454 
456  : mGraph( 0 )
457  , mReprojectionEnabled( false )
458  , mMaxFeatureCount( 0 )
459  , mHasTopologyProblem( false )
460 {
461 }
462 
463 
464 bool QgsTracer::initGraph()
465 {
466  if ( mGraph )
467  return true; // already initialized
468 
469  mHasTopologyProblem = false;
470 
471  QgsFeature f;
472  QgsMultiPolyline mpl;
473 
474  // extract linestrings
475 
476  // TODO: use QgsPointLocator as a source for the linework
477 
478  QTime t1, t2, t2a, t3;
479 
480  t1.start();
481  int featuresCounted = 0;
482  Q_FOREACH ( QgsVectorLayer* vl, mLayers )
483  {
484  QgsCoordinateTransform ct( vl->crs(), mCRS );
485 
486  QgsFeatureRequest request;
488  if ( !mExtent.isEmpty() )
489  request.setFilterRect( mReprojectionEnabled ? ct.transformBoundingBox( mExtent, QgsCoordinateTransform::ReverseTransform ) : mExtent );
490 
491  QgsFeatureIterator fi = vl->getFeatures( request );
492  while ( fi.nextFeature( f ) )
493  {
494  if ( !f.constGeometry() )
495  continue;
496 
497  if ( mReprojectionEnabled && !ct.isShortCircuited() )
498  {
499  try
500  {
501  f.geometry()->transform( ct );
502  }
503  catch ( QgsCsException& )
504  {
505  continue; // ignore if the transform failed
506  }
507  }
508 
509  extractLinework( f.constGeometry(), mpl );
510 
511  ++featuresCounted;
512  if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
513  return false;
514  }
515  }
516  int timeExtract = t1.elapsed();
517 
518  // resolve intersections
519 
520  t2.start();
521 
522  int timeNodingCall = 0;
523 
524 #if 0
525  // without noding - if data are known to be noded beforehand
526 #else
528 
529  try
530  {
531  t2a.start();
532  // GEOSNode_r may throw an exception
533  GEOSGeometry* allNoded = GEOSNode_r( QgsGeometry::getGEOSHandler(), allGeom->asGeos() );
534  timeNodingCall = t2a.elapsed();
535 
536  QgsGeometry* noded = new QgsGeometry;
537  noded->fromGeos( allNoded );
538  delete allGeom;
539 
540  mpl = noded->asMultiPolyline();
541 
542  delete noded;
543  }
544  catch ( GEOSException &e )
545  {
546  // no big deal... we will just not have nicely noded linework, potentially
547  // missing some intersections
548 
549  mHasTopologyProblem = true;
550 
551  QgsDebugMsg( "Tracer Noding Exception: " + e.what() );
552  }
553 #endif
554 
555  int timeNoding = t2.elapsed();
556 
557  t3.start();
558 
559  mGraph = makeGraph( mpl );
560 
561  int timeMake = t3.elapsed();
562 
563  Q_UNUSED( timeExtract );
564  Q_UNUSED( timeNoding );
565  Q_UNUSED( timeNodingCall );
566  Q_UNUSED( timeMake );
567  QgsDebugMsg( QString( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
568  .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
569  return true;
570 }
571 
573 {
574  invalidateGraph();
575 }
576 
578 {
579  if ( mLayers == layers )
580  return;
581 
582  Q_FOREACH ( QgsVectorLayer* layer, mLayers )
583  {
584  disconnect( layer, SIGNAL( featureAdded( QgsFeatureId ) ), this, SLOT( onFeatureAdded( QgsFeatureId ) ) );
585  disconnect( layer, SIGNAL( featureDeleted( QgsFeatureId ) ), this, SLOT( onFeatureDeleted( QgsFeatureId ) ) );
586  disconnect( layer, SIGNAL( geometryChanged( QgsFeatureId, QgsGeometry& ) ), this, SLOT( onGeometryChanged( QgsFeatureId, QgsGeometry& ) ) );
587  disconnect( layer, SIGNAL( destroyed( QObject* ) ), this, SLOT( onLayerDestroyed( QObject* ) ) );
588  }
589 
590  mLayers = layers;
591 
592  Q_FOREACH ( QgsVectorLayer* layer, mLayers )
593  {
594  connect( layer, SIGNAL( featureAdded( QgsFeatureId ) ), this, SLOT( onFeatureAdded( QgsFeatureId ) ) );
595  connect( layer, SIGNAL( featureDeleted( QgsFeatureId ) ), this, SLOT( onFeatureDeleted( QgsFeatureId ) ) );
596  connect( layer, SIGNAL( geometryChanged( QgsFeatureId, QgsGeometry& ) ), this, SLOT( onGeometryChanged( QgsFeatureId, QgsGeometry& ) ) );
597  connect( layer, SIGNAL( destroyed( QObject* ) ), this, SLOT( onLayerDestroyed( QObject* ) ) );
598  }
599 
600  invalidateGraph();
601 }
602 
604 {
605  if ( mReprojectionEnabled == enabled )
606  return;
607 
608  mReprojectionEnabled = enabled;
609  invalidateGraph();
610 }
611 
613 {
614  if ( mCRS == crs )
615  return;
616 
617  mCRS = crs;
618  invalidateGraph();
619 }
620 
622 {
623  if ( mExtent == extent )
624  return;
625 
626  mExtent = extent;
627  invalidateGraph();
628 }
629 
631 {
632  if ( mGraph )
633  return true;
634 
635  // configuration from derived class?
636  configure();
637 
638  return initGraph();
639 }
640 
641 
643 {
644  delete mGraph;
645  mGraph = 0;
646 }
647 
648 void QgsTracer::onFeatureAdded( QgsFeatureId fid )
649 {
650  Q_UNUSED( fid );
651  invalidateGraph();
652 }
653 
654 void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
655 {
656  Q_UNUSED( fid );
657  invalidateGraph();
658 }
659 
660 void QgsTracer::onGeometryChanged( QgsFeatureId fid, QgsGeometry& geom )
661 {
662  Q_UNUSED( fid );
663  Q_UNUSED( geom );
664  invalidateGraph();
665 }
666 
667 void QgsTracer::onLayerDestroyed( QObject* obj )
668 {
669  // remove the layer before it is completely invalid (static_cast should be the safest cast)
670  mLayers.removeAll( static_cast<QgsVectorLayer*>( obj ) );
671  invalidateGraph();
672 }
673 
675 {
676  init(); // does nothing if the graph exists already
677  if ( !mGraph )
678  {
679  if ( error ) *error = ErrTooManyFeatures;
680  return QVector<QgsPoint>();
681  }
682 
683  QTime t;
684  t.start();
685  int v1 = pointInGraph( *mGraph, p1 );
686  int v2 = pointInGraph( *mGraph, p2 );
687  int tPrep = t.elapsed();
688 
689  if ( v1 == -1 )
690  {
691  if ( error ) *error = ErrPoint1;
692  return QVector<QgsPoint>();
693  }
694  if ( v2 == -1 )
695  {
696  if ( error ) *error = ErrPoint2;
697  return QVector<QgsPoint>();
698  }
699 
700  QTime t2;
701  t2.start();
702  QgsPolyline points = shortestPath( *mGraph, v1, v2 );
703  int tPath = t2.elapsed();
704 
705  Q_UNUSED( tPrep );
706  Q_UNUSED( tPath );
707  QgsDebugMsg( QString( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
708 
709  resetGraph( *mGraph );
710 
711  if ( error )
712  *error = points.isEmpty() ? ErrNoPath : ErrNone;
713 
714  return points;
715 }
716 
718 {
719  init(); // does nothing if the graph exists already
720  if ( !mGraph )
721  return false;
722 
723  if ( point2vertex( *mGraph, pt ) != -1 )
724  return true;
725 
726  int lineVertexAfter;
727  int e = point2edge( *mGraph, pt, lineVertexAfter );
728  return e != -1;
729 }
QgsPolygon asPolygon() const
Return contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list...
QVector< E > e
Edges of the graph.
Definition: qgstracer.cpp:114
Wrapper for iterator of features from vector data provider or vector layer.
QgsMultiPolyline asMultiPolyline() const
Return contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list.
A rectangle specified with double values.
Definition: qgsrectangle.h:35
double weight() const
Definition: qgstracer.cpp:100
QVector< QgsPoint > shortestPath(const QgsTracerGraph &g, int v1, int v2)
Definition: qgstracer.cpp:176
iterator begin()
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
Definition: qgstracer.cpp:119
virtual void configure()
Allows derived classes to setup the settings just before the tracer is initialized.
Definition: qgstracer.h:106
#define QgsDebugMsg(str)
Definition: qgslogger.h:33
int indexOf(const T &value, int from) const
QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest())
Query the provider for features specified in request.
int pointInGraph(QgsTracerGraph &g, const QgsPoint &pt)
Definition: qgstracer.cpp:363
const QgsCoordinateReferenceSystem & crs() const
Returns layer&#39;s spatial reference system.
void setExtent(const QgsRectangle &extent)
Set extent to which graph&#39;s features will be limited (empty extent means no limit) ...
Definition: qgstracer.cpp:621
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
int point2vertex(const QgsTracerGraph &g, const QgsPoint &pt, double epsilon=1e-6)
Definition: qgstracer.cpp:257
Abstract base class for all geometries.
QList< QgsVectorLayer * > layers() const
Get layers used for tracing.
Definition: qgstracer.h:46
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:76
QgsTracerGraph * makeGraph(const QVector< QgsPolyline > &edges)
Definition: qgstracer.cpp:123
const QgsGeometry * constGeometry() const
Gets a const pointer to the geometry object associated with this feature.
Definition: qgsfeature.cpp:82
T & first()
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
Definition: qgsfeature.h:187
double closestSegment(const QgsPolyline &pl, const QgsPoint &pt, int &vertexAfter, double epsilon)
Definition: qgstracer.cpp:62
bool disconnect(const QObject *sender, const char *signal, const QObject *receiver, const char *method)
std::pair< int, double > DijkstraQueueItem
Definition: qgstracer.cpp:27
QgsPolyline asPolyline() const
Return contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list...
double y() const
Get the y value of the point.
Definition: qgspoint.h:193
void reset(T *other)
double ANALYSIS_EXPORT max(double x, double y)
Returns the maximum of two doubles or the first argument if both are equal.
int elapsed() const
bool isEmpty() const
test if rectangle is empty.
QSet< int > inactiveEdges
Temporarily removed edges.
Definition: qgstracer.cpp:117
Max feature count threshold was reached while reading features.
Definition: qgstracer.h:88
static bool isCurvedType(Type type)
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:531
int removeAll(const T &value)
void remove(int i)
virtual QgsAbstractGeometryV2 * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
PathError
Possible errors that may happen when calling findShortestPath()
Definition: qgstracer.h:85
This class wraps a request for features to a vector layer (or directly its vector data provider)...
QList< int > QgsAttributeList
void fromGeos(GEOSGeometry *geos)
Set the geometry, feeding in a geometry in GEOS format.
void splitLinestring(const QgsPolyline &points, const QgsPoint &pt, int lineVertexAfter, QgsPolyline &pts1, QgsPolyline &pts2)
Definition: qgstracer.cpp:293
const T * constData() const
Simple graph structure for shortest path search.
Definition: qgstracer.cpp:88
A class to represent a point.
Definition: qgspoint.h:117
T * data() const
iterator end()
const T value(const Key &key) const
void resetGraph(QgsTracerGraph &g)
Definition: qgstracer.cpp:375
QgsGeometry * geometry()
Get the geometry object associated with this feature.
Definition: qgsfeature.cpp:76
bool contains(const T &value) const
static QgsGeometry * fromMultiPolyline(const QgsMultiPolyline &multiline)
Creates a new geometry from a QgsMultiPolyline object.
End point cannot be joined to the graph.
Definition: qgstracer.h:90
QVector< V > v
Vertices of the graph.
Definition: qgstracer.cpp:112
void setCrsTransformEnabled(bool enabled)
Set whether to do reprojection to destination CRS.
Definition: qgstracer.cpp:603
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:108
QgsAbstractGeometryV2 * geometry() const
Returns the underlying geometry store.
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
bool isEmpty() const
QgsWKBTypes::Type wkbType() const
Returns the WKB type of the geometry.
QgsMultiPolygon asMultiPolygon() const
Return contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty ...
QgsPoint pt
location of the vertex
Definition: qgstracer.cpp:106
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:642
const GEOSGeometry * asGeos(double precision=0) const
Returns a geos geometry.
Class for storing a coordinate reference system (CRS)
int count(const T &value) const
bool isPointSnapped(const QgsPoint &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:717
QgsRectangle extent() const
Get extent to which graph&#39;s features will be limited (empty extent means no limit) ...
Definition: qgstracer.h:61
Class for doing transforms between two map coordinate systems.
int transform(const QgsCoordinateTransform &ct)
Transform this geometry as described by CoordinateTransform ct.
qint64 QgsFeatureId
Definition: qgsfeature.h:31
No error.
Definition: qgstracer.h:87
void replace(int i, const T &value)
QVector< QgsPoint > coords
coordinates of the edge (including endpoints)
Definition: qgstracer.cpp:97
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:630
void start()
static Type flatType(Type type)
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:366
bool contains(const Key &key) const
Custom exception class for Coordinate Reference System related exceptions.
double distance2D(const QgsPolyline &coords)
Definition: qgstracer.cpp:40
bool nextFeature(QgsFeature &f)
void clear()
int otherVertex(int v0) const
Definition: qgstracer.cpp:99
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b)
Definition: qgstracer.cpp:32
bool connect(const QObject *sender, const char *signal, const QObject *receiver, const char *method, Qt::ConnectionType type)
Represents a vector layer which manages a vector based data sets.
bool empty() const
iterator end()
void extractLinework(const QgsGeometry *g, QgsMultiPolyline &mpl)
Definition: qgstracer.cpp:409
int point2edge(const QgsTracerGraph &g, const QgsPoint &pt, int &lineVertexAfter, double epsilon=1e-6)
Definition: qgstracer.cpp:272
iterator begin()
void setLayers(const QList< QgsVectorLayer *> &layers)
Set layers used for tracing.
Definition: qgstracer.cpp:577
void destroyed(QObject *obj)
QVector< QgsPoint > findShortestPath(const QgsPoint &p1, const QgsPoint &p2, PathError *error=nullptr)
Given two points, find the shortest path and return points on the way.
Definition: qgstracer.cpp:674
QgsFeatureRequest & setFilterRect(const QgsRectangle &rect)
Set rectangle from which features will be taken.
Points are not connected in the graph.
Definition: qgstracer.h:91
double x() const
Get the x value of the point.
Definition: qgspoint.h:185
Start point cannot be joined to the graph.
Definition: qgstracer.h:89
int v1
vertices that the edge connects
Definition: qgstracer.cpp:95
int joinVertexToGraph(QgsTracerGraph &g, const QgsPoint &pt)
Definition: qgstracer.cpp:310
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs)
Set CRS used for tracing.
Definition: qgstracer.cpp:612