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 *
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
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