QGIS API Documentation 3.41.0-Master (3440c17df1d)
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#include "moc_qgstracer.cpp"
18
19
20#include "qgsfeatureiterator.h"
21#include "qgsgeometry.h"
22#include "qgsgeometryutils.h"
23#include "qgsgeos.h"
24#include "qgslogger.h"
25#include "qgsvectorlayer.h"
26#include "qgsrenderer.h"
29#include "qgsrendercontext.h"
31
32#include <queue>
33#include <vector>
34
35typedef std::pair<int, double> DijkstraQueueItem; // first = vertex index, second = distance
36
37// utility comparator for queue items based on distance
38struct comp
39{
41 {
42 return a.second > b.second;
43 }
44};
45
46
47// TODO: move to geometry utils
48double distance2D( const QgsPolylineXY &coords )
49{
50 int np = coords.count();
51 if ( np == 0 )
52 return 0;
53
54 double x0 = coords[0].x(), y0 = coords[0].y();
55 double x1, y1;
56 double dist = 0;
57 for ( int i = 1; i < np; ++i )
58 {
59 x1 = coords[i].x();
60 y1 = coords[i].y();
61 dist += QgsGeometryUtilsBase::distance2D( x1, y1, x0, y0 );
62 x0 = x1;
63 y0 = y1;
64 }
65 return dist;
66}
67
68
69// TODO: move to geometry utils
70double closestSegment( const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon )
71{
72 double sqrDist = std::numeric_limits<double>::max();
73 const QgsPointXY *pldata = pl.constData();
74 int plcount = pl.count();
75 double prevX = pldata[0].x(), prevY = pldata[0].y();
76 double segmentPtX, segmentPtY;
77 for ( int i = 1; i < plcount; ++i )
78 {
79 double currentX = pldata[i].x();
80 double currentY = pldata[i].y();
81 double testDist = QgsGeometryUtilsBase::sqrDistToLine( pt.x(), pt.y(), prevX, prevY, currentX, currentY, segmentPtX, segmentPtY, epsilon );
82 if ( testDist < sqrDist )
83 {
84 sqrDist = testDist;
85 vertexAfter = i;
86 }
87 prevX = currentX;
88 prevY = currentY;
89 }
90 return sqrDist;
91}
92
94
97{
98 QgsTracerGraph() = default;
99
100 struct E // bidirectional edge
101 {
103 int v1, v2;
105 QVector<QgsPointXY> coords;
106
107 int otherVertex( int v0 ) const { return v1 == v0 ? v2 : v1; }
108 double weight() const { return distance2D( coords ); }
109 };
110
111 struct V
112 {
116 QVector<int> edges;
117 };
118
120 QVector<V> v;
122 QVector<E> e;
123
125 QSet<int> inactiveEdges;
128};
129
130
131QgsTracerGraph *makeGraph( const QVector<QgsPolylineXY> &edges )
132{
134 g->joinedVertices = 0;
135 QHash<QgsPointXY, int> point2vertex;
136
137 const auto constEdges = edges;
138 for ( const QgsPolylineXY &line : constEdges )
139 {
140 QgsPointXY p1( line[0] );
141 QgsPointXY p2( line[line.count() - 1] );
142
143 int v1 = -1, v2 = -1;
144 // get or add vertex 1
145 if ( point2vertex.contains( p1 ) )
146 v1 = point2vertex.value( p1 );
147 else
148 {
149 v1 = g->v.count();
151 v.pt = p1;
152 g->v.append( v );
153 point2vertex[p1] = v1;
154 }
155
156 // get or add vertex 2
157 if ( point2vertex.contains( p2 ) )
158 v2 = point2vertex.value( p2 );
159 else
160 {
161 v2 = g->v.count();
163 v.pt = p2;
164 g->v.append( v );
165 point2vertex[p2] = v2;
166 }
167
168 // add edge
170 e.v1 = v1;
171 e.v2 = v2;
172 e.coords = line;
173 g->e.append( e );
174
175 // link edge to vertices
176 int eIdx = g->e.count() - 1;
177 g->v[v1].edges << eIdx;
178 g->v[v2].edges << eIdx;
179 }
180
181 return g;
182}
183
184
185QVector<QgsPointXY> shortestPath( const QgsTracerGraph &g, int v1, int v2 )
186{
187 if ( v1 == -1 || v2 == -1 )
188 return QVector<QgsPointXY>(); // invalid input
189
190 // priority queue to drive Dijkstra:
191 // first of the pair is vertex index, second is distance
192 std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >, comp > Q;
193
194 // shortest distances to each vertex
195 QVector<double> D( g.v.count(), std::numeric_limits<double>::max() );
196 D[v1] = 0;
197
198 // whether vertices have been already processed
199 QVector<bool> F( g.v.count() );
200
201 // using which edge there is shortest path to each vertex
202 QVector<int> S( g.v.count(), -1 );
203
204 int u = -1;
205 Q.push( DijkstraQueueItem( v1, 0 ) );
206
207 while ( !Q.empty() )
208 {
209 u = Q.top().first; // new vertex to visit
210 Q.pop();
211
212 if ( u == v2 )
213 break; // we can stop now, there won't be a shorter path
214
215 if ( F[u] )
216 continue; // ignore previously added path which is actually longer
217
218 const QgsTracerGraph::V &vu = g.v[u];
219 const int *vuEdges = vu.edges.constData();
220 int count = vu.edges.count();
221 for ( int i = 0; i < count; ++i )
222 {
223 const QgsTracerGraph::E &edge = g.e[ vuEdges[i] ];
224 int v = edge.otherVertex( u );
225 double w = edge.weight();
226 if ( !F[v] && D[u] + w < D[v] )
227 {
228 // found a shorter way to the vertex
229 D[v] = D[u] + w;
230 S[v] = vuEdges[i];
231 Q.push( DijkstraQueueItem( v, D[v] ) );
232 }
233 }
234 F[u] = true; // mark the vertex as processed (we know the fastest path to it)
235 }
236
237 if ( u != v2 ) // there's no path to the end vertex
238 return QVector<QgsPointXY>();
239
240 //qDebug("dist %f", D[u]);
241
242 QVector<QgsPointXY> points;
243 QList<int> path;
244 while ( S[u] != -1 )
245 {
246 path << S[u];
247 const QgsTracerGraph::E &e = g.e[S[u]];
248 QVector<QgsPointXY> edgePoints = e.coords;
249 if ( edgePoints[0] != g.v[u].pt )
250 std::reverse( edgePoints.begin(), edgePoints.end() );
251 if ( !points.isEmpty() )
252 points.remove( points.count() - 1 ); // chop last one (will be used from next edge)
253 points << edgePoints;
254 u = e.otherVertex( u );
255 }
256
257 std::reverse( path.begin(), path.end() );
258 std::reverse( points.begin(), points.end() );
259 return points;
260}
261
262
263int point2vertex( const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon = 1e-6 )
264{
265 // TODO: use spatial index
266
267 for ( int i = 0; i < g.v.count(); ++i )
268 {
269 const QgsTracerGraph::V &v = g.v.at( i );
270 if ( v.pt == pt || ( std::fabs( v.pt.x() - pt.x() ) < epsilon && std::fabs( v.pt.y() - pt.y() ) < epsilon ) )
271 return i;
272 }
273
274 return -1;
275}
276
277
278int point2edge( const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon = 1e-6 )
279{
280 for ( int i = 0; i < g.e.count(); ++i )
281 {
282 if ( g.inactiveEdges.contains( i ) )
283 continue; // ignore temporarily disabled edges
284
285 const QgsTracerGraph::E &e = g.e.at( i );
286 int vertexAfter = -1;
287 double dist = closestSegment( e.coords, pt, vertexAfter, epsilon );
288 if ( dist == 0 )
289 {
290 lineVertexAfter = vertexAfter;
291 return i;
292 }
293 }
294 return -1;
295}
296
297
298void splitLinestring( const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2 )
299{
300 int count1 = lineVertexAfter;
301 int count2 = points.count() - lineVertexAfter;
302
303 for ( int i = 0; i < count1; ++i )
304 pts1 << points[i];
305 if ( points[lineVertexAfter - 1] != pt )
306 pts1 << pt; // repeat if not split exactly at that point
307
308 if ( pt != points[lineVertexAfter] )
309 pts2 << pt; // repeat if not split exactly at that point
310 for ( int i = 0; i < count2; ++i )
311 pts2 << points[i + lineVertexAfter];
312}
313
314
316{
317 // find edge where the point is
318 int lineVertexAfter;
319 int eIdx = point2edge( g, pt, lineVertexAfter );
320
321 //qDebug("e: %d", eIdx);
322
323 if ( eIdx == -1 )
324 return -1;
325
326 const QgsTracerGraph::E &e = g.e[eIdx];
327 QgsTracerGraph::V &v1 = g.v[e.v1];
328 QgsTracerGraph::V &v2 = g.v[e.v2];
329
330 QgsPolylineXY out1, out2;
331 splitLinestring( e.coords, pt, lineVertexAfter, out1, out2 );
332
333 int vIdx = g.v.count();
334 int e1Idx = g.e.count();
335 int e2Idx = e1Idx + 1;
336
337 // prepare new vertex and edges
338
340 v.pt = pt;
341 v.edges << e1Idx << e2Idx;
342
344 e1.v1 = e.v1;
345 e1.v2 = vIdx;
346 e1.coords = out1;
347
349 e2.v1 = vIdx;
350 e2.v2 = e.v2;
351 e2.coords = out2;
352
353 // update edge connectivity of existing vertices
354 v1.edges.replace( v1.edges.indexOf( eIdx ), e1Idx );
355 v2.edges.replace( v2.edges.indexOf( eIdx ), e2Idx );
356 g.inactiveEdges << eIdx;
357
358 // add new vertex and edges to the graph
359 g.v.append( v );
360 g.e.append( e1 );
361 g.e.append( e2 );
362 g.joinedVertices++;
363
364 return vIdx;
365}
366
367
369{
370 // try to use existing vertex in the graph
371 int v = point2vertex( g, pt );
372 if ( v != -1 )
373 return v;
374
375 // try to add the vertex to an edge (may fail if point is not on edge)
376 return joinVertexToGraph( g, pt );
377}
378
379
381{
382 // remove extra vertices and edges
383 g.v.resize( g.v.count() - g.joinedVertices );
384 g.e.resize( g.e.count() - g.joinedVertices * 2 );
385 g.joinedVertices = 0;
386
387 // fix vertices of deactivated edges
388 for ( int eIdx : std::as_const( g.inactiveEdges ) )
389 {
390 if ( eIdx >= g.e.count() )
391 continue;
392 const QgsTracerGraph::E &e = g.e[eIdx];
393 QgsTracerGraph::V &v1 = g.v[e.v1];
394 for ( int i = 0; i < v1.edges.count(); ++i )
395 {
396 if ( v1.edges[i] >= g.e.count() )
397 v1.edges.remove( i-- );
398 }
399 v1.edges << eIdx;
400
401 QgsTracerGraph::V &v2 = g.v[e.v2];
402 for ( int i = 0; i < v2.edges.count(); ++i )
403 {
404 if ( v2.edges[i] >= g.e.count() )
405 v2.edges.remove( i-- );
406 }
407 v2.edges << eIdx;
408 }
409
410 g.inactiveEdges.clear();
411}
412
413
415{
416 QgsGeometry geom = g;
417 // segmentize curved geometries - we will use noding algorithm from GEOS
418 // to find all intersections a bit later (so we need them segmentized anyway)
420 {
421 QgsAbstractGeometry *segmentizedGeomV2 = g.constGet()->segmentize();
422 if ( !segmentizedGeomV2 )
423 return;
424
425 geom = QgsGeometry( segmentizedGeomV2 );
426 }
427
428 switch ( QgsWkbTypes::flatType( geom.wkbType() ) )
429 {
431 mpl << geom.asPolyline();
432 break;
433
435 {
436 const auto polygon = geom.asPolygon();
437 for ( const QgsPolylineXY &ring : polygon )
438 mpl << ring;
439 }
440 break;
441
443 {
444 const auto multiPolyline = geom.asMultiPolyline();
445 for ( const QgsPolylineXY &linestring : multiPolyline )
446 mpl << linestring;
447 }
448 break;
449
451 {
452 const auto multiPolygon = geom.asMultiPolygon();
453 for ( const QgsPolygonXY &polygon : multiPolygon )
454 {
455 for ( const QgsPolylineXY &ring : polygon )
456 mpl << ring;
457 }
458 }
459 break;
460
461 default:
462 break; // unknown type - do nothing
463 }
464}
465
466// -------------
467
468
469QgsTracer::QgsTracer() = default;
470
471bool QgsTracer::initGraph()
472{
473 if ( mGraph )
474 return true; // already initialized
475
476 mHasTopologyProblem = false;
477
478 QgsFeature f;
480
481 // extract linestrings
482
483 // TODO: use QgsPointLocator as a source for the linework
484
485 QElapsedTimer t1, t2, t2a, t3;
486
487 t1.start();
488 int featuresCounted = 0;
489 for ( const QgsVectorLayer *vl : std::as_const( mLayers ) )
490 {
491 QgsFeatureRequest request;
492 bool filter = false;
493 std::unique_ptr< QgsFeatureRenderer > renderer;
494 std::unique_ptr<QgsRenderContext> ctx;
495
497 if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
498 {
499 renderer.reset( vl->renderer()->clone() );
500 ctx.reset( new QgsRenderContext( *mRenderContext.get() ) );
501 ctx->expressionContext() << QgsExpressionContextUtils::layerScope( vl );
502
503 // setup scale for scale dependent visibility (rule based)
504 renderer->startRender( *ctx.get(), vl->fields() );
505 filter = renderer->capabilities() & QgsFeatureRenderer::Filter;
506 request.setSubsetOfAttributes( renderer->usedAttributes( *ctx.get() ), vl->fields() );
507 }
508 else
509 {
510 request.setNoAttributes();
511 }
512
513 request.setDestinationCrs( mCRS, mTransformContext );
514 if ( !mExtent.isEmpty() )
515 request.setFilterRect( mExtent );
516
517 QgsFeatureIterator fi = vl->getFeatures( request );
518 while ( fi.nextFeature( f ) )
519 {
520 if ( !f.hasGeometry() )
521 continue;
522
523 if ( filter )
524 {
525 ctx->expressionContext().setFeature( f );
526 if ( !renderer->willRenderFeature( f, *ctx.get() ) )
527 {
528 continue;
529 }
530 }
531
532 extractLinework( f.geometry(), mpl );
533
534 ++featuresCounted;
535 if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
536 return false;
537 }
538
539 if ( renderer )
540 {
541 renderer->stopRender( *ctx.get() );
542 }
543 }
544 int timeExtract = t1.elapsed();
545
546 // resolve intersections
547
548 t2.start();
549
550 int timeNodingCall = 0;
551
552#if 0
553 // without noding - if data are known to be noded beforehand
554#else
556
557 try
558 {
559 t2a.start();
560 // GEOSNode_r may throw an exception
561 geos::unique_ptr allGeomGeos( QgsGeos::asGeos( allGeom ) );
562 geos::unique_ptr allNoded( GEOSNode_r( QgsGeosContext::get(), allGeomGeos.get() ) );
563
564 if ( mAddPointsOnIntersections )
565 {
566 mIntersections = QgsGeometry();
567 }
568 else
569 {
570 geos::unique_ptr allPoints( GEOSGeom_extractUniquePoints_r( QgsGeosContext::get(), allGeomGeos.get() ) );
571 geos::unique_ptr nodedPoints( GEOSGeom_extractUniquePoints_r( QgsGeosContext::get(), allNoded.get() ) );
572 geos::unique_ptr intersectionNodes( GEOSDifference_r( QgsGeosContext::get(), nodedPoints.get(), allPoints.get() ) );
573 mIntersections = QgsGeos::geometryFromGeos( intersectionNodes.release() );
574 }
575
576 timeNodingCall = t2a.elapsed();
577
578 QgsGeometry noded = QgsGeos::geometryFromGeos( allNoded.release() );
579
580 mpl = noded.asMultiPolyline();
581 }
582 catch ( GEOSException &e )
583 {
584 // no big deal... we will just not have nicely noded linework, potentially
585 // missing some intersections
586
587 mHasTopologyProblem = true;
588
589 QgsDebugError( QStringLiteral( "Tracer Noding Exception: %1" ).arg( e.what() ) );
590 }
591#endif
592
593 int timeNoding = t2.elapsed();
594
595 t3.start();
596
597 mGraph.reset( makeGraph( mpl ) );
598
599 int timeMake = t3.elapsed();
600
601 Q_UNUSED( timeExtract )
602 Q_UNUSED( timeNoding )
603 Q_UNUSED( timeNodingCall )
604 Q_UNUSED( timeMake )
605 QgsDebugMsgLevel( QStringLiteral( "tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
606 .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ), 2 );
607
608 return true;
609}
610
615
616void QgsTracer::setLayers( const QList<QgsVectorLayer *> &layers )
617{
618 if ( mLayers == layers )
619 return;
620
621 for ( QgsVectorLayer *layer : std::as_const( mLayers ) )
622 {
623 disconnect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
624 disconnect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
625 disconnect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
626 disconnect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
627 disconnect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
628 disconnect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
629 disconnect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
630 }
631
632 mLayers = layers;
633
634 for ( QgsVectorLayer *layer : layers )
635 {
636 connect( layer, &QgsVectorLayer::featureAdded, this, &QgsTracer::onFeatureAdded );
637 connect( layer, &QgsVectorLayer::featureDeleted, this, &QgsTracer::onFeatureDeleted );
638 connect( layer, &QgsVectorLayer::geometryChanged, this, &QgsTracer::onGeometryChanged );
639 connect( layer, &QgsVectorLayer::attributeValueChanged, this, &QgsTracer::onAttributeValueChanged );
640 connect( layer, &QgsVectorLayer::dataChanged, this, &QgsTracer::onDataChanged );
641 connect( layer, &QgsVectorLayer::styleChanged, this, &QgsTracer::onStyleChanged );
642 connect( layer, &QObject::destroyed, this, &QgsTracer::onLayerDestroyed );
643 }
644
646}
647
649{
650 mCRS = crs;
651 mTransformContext = context;
653}
654
656{
657 mRenderContext.reset( new QgsRenderContext( *renderContext ) );
659}
660
662{
663 if ( mExtent == extent )
664 return;
665
666 mExtent = extent;
668}
669
670void QgsTracer::setOffset( double offset )
671{
672 mOffset = offset;
673}
674
675void QgsTracer::offsetParameters( int &quadSegments, int &joinStyle, double &miterLimit )
676{
677 quadSegments = mOffsetSegments;
678 joinStyle = static_cast< int >( mOffsetJoinStyle );
679 miterLimit = mOffsetMiterLimit;
680}
681
682void QgsTracer::setOffsetParameters( int quadSegments, int joinStyle, double miterLimit )
683{
684 mOffsetSegments = quadSegments;
685 mOffsetJoinStyle = static_cast< Qgis::JoinStyle >( joinStyle );
686 mOffsetMiterLimit = miterLimit;
687}
688
690{
691 if ( mGraph )
692 return true;
693
694 // configuration from derived class?
695 configure();
696
697 return initGraph();
698}
699
700
702{
703 mGraph.reset( nullptr );
704}
705
706void QgsTracer::onFeatureAdded( QgsFeatureId fid )
707{
708 Q_UNUSED( fid )
710}
711
712void QgsTracer::onFeatureDeleted( QgsFeatureId fid )
713{
714 Q_UNUSED( fid )
716}
717
718void QgsTracer::onGeometryChanged( QgsFeatureId fid, const QgsGeometry &geom )
719{
720 Q_UNUSED( fid )
721 Q_UNUSED( geom )
723}
724
725void QgsTracer::onAttributeValueChanged( QgsFeatureId fid, int idx, const QVariant &value )
726{
727 Q_UNUSED( fid )
728 Q_UNUSED( idx )
729 Q_UNUSED( value )
731}
732
733void QgsTracer::onDataChanged( )
734{
736}
737
738void QgsTracer::onStyleChanged( )
739{
741}
742
743void QgsTracer::onLayerDestroyed( QObject *obj )
744{
745 // remove the layer before it is completely invalid (static_cast should be the safest cast)
746 mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
748}
749
750QVector<QgsPointXY> QgsTracer::findShortestPath( const QgsPointXY &p1, const QgsPointXY &p2, PathError *error )
751{
752 init(); // does nothing if the graph exists already
753 if ( !mGraph )
754 {
755 if ( error ) *error = ErrTooManyFeatures;
756 return QVector<QgsPointXY>();
757 }
758
759 QElapsedTimer t;
760 t.start();
761 int v1 = pointInGraph( *mGraph, p1 );
762 int v2 = pointInGraph( *mGraph, p2 );
763 int tPrep = t.elapsed();
764
765 if ( v1 == -1 )
766 {
767 if ( error ) *error = ErrPoint1;
768 return QVector<QgsPointXY>();
769 }
770 if ( v2 == -1 )
771 {
772 if ( error ) *error = ErrPoint2;
773 return QVector<QgsPointXY>();
774 }
775
776 QElapsedTimer t2;
777 t2.start();
778 QgsPolylineXY points = shortestPath( *mGraph, v1, v2 );
779 int tPath = t2.elapsed();
780
781 Q_UNUSED( tPrep )
782 Q_UNUSED( tPath )
783 QgsDebugMsgLevel( QStringLiteral( "path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
784
785 if ( points.size() > 2 && !mIntersections.isEmpty() )
786 {
787 QVector<QgsPointXY> noInts;
788 noInts.reserve( points.size() );
789 noInts.append( points.first() );
790 for ( auto it = std::next( points.begin() ), end = std::prev( points.end() ); it != end; ++it )
791 {
792 if ( mIntersections.contains( it->x(), it->y() ) )
793 {
794 // we skip points that are on a straight segment and were not on the original geometries
795 QgsPointXY nearest;
796 if ( 0 == it->sqrDistToSegment( std::prev( it )->x(),
797 std::prev( it )->y(),
798 std::next( it )->x(),
799 std::next( it )->y(),
800 nearest, 1E-12 ) )
801 {
802 continue;
803 }
804 }
805 noInts << *it;
806 }
807 noInts.append( points.last() );
808 points = noInts;
809 QgsDebugMsgLevel( QStringLiteral( "intersection point removal timing: %1 ms" ).arg( t2.elapsed() - tPath ), 2 );
810 }
811
812 resetGraph( *mGraph );
813
814 if ( !points.isEmpty() && mOffset != 0 )
815 {
816 QVector<QgsPointXY> pointsInput( points );
817 QgsLineString linestring( pointsInput );
818 std::unique_ptr<QgsGeometryEngine> linestringEngine( QgsGeometry::createGeometryEngine( &linestring ) );
819 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
820 if ( QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
821 {
822 points.clear();
823 for ( int i = 0; i < ls2->numPoints(); ++i )
824 points << QgsPointXY( ls2->pointN( i ) );
825
826 // sometimes (with negative offset?) the resulting curve is reversed
827 if ( points.count() >= 2 )
828 {
829 QgsPointXY res1 = points.first(), res2 = points.last();
830 double diffNormal = res1.distance( p1 ) + res2.distance( p2 );
831 double diffReversed = res1.distance( p2 ) + res2.distance( p1 );
832 if ( diffReversed < diffNormal )
833 std::reverse( points.begin(), points.end() );
834 }
835 }
836 }
837
838 if ( error )
839 *error = points.isEmpty() ? ErrNoPath : ErrNone;
840
841 return points;
842}
843
845{
846 init(); // does nothing if the graph exists already
847 if ( !mGraph )
848 return false;
849
850 if ( point2vertex( *mGraph, pt ) != -1 )
851 return true;
852
853 int lineVertexAfter;
854 int e = point2edge( *mGraph, pt, lineVertexAfter );
855 return e != -1;
856}
857
859{
860 if ( enable == mAddPointsOnIntersections )
861 return;
862
863 mAddPointsOnIntersections = enable;
865}
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...
Qgis::WkbType wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry, double precision=0.0, Qgis::GeosCreationFlags flags=Qgis::GeosCreationFlag::SkipEmptyInteriorRings)
Creates and returns a new geometry engine representing the specified geometry using precision on a gr...
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.
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:35
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:70
double distance2D(const QgsPolylineXY &coords)
Definition qgstracer.cpp:48
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:97
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:40