QGIS API Documentation 3.37.0-Master (fdefdf9c27f)
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 "qgsrenderer.h"
28#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 += QgsGeometryUtilsBase::distance2D( x1, y1, x0, 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 = QgsGeometryUtilsBase::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 QgsDebugError( 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:1694
@ LineString
LineString.
@ Polygon
Polygon.
@ MultiPolygon
MultiPolygon.
@ MultiLineString
MultiLineString.
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)
Fetch next feature and stores in f, returns true on success.
@ Filter
Features may be filtered, i.e. some features may not be rendered (categorized, rule based ....
Definition: qgsrenderer.h:272
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:230
static double distance2D(double x1, double y1, double x2, double y2)
Returns the 2D distance between (x1, y1) and (x2, y2).
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.
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:162
QgsMultiPolygonXY asMultiPolygon() const
Returns the contents of the geometry as a multi-polygon.
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.
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
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, double precision=0.0)
Creates and returns a new geometry engine representing the specified geometry using precision on a gr...
Qgis::WkbType wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
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:3576
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:60
double distance(double x, double y) const
Returns the distance between this point and a specified x, y coordinate.
Definition: qgspointxy.h:207
double y
Definition: qgspointxy.h:64
Q_GADGET double x
Definition: qgspointxy.h:63
A rectangle specified with double values.
Definition: qgsrectangle.h:42
bool isEmpty() const
Returns true if the rectangle has no area.
Definition: qgsrectangle.h:492
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:132
@ ErrNoPath
Points are not connected in the graph.
Definition: qgstracer.h:137
@ ErrPoint2
End point cannot be joined to the graph.
Definition: qgstracer.h:136
@ ErrPoint1
Start point cannot be joined to the graph.
Definition: qgstracer.h:135
@ ErrNone
No error.
Definition: qgstracer.h:133
@ ErrTooManyFeatures
Max feature count threshold was reached while reading features.
Definition: qgstracer.h:134
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:78
~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:86
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:55
virtual void configure()
Allows derived classes to setup the settings just before the tracer is initialized.
Definition: qgstracer.h:157
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(Qgis::WkbType type)
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:806
static Qgis::WkbType flatType(Qgis::WkbType type)
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:628
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:73
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:74
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:84
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:62
#define QgsDebugMsgLevel(str, level)
Definition: qgslogger.h:39
#define QgsDebugError(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