QGIS API Documentation 3.28.0-Firenze (ed3ad0430f)
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#include "qgsrenderer.h"
29#include "qgsrendercontext.h"
30
31#include <queue>
32#include <vector>
33
34typedef std::pair<int, double> DijkstraQueueItem; // first = vertex index, second = distance
35
36// utility comparator for queue items based on distance
37struct comp
38{
40 {
41 return a.second > b.second;
42 }
43};
44
45
46// TODO: move to geometry utils
47double distance2D( const QgsPolylineXY &coords )
48{
49 int np = coords.count();
50 if ( np == 0 )
51 return 0;
52
53 double x0 = coords[0].x(), y0 = coords[0].y();
54 double x1, y1;
55 double dist = 0;
56 for ( int i = 1; i < np; ++i )
57 {
58 x1 = coords[i].x();
59 y1 = coords[i].y();
60 dist += std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
61 x0 = x1;
62 y0 = y1;
63 }
64 return dist;
65}
66
67
68// TODO: move to geometry utils
69double closestSegment( const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon )
70{
71 double sqrDist = std::numeric_limits<double>::max();
72 const QgsPointXY *pldata = pl.constData();
73 int plcount = pl.count();
74 double prevX = pldata[0].x(), prevY = pldata[0].y();
75 double segmentPtX, segmentPtY;
76 for ( int i = 1; i < plcount; ++i )
77 {
78 double currentX = pldata[i].x();
79 double currentY = pldata[i].y();
80 double testDist = QgsGeometryUtils::sqrDistToLine( pt.x(), pt.y(), prevX, prevY, currentX, currentY, segmentPtX, segmentPtY, epsilon );
81 if ( testDist < sqrDist )
82 {
83 sqrDist = testDist;
84 vertexAfter = i;
85 }
86 prevX = currentX;
87 prevY = currentY;
88 }
89 return sqrDist;
90}
91
93
96{
97 QgsTracerGraph() = default;
98
99 struct E // bidirectional edge
100 {
102 int v1, v2;
104 QVector<QgsPointXY> coords;
105
106 int otherVertex( int v0 ) const { return v1 == v0 ? v2 : v1; }
107 double weight() const { return distance2D( coords ); }
108 };
109
110 struct V
111 {
115 QVector<int> edges;
116 };
117
119 QVector<V> v;
121 QVector<E> e;
122
124 QSet<int> inactiveEdges;
127};
128
129
130QgsTracerGraph *makeGraph( const QVector<QgsPolylineXY> &edges )
131{
133 g->joinedVertices = 0;
134 QHash<QgsPointXY, int> point2vertex;
135
136 const auto constEdges = edges;
137 for ( const QgsPolylineXY &line : constEdges )
138 {
139 QgsPointXY p1( line[0] );
140 QgsPointXY p2( line[line.count() - 1] );
141
142 int v1 = -1, v2 = -1;
143 // get or add vertex 1
144 if ( point2vertex.contains( p1 ) )
145 v1 = point2vertex.value( p1 );
146 else
147 {
148 v1 = g->v.count();
150 v.pt = p1;
151 g->v.append( v );
152 point2vertex[p1] = v1;
153 }
154
155 // get or add vertex 2
156 if ( point2vertex.contains( p2 ) )
157 v2 = point2vertex.value( p2 );
158 else
159 {
160 v2 = g->v.count();
162 v.pt = p2;
163 g->v.append( v );
164 point2vertex[p2] = v2;
165 }
166
167 // add edge
169 e.v1 = v1;
170 e.v2 = v2;
171 e.coords = line;
172 g->e.append( e );
173
174 // link edge to vertices
175 int eIdx = g->e.count() - 1;
176 g->v[v1].edges << eIdx;
177 g->v[v2].edges << eIdx;
178 }
179
180 return g;
181}
182
183
184QVector<QgsPointXY> shortestPath( const QgsTracerGraph &g, int v1, int v2 )
185{
186 if ( v1 == -1 || v2 == -1 )
187 return QVector<QgsPointXY>(); // invalid input
188
189 // priority queue to drive Dijkstra:
190 // first of the pair is vertex index, second is distance
191 std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >, comp > Q;
192
193 // shortest distances to each vertex
194 QVector<double> D( g.v.count(), std::numeric_limits<double>::max() );
195 D[v1] = 0;
196
197 // whether vertices have been already processed
198 QVector<bool> F( g.v.count() );
199
200 // using which edge there is shortest path to each vertex
201 QVector<int> S( g.v.count(), -1 );
202
203 int u = -1;
204 Q.push( DijkstraQueueItem( v1, 0 ) );
205
206 while ( !Q.empty() )
207 {
208 u = Q.top().first; // new vertex to visit
209 Q.pop();
210
211 if ( u == v2 )
212 break; // we can stop now, there won't be a shorter path
213
214 if ( F[u] )
215 continue; // ignore previously added path which is actually longer
216
217 const QgsTracerGraph::V &vu = g.v[u];
218 const int *vuEdges = vu.edges.constData();
219 int count = vu.edges.count();
220 for ( int i = 0; i < count; ++i )
221 {
222 const QgsTracerGraph::E &edge = g.e[ vuEdges[i] ];
223 int v = edge.otherVertex( u );
224 double w = edge.weight();
225 if ( !F[v] && D[u] + w < D[v] )
226 {
227 // found a shorter way to the vertex
228 D[v] = D[u] + w;
229 S[v] = vuEdges[i];
230 Q.push( DijkstraQueueItem( v, D[v] ) );
231 }
232 }
233 F[u] = true; // mark the vertex as processed (we know the fastest path to it)
234 }
235
236 if ( u != v2 ) // there's no path to the end vertex
237 return QVector<QgsPointXY>();
238
239 //qDebug("dist %f", D[u]);
240
241 QVector<QgsPointXY> points;
242 QList<int> path;
243 while ( S[u] != -1 )
244 {
245 path << S[u];
246 const QgsTracerGraph::E &e = g.e[S[u]];
247 QVector<QgsPointXY> edgePoints = e.coords;
248 if ( edgePoints[0] != g.v[u].pt )
249 std::reverse( edgePoints.begin(), edgePoints.end() );
250 if ( !points.isEmpty() )
251 points.remove( points.count() - 1 ); // chop last one (will be used from next edge)
252 points << edgePoints;
253 u = e.otherVertex( u );
254 }
255
256 std::reverse( path.begin(), path.end() );
257 std::reverse( points.begin(), points.end() );
258 return points;
259}
260
261
262int point2vertex( const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon = 1e-6 )
263{
264 // TODO: use spatial index
265
266 for ( int i = 0; i < g.v.count(); ++i )
267 {
268 const QgsTracerGraph::V &v = g.v.at( i );
269 if ( v.pt == pt || ( std::fabs( v.pt.x() - pt.x() ) < epsilon && std::fabs( v.pt.y() - pt.y() ) < epsilon ) )
270 return i;
271 }
272
273 return -1;
274}
275
276
277int point2edge( const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon = 1e-6 )
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 int vertexAfter = -1;
286 double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
287 if ( dist == 0 )
288 {
289 lineVertexAfter = vertexAfter;
290 return i;
291 }
292 }
293 return -1;
294}
295
296
297void splitLinestring( const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2 )
298{
299 int count1 = lineVertexAfter;
300 int count2 = points.count() - lineVertexAfter;
301
302 for ( int i = 0; i < count1; ++i )
303 pts1 << points[i];
304 if ( points[lineVertexAfter - 1] != pt )
305 pts1 << pt; // repeat if not split exactly at that point
306
307 if ( pt != points[lineVertexAfter] )
308 pts2 << pt; // repeat if not split exactly at that point
309 for ( int i = 0; i < count2; ++i )
310 pts2 << points[i + lineVertexAfter];
311}
312
313
315{
316 // find edge where the point is
317 int lineVertexAfter;
318 int eIdx = point2edge( g, pt, lineVertexAfter );
319
320 //qDebug("e: %d", eIdx);
321
322 if ( eIdx == -1 )
323 return -1;
324
325 const QgsTracerGraph::E &e = g.e[eIdx];
326 QgsTracerGraph::V &v1 = g.v[e.v1];
327 QgsTracerGraph::V &v2 = g.v[e.v2];
328
329 QgsPolylineXY out1, out2;
330 splitLinestring( e.coords, pt, lineVertexAfter, out1, out2 );
331
332 int vIdx = g.v.count();
333 int e1Idx = g.e.count();
334 int e2Idx = e1Idx + 1;
335
336 // prepare new vertex and edges
337
339 v.pt = pt;
340 v.edges << e1Idx << e2Idx;
341
343 e1.v1 = e.v1;
344 e1.v2 = vIdx;
345 e1.coords = out1;
346
348 e2.v1 = vIdx;
349 e2.v2 = e.v2;
350 e2.coords = out2;
351
352 // update edge connectivity of existing vertices
353 v1.edges.replace( v1.edges.indexOf( eIdx ), e1Idx );
354 v2.edges.replace( v2.edges.indexOf( eIdx ), e2Idx );
355 g.inactiveEdges << eIdx;
356
357 // add new vertex and edges to the graph
358 g.v.append( v );
359 g.e.append( e1 );
360 g.e.append( e2 );
361 g.joinedVertices++;
362
363 return vIdx;
364}
365
366
368{
369 // try to use existing vertex in the graph
370 int v = point2vertex( g, pt );
371 if ( v != -1 )
372 return v;
373
374 // try to add the vertex to an edge (may fail if point is not on edge)
375 return joinVertexToGraph( g, pt );
376}
377
378
380{
381 // remove extra vertices and edges
382 g.v.resize( g.v.count() - g.joinedVertices );
383 g.e.resize( g.e.count() - g.joinedVertices * 2 );
384 g.joinedVertices = 0;
385
386 // fix vertices of deactivated edges
387 for ( int eIdx : std::as_const( g.inactiveEdges ) )
388 {
389 if ( eIdx >= g.e.count() )
390 continue;
391 const QgsTracerGraph::E &e = g.e[eIdx];
392 QgsTracerGraph::V &v1 = g.v[e.v1];
393 for ( int i = 0; i < v1.edges.count(); ++i )
394 {
395 if ( v1.edges[i] >= g.e.count() )
396 v1.edges.remove( i-- );
397 }
398 v1.edges << eIdx;
399
400 QgsTracerGraph::V &v2 = g.v[e.v2];
401 for ( int i = 0; i < v2.edges.count(); ++i )
402 {
403 if ( v2.edges[i] >= g.e.count() )
404 v2.edges.remove( i-- );
405 }
406 v2.edges << eIdx;
407 }
408
409 g.inactiveEdges.clear();
410}
411
412
414{
415 QgsGeometry geom = g;
416 // segmentize curved geometries - we will use noding algorithm from GEOS
417 // to find all intersections a bit later (so we need them segmentized anyway)
419 {
420 QgsAbstractGeometry *segmentizedGeomV2 = g.constGet()->segmentize();
421 if ( !segmentizedGeomV2 )
422 return;
423
424 geom = QgsGeometry( segmentizedGeomV2 );
425 }
426
427 switch ( QgsWkbTypes::flatType( geom.wkbType() ) )
428 {
430 mpl << geom.asPolyline();
431 break;
432
434 {
435 const auto polygon = geom.asPolygon();
436 for ( const QgsPolylineXY &ring : polygon )
437 mpl << ring;
438 }
439 break;
440
442 {
443 const auto multiPolyline = geom.asMultiPolyline();
444 for ( const QgsPolylineXY &linestring : multiPolyline )
445 mpl << linestring;
446 }
447 break;
448
450 {
451 const auto multiPolygon = geom.asMultiPolygon();
452 for ( const QgsPolygonXY &polygon : multiPolygon )
453 {
454 for ( const QgsPolylineXY &ring : polygon )
455 mpl << ring;
456 }
457 }
458 break;
459
460 default:
461 break; // unknown type - do nothing
462 }
463}
464
465// -------------
466
467
468QgsTracer::QgsTracer() = default;
469
470bool QgsTracer::initGraph()
471{
472 if ( mGraph )
473 return true; // already initialized
474
475 mHasTopologyProblem = false;
476
477 QgsFeature f;
479
480 // extract linestrings
481
482 // TODO: use QgsPointLocator as a source for the linework
483
484 QElapsedTimer t1, t2, t2a, t3;
485
486 t1.start();
487 int featuresCounted = 0;
488 for ( const QgsVectorLayer *vl : std::as_const( mLayers ) )
489 {
490 QgsFeatureRequest request;
491 bool filter = false;
492 std::unique_ptr< QgsFeatureRenderer > renderer;
493 std::unique_ptr<QgsRenderContext> ctx;
494
496 if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
497 {
498 renderer.reset( vl->renderer()->clone() );
499 ctx.reset( new QgsRenderContext( *mRenderContext.get() ) );
500 ctx->expressionContext() << QgsExpressionContextUtils::layerScope( vl );
501
502 // setup scale for scale dependent visibility (rule based)
503 renderer->startRender( *ctx.get(), vl->fields() );
504 filter = renderer->capabilities() & QgsFeatureRenderer::Filter;
505 request.setSubsetOfAttributes( renderer->usedAttributes( *ctx.get() ), vl->fields() );
506 }
507 else
508 {
509 request.setNoAttributes();
510 }
511
512 request.setDestinationCrs( mCRS, mTransformContext );
513 if ( !mExtent.isEmpty() )
514 request.setFilterRect( mExtent );
515
516 QgsFeatureIterator fi = vl->getFeatures( request );
517 while ( fi.nextFeature( f ) )
518 {
519 if ( !f.hasGeometry() )
520 continue;
521
522 if ( filter )
523 {
524 ctx->expressionContext().setFeature( f );
525 if ( !renderer->willRenderFeature( f, *ctx.get() ) )
526 {
527 continue;
528 }
529 }
530
531 extractLinework( f.geometry(), mpl );
532
533 ++featuresCounted;
534 if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
535 return false;
536 }
537
538 if ( renderer )
539 {
540 renderer->stopRender( *ctx.get() );
541 }
542 }
543 int timeExtract = t1.elapsed();
544
545 // resolve intersections
546
547 t2.start();
548
549 int timeNodingCall = 0;
550
551#if 0
552 // without noding - if data are known to be noded beforehand
553#else
555
556 try
557 {
558 t2a.start();
559 // GEOSNode_r may throw an exception
560 geos::unique_ptr allGeomGeos( QgsGeos::asGeos( allGeom ) );
561 geos::unique_ptr allNoded( GEOSNode_r( QgsGeos::getGEOSHandler(), allGeomGeos.get() ) );
562 timeNodingCall = t2a.elapsed();
563
564 QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
565
566 mpl = noded.asMultiPolyline();
567 }
568 catch ( GEOSException &e )
569 {
570 // no big deal... we will just not have nicely noded linework, potentially
571 // missing some intersections
572
573 mHasTopologyProblem = true;
574
575 QgsDebugMsg( QStringLiteral( "Tracer Noding Exception: %1" ).arg( e.what() ) );
576 }
577#endif
578
579 int timeNoding = t2.elapsed();
580
581 t3.start();
582
583 mGraph.reset( makeGraph( mpl ) );
584
585 int timeMake = t3.elapsed();
586
587 Q_UNUSED( timeExtract )
588 Q_UNUSED( timeNoding )
589 Q_UNUSED( timeNodingCall )
590 Q_UNUSED( timeMake )
591 QgsDebugMsgLevel( QStringLiteral( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
592 .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ), 2 );
593
594 return true;
595}
596
598{
600}
601
602void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
603{
604 if ( mLayers == layers )
605 return;
606
607 for ( QgsVectorLayer *layer : std::as_const( mLayers ) )
608 {
609 disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
610 disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
611 disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
612 disconnect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
613 disconnect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
614 disconnect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
615 disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
616 }
617
618 mLayers = layers;
619
620 for ( QgsVectorLayer *layer : layers )
621 {
622 connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
623 connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
624 connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
625 connect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
626 connect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
627 connect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
628 connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
629 }
630
632}
633
635{
636 mCRS = crs;
637 mTransformContext = context;
639}
640
642{
643 mRenderContext.reset( new QgsRenderContext( *renderContext ) );
645}
646
648{
649 if ( mExtent == extent )
650 return;
651
652 mExtent = extent;
654}
655
656void QgsTracer::setOffset( double offset )
657{
658 mOffset = offset;
659}
660
661void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
662{
663 quadSegments = mOffsetSegments;
664 joinStyle = static_cast< int >( mOffsetJoinStyle );
665 miterLimit = mOffsetMiterLimit;
666}
667
668void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
669{
670 mOffsetSegments = quadSegments;
671 mOffsetJoinStyle = static_cast< Qgis::JoinStyle >( joinStyle );
672 mOffsetMiterLimit = miterLimit;
673}
674
676{
677 if ( mGraph )
678 return true;
679
680 // configuration from derived class?
681 configure();
682
683 return initGraph();
684}
685
686
688{
689 mGraph.reset( nullptr );
690}
691
692void QgsTracer::onFeatureAdded( QgsFeatureId fid )
693{
694 Q_UNUSED( fid )
696}
697
698void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
699{
700 Q_UNUSED( fid )
702}
703
704void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
705{
706 Q_UNUSED( fid )
707 Q_UNUSED( geom )
709}
710
711void QgsTracer::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
712{
713 Q_UNUSED( fid )
714 Q_UNUSED( idx )
715 Q_UNUSED( value )
717}
718
719void QgsTracer::onDataChanged( )
720{
722}
723
724void QgsTracer::onStyleChanged( )
725{
727}
728
729void QgsTracer::onLayerDestroyed( QObject *obj )
730{
731 // remove the layer before it is completely invalid (static_cast should be the safest cast)
732 mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
734}
735
736QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
737{
738 init(); // does nothing if the graph exists already
739 if ( !mGraph )
740 {
741 if ( error ) *error = ErrTooManyFeatures;
742 return QVector<QgsPointXY>();
743 }
744
745 QElapsedTimer t;
746 t.start();
747 int v1 = pointInGraph( *mGraph, p1 );
748 int v2 = pointInGraph( *mGraph, p2 );
749 int tPrep = t.elapsed();
750
751 if ( v1 == -1 )
752 {
753 if ( error ) *error = ErrPoint1;
754 return QVector<QgsPointXY>();
755 }
756 if ( v2 == -1 )
757 {
758 if ( error ) *error = ErrPoint2;
759 return QVector<QgsPointXY>();
760 }
761
762 QElapsedTimer t2;
763 t2.start();
764 QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
765 int tPath = t2.elapsed();
766
767 Q_UNUSED( tPrep )
768 Q_UNUSED( tPath )
769 QgsDebugMsgLevel( QStringLiteral( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
770
771 resetGraph( *mGraph );
772
773 if ( !points.isEmpty() && mOffset != 0 )
774 {
775 QVector<QgsPointXY> pointsInput( points );
776 QgsLineString linestring( pointsInput );
777 std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
778 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
779 if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
780 {
781 points.clear();
782 for ( int i = 0; i < ls2->numPoints(); ++i )
783 points << QgsPointXY( ls2->pointN( i ) );
784
785 // sometimes (with negative offset?) the resulting curve is reversed
786 if ( points.count() >= 2 )
787 {
788 QgsPointXY res1 = points.first(), res2 = points.last();
789 double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
790 double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
791 if ( diffReversed < diffNormal )
792 std::reverse( points.begin(), points.end() );
793 }
794 }
795 }
796
797 if ( error )
798 *error = points.isEmpty() ? ErrNoPath : ErrNone;
799
800 return points;
801}
802
804{
805 init(); // does nothing if the graph exists already
806 if ( !mGraph )
807 return false;
808
809 if ( point2vertex( *mGraph, pt ) != -1 )
810 return true;
811
812 int lineVertexAfter;
813 int e = point2edge( *mGraph, pt, lineVertexAfter );
814 return e != -1;
815}
JoinStyle
Join styles for buffers.
Definition: qgis.h:1033
Abstract base class for all geometries.
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
This class represents a coordinate reference system (CRS).
Contains information about the context in which a coordinate transform is executed.
static QgsExpressionContextScope * layerScope(const QgsMapLayer *layer)
Creates a new scope which contains variables and functions relating to a QgsMapLayer.
Wrapper for iterator of features from vector data provider or vector layer.
bool nextFeature(QgsFeature &f)
@ Filter
Features may be filtered, i.e. some features may not be rendered (categorized, rule based ....
Definition: qgsrenderer.h:265
This class wraps a request for features to a vector layer (or directly its vector data provider).
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
QgsFeatureRequest & setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the destination crs for feature's geometries.
QgsFeatureRequest & setNoAttributes()
Set that no attributes will be fetched.
QgsFeatureRequest & setFilterRect(const QgsRectangle &rectangle)
Sets the rectangle from which features will be taken.
The feature class encapsulates a single feature including its unique ID, geometry and a list of field...
Definition: qgsfeature.h:56
QgsGeometry geometry
Definition: qgsfeature.h:67
bool hasGeometry() const
Returns true if the feature has an associated geometry.
Definition: qgsfeature.cpp:233
static double sqrDistToLine(double ptX, double ptY, double x1, double y1, double x2, double y2, double &minDistX, double &minDistY, double epsilon) SIP_HOLDGIL
Returns the squared distance between a point and a line.
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:164
const QgsAbstractGeometry * constGet() const SIP_HOLDGIL
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
QgsMultiPolygonXY asMultiPolygon() const
Returns the contents of the geometry as a multi-polygon.
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
QgsPolygonXY asPolygon() const
Returns the contents of the geometry as a polygon.
QgsPolylineXY asPolyline() const
Returns the contents of the geometry as a polyline.
QgsMultiPolylineXY asMultiPolyline() const
Returns the contents of the geometry as a multi-linestring.
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry)
Creates and returns a new geometry engine representing the specified geometry.
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0)
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
Definition: qgsgeos.cpp:220
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:3446
static QgsGeometry geometryFromGeos(GEOSGeometry *geos)
Creates a new QgsGeometry object, feeding in a geometry in GEOS format.
Definition: qgsgeos.cpp:150
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:45
void styleChanged()
Signal emitted whenever a change affects the layer's style.
void dataChanged()
Data of layer changed.
A class to represent a 2D point.
Definition: qgspointxy.h:59
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
double distance(double x, double y) const SIP_HOLDGIL
Returns the distance between this point and a specified x, y coordinate.
Definition: qgspointxy.h:211
A rectangle specified with double values.
Definition: qgsrectangle.h:42
bool isEmpty() const
Returns true if the rectangle is empty.
Definition: qgsrectangle.h:469
Contains information about the context of a rendering operation.
T value(const QString &dynamicKeyPart=QString()) const
Returns settings value.
static const QgsSettingsEntryBool settingsDigitizingSnapInvisibleFeature
Settings entry digitizing snap invisible feature.
void setRenderContext(const QgsRenderContext *renderContext)
Sets the renderContext used for tracing only on visible features.
Definition: qgstracer.cpp:641
void setExtent(const QgsRectangle &extent)
Sets extent to which graph's features will be limited (empty extent means no limit)
Definition: qgstracer.cpp:647
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:803
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:736
PathError
Possible errors that may happen when calling findShortestPath()
Definition: qgstracer.h:138
@ ErrNoPath
Points are not connected in the graph.
Definition: qgstracer.h:143
@ ErrPoint2
End point cannot be joined to the graph.
Definition: qgstracer.h:142
@ ErrPoint1
Start point cannot be joined to the graph.
Definition: qgstracer.h:141
@ ErrNone
No error.
Definition: qgstracer.h:139
@ ErrTooManyFeatures
Max feature count threshold was reached while reading features.
Definition: qgstracer.h:140
void setOffset(double offset)
Set offset in map units that should be applied to the traced paths returned from findShortestPath().
Definition: qgstracer.cpp:656
QgsTracer()
Constructor for QgsTracer.
QgsRectangle extent() const
Gets extent to which graph's features will be limited (empty extent means no limit)
Definition: qgstracer.h:79
~QgsTracer() override
Definition: qgstracer.cpp:597
void setLayers(const QList< QgsVectorLayer * > &layers)
Sets layers used for tracing.
Definition: qgstracer.cpp:602
double offset() const
Gets offset in map units that should be applied to the traced paths returned from findShortestPath().
Definition: qgstracer.h:88
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Gets extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:661
bool init()
Build the internal data structures.
Definition: qgstracer.cpp:675
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
Definition: qgstracer.cpp:668
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
Definition: qgstracer.cpp:687
QList< QgsVectorLayer * > layers() const
Gets layers used for tracing.
Definition: qgstracer.h:56
virtual void configure()
Allows derived classes to setup the settings just before the tracer is initialized.
Definition: qgstracer.h:163
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
Definition: qgstracer.cpp:634
Represents a vector layer which manages a vector based data sets.
void attributeValueChanged(QgsFeatureId fid, int idx, const QVariant &value)
Emitted whenever an attribute value change is done in the edit buffer.
void featureAdded(QgsFeatureId fid)
Emitted when a new feature has been added to the layer.
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Emitted whenever a geometry change is done in the edit buffer.
static bool isCurvedType(Type type) SIP_HOLDGIL
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:911
static Type flatType(Type type) SIP_HOLDGIL
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:732
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:74
qint64 QgsFeatureId
64 bit feature ids negative numbers are used for uncommitted/newly added features
Definition: qgsfeatureid.h:28
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item.
Definition: qgsgeometry.h:76
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:86
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:63
#define QgsDebugMsgLevel(str, level)
Definition: qgslogger.h:39
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
std::pair< int, double > DijkstraQueueItem
Definition: qgstracer.cpp:34
void splitLinestring(const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2)
Definition: qgstracer.cpp:297
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:367
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
Definition: qgstracer.cpp:413
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
Definition: qgstracer.cpp:262
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
Definition: qgstracer.cpp:277
void resetGraph(QgsTracerGraph &g)
Definition: qgstracer.cpp:379
double closestSegment(const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon)
Definition: qgstracer.cpp:69
double distance2D(const QgsPolylineXY &coords)
Definition: qgstracer.cpp:47
int joinVertexToGraph(QgsTracerGraph &g, const QgsPointXY &pt)
Definition: qgstracer.cpp:314
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
Definition: qgstracer.cpp:130
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
Definition: qgstracer.cpp:184
const QgsCoordinateReferenceSystem & crs
int v1
vertices that the edge connects
Definition: qgstracer.cpp:102
int otherVertex(int v0) const
Definition: qgstracer.cpp:106
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
Definition: qgstracer.cpp:104
double weight() const
Definition: qgstracer.cpp:107
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
Definition: qgstracer.cpp:115
QgsPointXY pt
location of the vertex
Definition: qgstracer.cpp:113
Simple graph structure for shortest path search.
Definition: qgstracer.cpp:96
QSet< int > inactiveEdges
Temporarily removed edges.
Definition: qgstracer.cpp:124
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
Definition: qgstracer.cpp:126
QgsTracerGraph()=default
QVector< E > e
Edges of the graph.
Definition: qgstracer.cpp:121
QVector< V > v
Vertices of the graph.
Definition: qgstracer.cpp:119
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b) const
Definition: qgstracer.cpp:39