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 )
60 dist += std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
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;
562 timeNodingCall = t2a.elapsed();
568 catch ( GEOSException &e )
573 mHasTopologyProblem =
true;
575 QgsDebugMsg( QStringLiteral(
"Tracer Noding Exception: %1" ).arg( e.what() ) );
579 int timeNoding = t2.elapsed();
585 int timeMake = t3.elapsed();
587 Q_UNUSED( timeExtract )
588 Q_UNUSED( timeNoding )
589 Q_UNUSED( timeNodingCall )
591 QgsDebugMsgLevel( QStringLiteral(
"tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
592 .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ), 2 );
615 disconnect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
628 connect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
637 mTransformContext = context;
663 quadSegments = mOffsetSegments;
664 joinStyle =
static_cast< int >( mOffsetJoinStyle );
665 miterLimit = mOffsetMiterLimit;
670 mOffsetSegments = quadSegments;
672 mOffsetMiterLimit = miterLimit;
689 mGraph.reset(
nullptr );
711void QgsTracer::onAttributeValueChanged(
QgsFeatureId fid,
int idx,
const QVariant &value )
719void QgsTracer::onDataChanged( )
724void QgsTracer::onStyleChanged( )
729void QgsTracer::onLayerDestroyed( QObject *obj )
742 return QVector<QgsPointXY>();
749 int tPrep = t.elapsed();
754 return QVector<QgsPointXY>();
759 return QVector<QgsPointXY>();
765 int tPath = t2.elapsed();
769 QgsDebugMsgLevel( QStringLiteral(
"path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ), 2 );
773 if ( !points.isEmpty() && mOffset != 0 )
775 QVector<QgsPointXY> pointsInput( points );
778 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
779 if (
QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
782 for (
int i = 0; i < ls2->numPoints(); ++i )
786 if ( points.count() >= 2 )
788 QgsPointXY res1 = points.first(), res2 = points.last();
789 double diffNormal = res1.
distance( p1 ) + res2.distance( p2 );
790 double diffReversed = res1.
distance( p2 ) + res2.distance( p1 );
791 if ( diffReversed < diffNormal )
792 std::reverse( points.begin(), points.end() );
813 int e =
point2edge( *mGraph, pt, lineVertexAfter );
JoinStyle
Join styles for buffers.
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)
@ 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 sqrDistToLine(double ptX, double ptY, double x1, double y1, double x2, double y2, double &minDistX, double &minDistY, double epsilon) SIP_HOLDGIL
Returns the squared distance between a point and a line.
A geometry is the spatial representation of a feature.
const QgsAbstractGeometry * constGet() const SIP_HOLDGIL
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
QgsMultiPolygonXY asMultiPolygon() const
Returns the contents of the geometry as a multi-polygon.
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
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.
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.
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry)
Creates and returns a new geometry engine representing the specified geometry.
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0)
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
static GEOSContextHandle_t getGEOSHandler()
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 SIP_HOLDGIL
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 is empty.
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.
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(Type type) SIP_HOLDGIL
Returns true if the WKB type is a curved type or can contain curved geometries.
static Type flatType(Type type) SIP_HOLDGIL
Returns the flat type for a WKB type.
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
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)
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