QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
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( QgsGeosContext::get(), allGeomGeos.get() ) );
562
563 if ( mAddPointsOnIntersections )
564 {
565 mIntersections = QgsGeometry();
566 }
567 else
568 {
569 geos::unique_ptr allPoints( GEOSGeom_extractUniquePoints_r( QgsGeosContext::get(), allGeomGeos.get() ) );
570 geos::unique_ptr nodedPoints( GEOSGeom_extractUniquePoints_r( QgsGeosContext::get(), allNoded.get() ) );
571 geos::unique_ptr intersectionNodes( GEOSDifference_r( QgsGeosContext::get(), nodedPoints.get(), allPoints.get() ) );
572 mIntersections = QgsGeos::geometryFromGeos( intersectionNodes.release() );
573 }
574
575 timeNodingCall = t2a.elapsed();
576
577 QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
578
579 mpl = noded.asMultiPolyline();
580 }
581 catch ( GEOSException &e )
582 {
583 // no big deal... we will just not have nicely noded linework, potentially
584 // missing some intersections
585
586 mHasTopologyProblem = true;
587
588 QgsDebugError( QStringLiteral( "Tracer Noding Exception: %1" ).arg( e.what() ) );
589 }
590#endif
591
592 int timeNoding = t2.elapsed();
593
594 t3.start();
595
596 mGraph.reset( makeGraph( mpl ) );
597
598 int timeMake = t3.elapsed();
599
600 Q_UNUSED( timeExtract )
601 Q_UNUSED( timeNoding )
602 Q_UNUSED( timeNodingCall )
603 Q_UNUSED( timeMake )
604 QgsDebugMsgLevel( QStringLiteral( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
605 .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ), 2 );
606
607 return true;
608}
609
614
615void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
616{
617 if ( mLayers == layers )
618 return;
619
620 for ( QgsVectorLayer *layer : std::as_const( mLayers ) )
621 {
622 disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
623 disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
624 disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
625 disconnect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
626 disconnect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
627 disconnect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
628 disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
629 }
630
631 mLayers = layers;
632
633 for ( QgsVectorLayer *layer : layers )
634 {
635 connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
636 connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
637 connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
638 connect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
639 connect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
640 connect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
641 connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
642 }
643
645}
646
648{
649 mCRS = crs;
650 mTransformContext = context;
652}
653
655{
656 mRenderContext.reset( new QgsRenderContext( *renderContext ) );
658}
659
661{
662 if ( mExtent == extent )
663 return;
664
665 mExtent = extent;
667}
668
669void QgsTracer::setOffset( double offset )
670{
671 mOffset = offset;
672}
673
674void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
675{
676 quadSegments = mOffsetSegments;
677 joinStyle = static_cast< int >( mOffsetJoinStyle );
678 miterLimit = mOffsetMiterLimit;
679}
680
681void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
682{
683 mOffsetSegments = quadSegments;
684 mOffsetJoinStyle = static_cast< Qgis::JoinStyle >( joinStyle );
685 mOffsetMiterLimit = miterLimit;
686}
687
689{
690 if ( mGraph )
691 return true;
692
693 // configuration from derived class?
694 configure();
695
696 return initGraph();
697}
698
699
701{
702 mGraph.reset( nullptr );
703}
704
705void QgsTracer::onFeatureAdded( QgsFeatureId fid )
706{
707 Q_UNUSED( fid )
709}
710
711void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
712{
713 Q_UNUSED( fid )
715}
716
717void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
718{
719 Q_UNUSED( fid )
720 Q_UNUSED( geom )
722}
723
724void QgsTracer::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
725{
726 Q_UNUSED( fid )
727 Q_UNUSED( idx )
728 Q_UNUSED( value )
730}
731
732void QgsTracer::onDataChanged( )
733{
735}
736
737void QgsTracer::onStyleChanged( )
738{
740}
741
742void QgsTracer::onLayerDestroyed( QObject *obj )
743{
744 // remove the layer before it is completely invalid (static_cast should be the safest cast)
745 mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
747}
748
749QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
750{
751 init(); // does nothing if the graph exists already
752 if ( !mGraph )
753 {
754 if ( error ) *error = ErrTooManyFeatures;
755 return QVector<QgsPointXY>();
756 }
757
758 QElapsedTimer t;
759 t.start();
760 int v1 = pointInGraph( *mGraph, p1 );
761 int v2 = pointInGraph( *mGraph, p2 );
762 int tPrep = t.elapsed();
763
764 if ( v1 == -1 )
765 {
766 if ( error ) *error = ErrPoint1;
767 return QVector<QgsPointXY>();
768 }
769 if ( v2 == -1 )
770 {
771 if ( error ) *error = ErrPoint2;
772 return QVector<QgsPointXY>();
773 }
774
775 QElapsedTimer t2;
776 t2.start();
777 QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
778 int tPath = t2.elapsed();
779
780 Q_UNUSED( tPrep )
781 Q_UNUSED( tPath )
782 QgsDebugMsgLevel( QStringLiteral( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
783
784 if ( points.size() > 2 && !mIntersections.isEmpty() )
785 {
786 QVector<QgsPointXY> noInts;
787 noInts.reserve( points.size() );
788 noInts.append( points.first() );
789 for ( auto it = std::next( points.begin() ), end = std::prev( points.end() ); it != end; ++it )
790 {
791 if ( mIntersections.contains( it->x(), it->y() ) )
792 {
793 // we skip points that are on a straight segment and were not on the original geometries
794 QgsPointXY nearest;
795 if ( 0 == it->sqrDistToSegment( std::prev( it )->x(),
796 std::prev( it )->y(),
797 std::next( it )->x(),
798 std::next( it )->y(),
799 nearest, 1E-12 ) )
800 {
801 continue;
802 }
803 }
804 noInts << *it;
805 }
806 noInts.append( points.last() );
807 points = noInts;
808 QgsDebugMsgLevel( QStringLiteral( "intersection point removal timing: %1 ms" ).arg( t2.elapsed() - tPath ), 2 );
809 }
810
811 resetGraph( *mGraph );
812
813 if ( !points.isEmpty() && mOffset != 0 )
814 {
815 QVector<QgsPointXY> pointsInput( points );
816 QgsLineString linestring( pointsInput );
817 std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
818 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
819 if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
820 {
821 points.clear();
822 for ( int i = 0; i < ls2->numPoints(); ++i )
823 points << QgsPointXY( ls2->pointN( i ) );
824
825 // sometimes (with negative offset?) the resulting curve is reversed
826 if ( points.count() >= 2 )
827 {
828 QgsPointXY res1 = points.first(), res2 = points.last();
829 double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
830 double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
831 if ( diffReversed < diffNormal )
832 std::reverse( points.begin(), points.end() );
833 }
834 }
835 }
836
837 if ( error )
838 *error = points.isEmpty() ? ErrNoPath : ErrNone;
839
840 return points;
841}
842
844{
845 init(); // does nothing if the graph exists already
846 if ( !mGraph )
847 return false;
848
849 if ( point2vertex( *mGraph, pt ) != -1 )
850 return true;
851
852 int lineVertexAfter;
853 int e = point2edge( *mGraph, pt, lineVertexAfter );
854 return e != -1;
855}
856
858{
859 if ( enable == mAddPointsOnIntersections )
860 return;
861
862 mAddPointsOnIntersections = enable;
864}
JoinStyle
Join styles for buffers.
Definition qgis.h:1968
@ 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 ....
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:58
QgsGeometry geometry
Definition qgsfeature.h:69
bool hasGeometry() const
Returns true if the feature has an associated geometry.
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.
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.
bool contains(const QgsPointXY *p) const
Returns true if the geometry contains the point p.
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.
bool isEmpty() const
Returns true if the geometry is empty (eg a linestring with no vertices, or a collection with no geom...
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 GEOSContextHandle_t get()
Returns a thread local instance of a GEOS context, safe for use in the current thread.
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0, Qgis::GeosCreationFlags flags=Qgis::GeosCreationFlags())
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
Definition qgsgeos.cpp:257
static QgsGeometry geometryFromGeos(GEOSGeometry *geos)
Creates a new QgsGeometry object, feeding in a geometry in GEOS format.
Definition qgsgeos.cpp:185
Line string geometry type, with support for z-dimension and m-values.
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:206
double y
Definition qgspointxy.h:64
double x
Definition qgspointxy.h:63
A rectangle specified with double values.
bool isEmpty() const
Returns true if the rectangle has no area.
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.
void setExtent(const QgsRectangle &extent)
Sets extent to which graph's features will be limited (empty extent means no limit)
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...
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.
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().
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
void setLayers(const QList< QgsVectorLayer * > &layers)
Sets layers used for tracing.
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)
bool init()
Build the internal data structures.
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
QList< QgsVectorLayer * > layers() const
Gets layers used for tracing.
Definition qgstracer.h:55
void setAddPointsOnIntersectionsEnabled(bool enable)
When enable is true, the shortest path's straight segments will include vertices where the input laye...
virtual void configure()
Allows derived classes to setup the settings just before the tracer is initialized.
Definition qgstracer.h:170
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
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.
static Qgis::WkbType flatType(Qgis::WkbType type)
Returns the flat type for a WKB type.
qint64 QgsFeatureId
64 bit feature ids negative numbers are used for uncommitted/newly added features
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)
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
void resetGraph(QgsTracerGraph &g)
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)
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
const QgsCoordinateReferenceSystem & crs
int v1
vertices that the edge connects
int otherVertex(int v0) const
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
double weight() const
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
QgsPointXY pt
location of the vertex
Simple graph structure for shortest path search.
Definition qgstracer.cpp:96
QSet< int > inactiveEdges
Temporarily removed edges.
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
QgsTracerGraph()=default
QVector< E > e
Edges of the graph.
QVector< V > v
Vertices of the graph.
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b) const
Definition qgstracer.cpp:39