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