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