41 return a.second > b.second;
49 int np = coords.count();
53 double x0 = coords[0].x(), y0 = coords[0].y();
56 for (
int i = 1; i < np; ++i )
71 double sqrDist = std::numeric_limits<double>::max();
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 )
78 double currentX = pldata[i].
x();
79 double currentY = pldata[i].
y();
81 if ( testDist < sqrDist )
136 const auto constEdges = edges;
142 int v1 = -1, v2 = -1;
175 int eIdx = g->
e.count() - 1;
176 g->
v[v1].edges << eIdx;
177 g->
v[v2].edges << eIdx;
186 if ( v1 == -1 || v2 == -1 )
187 return QVector<QgsPointXY>();
191 std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >,
comp > Q;
194 QVector<double> D( g.
v.count(), std::numeric_limits<double>::max() );
198 QVector<bool> F( g.
v.count() );
201 QVector<int> S( g.
v.count(), -1 );
218 const int *vuEdges = vu.
edges.constData();
219 int count = vu.
edges.count();
220 for (
int i = 0; i < count; ++i )
225 if ( !F[v] && D[u] + w < D[v] )
237 return QVector<QgsPointXY>();
241 QVector<QgsPointXY> points;
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 );
252 points << edgePoints;
256 std::reverse( path.begin(), path.end() );
257 std::reverse( points.begin(), points.end() );
266 for (
int i = 0; i < g.
v.count(); ++i )
269 if ( v.
pt == pt || ( std::fabs( v.
pt.
x() - pt.
x() ) < epsilon && std::fabs( v.
pt.
y() - pt.
y() ) < epsilon ) )
279 for (
int i = 0; i < g.
e.count(); ++i )
285 int vertexAfter = -1;
289 lineVertexAfter = vertexAfter;
299 int count1 = lineVertexAfter;
300 int count2 = points.count() - lineVertexAfter;
302 for (
int i = 0; i < count1; ++i )
304 if ( points[lineVertexAfter - 1] != pt )
307 if ( pt != points[lineVertexAfter] )
309 for (
int i = 0; i < count2; ++i )
310 pts2 << points[i + lineVertexAfter];
318 int eIdx =
point2edge( g, pt, lineVertexAfter );
332 int vIdx = g.
v.count();
333 int e1Idx = g.
e.count();
334 int e2Idx = e1Idx + 1;
340 v.
edges << e1Idx << e2Idx;
353 v1.
edges.replace( v1.
edges.indexOf( eIdx ), e1Idx );
354 v2.
edges.replace( v2.
edges.indexOf( eIdx ), e2Idx );
389 if ( eIdx >= g.
e.count() )
393 for (
int i = 0; i < v1.
edges.count(); ++i )
395 if ( v1.
edges[i] >= g.
e.count() )
396 v1.
edges.remove( i-- );
401 for (
int i = 0; i < v2.
edges.count(); ++i )
403 if ( v2.
edges[i] >= g.
e.count() )
404 v2.
edges.remove( i-- );
421 if ( !segmentizedGeomV2 )
470bool QgsTracer::initGraph()
475 mHasTopologyProblem =
false;
484 QElapsedTimer t1, t2, t2a, t3;
487 int featuresCounted = 0;
492 std::unique_ptr< QgsFeatureRenderer > renderer;
493 std::unique_ptr<QgsRenderContext> ctx;
496 if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
498 renderer.reset( vl->renderer()->clone() );
503 renderer->startRender( *ctx.get(), vl->fields() );
524 ctx->expressionContext().setFeature( f );
525 if ( !renderer->willRenderFeature( f, *ctx.get() ) )
534 if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
540 renderer->stopRender( *ctx.get() );
543 int timeExtract = t1.elapsed();
549 int timeNodingCall = 0;
563 if ( mAddPointsOnIntersections )
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() ) );
575 timeNodingCall = t2a.elapsed();
581 catch ( GEOSException &e )
586 mHasTopologyProblem =
true;
588 QgsDebugError( QStringLiteral(
"Tracer Noding Exception: %1" ).arg( e.what() ) );
592 int timeNoding = t2.elapsed();
598 int timeMake = t3.elapsed();
600 Q_UNUSED( timeExtract )
601 Q_UNUSED( timeNoding )
602 Q_UNUSED( timeNodingCall )
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 );
628 disconnect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
641 connect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
650 mTransformContext = context;
676 quadSegments = mOffsetSegments;
677 joinStyle =
static_cast< int >( mOffsetJoinStyle );
678 miterLimit = mOffsetMiterLimit;
683 mOffsetSegments = quadSegments;
685 mOffsetMiterLimit = miterLimit;
702 mGraph.reset(
nullptr );
724void QgsTracer::onAttributeValueChanged(
QgsFeatureId fid,
int idx,
const QVariant &value )
732void QgsTracer::onDataChanged( )
737void QgsTracer::onStyleChanged( )
742void QgsTracer::onLayerDestroyed( QObject *obj )
755 return QVector<QgsPointXY>();
762 int tPrep = t.elapsed();
767 return QVector<QgsPointXY>();
772 return QVector<QgsPointXY>();
778 int tPath = t2.elapsed();
782 QgsDebugMsgLevel( QStringLiteral(
"path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
784 if ( points.size() > 2 && !mIntersections.
isEmpty() )
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 )
791 if ( mIntersections.
contains( it->x(), it->y() ) )
795 if ( 0 == it->sqrDistToSegment( std::prev( it )->x(),
796 std::prev( it )->y(),
797 std::next( it )->x(),
798 std::next( it )->y(),
806 noInts.append( points.last() );
808 QgsDebugMsgLevel( QStringLiteral(
"intersection point removal timing: %1 ms" ).arg( t2.elapsed() - tPath ), 2 );
813 if ( !points.isEmpty() && mOffset != 0 )
815 QVector<QgsPointXY> pointsInput( points );
818 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
819 if (
QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
822 for (
int i = 0; i < ls2->numPoints(); ++i )
826 if ( points.count() >= 2 )
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() );
853 int e =
point2edge( *mGraph, pt, lineVertexAfter );
859 if ( enable == mAddPointsOnIntersections )
862 mAddPointsOnIntersections = enable;
JoinStyle
Join styles for buffers.
@ 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...
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...
static QgsGeometry geometryFromGeos(GEOSGeometry *geos)
Creates a new QgsGeometry object, feeding in a geometry in GEOS format.
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.
double distance(double x, double y) const
Returns the distance between this point and a specified x, y coordinate.
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()
@ ErrNoPath
Points are not connected in the graph.
@ ErrPoint2
End point cannot be joined to the graph.
@ ErrPoint1
Start point cannot be joined to the graph.
@ ErrTooManyFeatures
Max feature count threshold was reached while reading features.
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)
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().
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.
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.
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.
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
#define QgsDebugMsgLevel(str, level)
#define QgsDebugError(str)
std::pair< int, double > DijkstraQueueItem
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)
double distance2D(const QgsPolylineXY &coords)
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)
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
QgsPointXY pt
location of the vertex
Simple graph structure for shortest path search.
QSet< int > inactiveEdges
Temporarily removed edges.
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
QVector< E > e
Edges of the graph.
QVector< V > v
Vertices of the graph.
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b) const