17#include "moc_qgstracer.cpp"
42 return a.second > b.second;
50 int np = coords.count();
54 double x0 = coords[0].x(), y0 = coords[0].y();
57 for (
int i = 1; i < np; ++i )
72 double sqrDist = std::numeric_limits<double>::max();
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 )
79 double currentX = pldata[i].
x();
80 double currentY = pldata[i].
y();
82 if ( testDist < sqrDist )
137 const auto constEdges = edges;
143 int v1 = -1, v2 = -1;
176 int eIdx = g->
e.count() - 1;
177 g->
v[v1].edges << eIdx;
178 g->
v[v2].edges << eIdx;
187 if ( v1 == -1 || v2 == -1 )
188 return QVector<QgsPointXY>();
192 std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >,
comp > Q;
195 QVector<double> D( g.
v.count(), std::numeric_limits<double>::max() );
199 QVector<bool> F( g.
v.count() );
202 QVector<int> S( g.
v.count(), -1 );
219 const int *vuEdges = vu.
edges.constData();
220 int count = vu.
edges.count();
221 for (
int i = 0; i < count; ++i )
226 if ( !F[v] && D[u] + w < D[v] )
238 return QVector<QgsPointXY>();
242 QVector<QgsPointXY> points;
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 );
253 points << edgePoints;
257 std::reverse( path.begin(), path.end() );
258 std::reverse( points.begin(), points.end() );
267 for (
int i = 0; i < g.
v.count(); ++i )
270 if ( v.
pt == pt || ( std::fabs( v.
pt.
x() - pt.
x() ) < epsilon && std::fabs( v.
pt.
y() - pt.
y() ) < epsilon ) )
280 for (
int i = 0; i < g.
e.count(); ++i )
286 int vertexAfter = -1;
290 lineVertexAfter = vertexAfter;
300 int count1 = lineVertexAfter;
301 int count2 = points.count() - lineVertexAfter;
303 for (
int i = 0; i < count1; ++i )
305 if ( points[lineVertexAfter - 1] != pt )
308 if ( pt != points[lineVertexAfter] )
310 for (
int i = 0; i < count2; ++i )
311 pts2 << points[i + lineVertexAfter];
319 int eIdx =
point2edge( g, pt, lineVertexAfter );
333 int vIdx = g.
v.count();
334 int e1Idx = g.
e.count();
335 int e2Idx = e1Idx + 1;
341 v.
edges << e1Idx << e2Idx;
354 v1.
edges.replace( v1.
edges.indexOf( eIdx ), e1Idx );
355 v2.
edges.replace( v2.
edges.indexOf( eIdx ), e2Idx );
390 if ( eIdx >= g.
e.count() )
394 for (
int i = 0; i < v1.
edges.count(); ++i )
396 if ( v1.
edges[i] >= g.
e.count() )
397 v1.
edges.remove( i-- );
402 for (
int i = 0; i < v2.
edges.count(); ++i )
404 if ( v2.
edges[i] >= g.
e.count() )
405 v2.
edges.remove( i-- );
422 if ( !segmentizedGeomV2 )
471bool QgsTracer::initGraph()
476 mHasTopologyProblem =
false;
485 QElapsedTimer t1, t2, t2a, t3;
488 int featuresCounted = 0;
493 std::unique_ptr< QgsFeatureRenderer > renderer;
494 std::unique_ptr<QgsRenderContext> ctx;
497 if ( !enableInvisibleFeature && mRenderContext && vl->renderer() )
499 renderer.reset( vl->renderer()->clone() );
504 renderer->startRender( *ctx.get(), vl->fields() );
525 ctx->expressionContext().setFeature( f );
526 if ( !renderer->willRenderFeature( f, *ctx.get() ) )
535 if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
541 renderer->stopRender( *ctx.get() );
544 int timeExtract = t1.elapsed();
550 int timeNodingCall = 0;
564 if ( mAddPointsOnIntersections )
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() ) );
576 timeNodingCall = t2a.elapsed();
582 catch ( GEOSException &e )
587 mHasTopologyProblem =
true;
589 QgsDebugError( QStringLiteral(
"Tracer Noding Exception: %1" ).arg( e.what() ) );
593 int timeNoding = t2.elapsed();
599 int timeMake = t3.elapsed();
601 Q_UNUSED( timeExtract )
602 Q_UNUSED( timeNoding )
603 Q_UNUSED( timeNodingCall )
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 );
629 disconnect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
642 connect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
651 mTransformContext = context;
677 quadSegments = mOffsetSegments;
678 joinStyle =
static_cast< int >( mOffsetJoinStyle );
679 miterLimit = mOffsetMiterLimit;
684 mOffsetSegments = quadSegments;
686 mOffsetMiterLimit = miterLimit;
703 mGraph.reset(
nullptr );
725void QgsTracer::onAttributeValueChanged(
QgsFeatureId fid,
int idx,
const QVariant &value )
733void QgsTracer::onDataChanged( )
738void QgsTracer::onStyleChanged( )
743void QgsTracer::onLayerDestroyed( QObject *obj )
756 return QVector<QgsPointXY>();
763 int tPrep = t.elapsed();
768 return QVector<QgsPointXY>();
773 return QVector<QgsPointXY>();
779 int tPath = t2.elapsed();
783 QgsDebugMsgLevel( QStringLiteral(
"path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
785 if ( points.size() > 2 && !mIntersections.
isEmpty() )
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 )
792 if ( mIntersections.
contains( it->x(), it->y() ) )
796 if ( 0 == it->sqrDistToSegment( std::prev( it )->x(),
797 std::prev( it )->y(),
798 std::next( it )->x(),
799 std::next( it )->y(),
807 noInts.append( points.last() );
809 QgsDebugMsgLevel( QStringLiteral(
"intersection point removal timing: %1 ms" ).arg( t2.elapsed() - tPath ), 2 );
814 if ( !points.isEmpty() && mOffset != 0 )
816 QVector<QgsPointXY> pointsInput( points );
819 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
820 if (
QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
823 for (
int i = 0; i < ls2->numPoints(); ++i )
827 if ( points.count() >= 2 )
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() );
854 int e =
point2edge( *mGraph, pt, lineVertexAfter );
860 if ( enable == mAddPointsOnIntersections )
863 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...
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...
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