37 return a.second > b.second;
45 int np = coords.count();
49 double x0 = coords[0].x(), y0 = coords[0].y();
52 for (
int i = 1; i < np; ++i )
56 dist += std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
67 double sqrDist = std::numeric_limits<double>::max();
69 int plcount = pl.count();
70 double prevX = pldata[0].
x(), prevY = pldata[0].
y();
71 double segmentPtX, segmentPtY;
72 for (
int i = 1; i < plcount; ++i )
74 double currentX = pldata[i].
x();
75 double currentY = pldata[i].
y();
77 if ( testDist < sqrDist )
122 int joinedVertices{ 0 };
137 int v1 = -1, v2 = -1;
139 if ( point2vertex.contains( p1 ) )
140 v1 = point2vertex.value( p1 );
147 point2vertex[p1] = v1;
151 if ( point2vertex.contains( p2 ) )
152 v2 = point2vertex.value( p2 );
159 point2vertex[p2] = v2;
170 int eIdx = g->
e.count() - 1;
171 g->
v[v1].edges << eIdx;
172 g->
v[v2].edges << eIdx;
181 if ( v1 == -1 || v2 == -1 )
182 return QVector<QgsPointXY>();
186 std::priority_queue< DijkstraQueueItem, std::vector< DijkstraQueueItem >,
comp > Q;
189 QVector<double> D( g.
v.count(), std::numeric_limits<double>::max() );
193 QVector<bool> F( g.
v.count() );
196 QVector<int> S( g.
v.count(), -1 );
213 const int *vuEdges = vu.
edges.constData();
214 int count = vu.
edges.count();
215 for (
int i = 0; i < count; ++i )
220 if ( !F[v] && D[u] + w < D[v] )
232 return QVector<QgsPointXY>();
236 QVector<QgsPointXY> points;
242 QVector<QgsPointXY> edgePoints = e.
coords;
243 if ( edgePoints[0] != g.
v[u].pt )
244 std::reverse( edgePoints.begin(), edgePoints.end() );
245 if ( !points.isEmpty() )
246 points.remove( points.count() - 1 );
247 points << edgePoints;
251 std::reverse( path.begin(), path.end() );
255 std::reverse( points.begin(), points.end() );
264 for (
int i = 0; i < g.
v.count(); ++i )
267 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 )
288 lineVertexAfter = vertexAfter;
298 int count1 = lineVertexAfter;
299 int count2 = points.count() - lineVertexAfter;
301 for (
int i = 0; i < count1; ++i )
303 if ( points[lineVertexAfter - 1] != pt )
306 if ( pt != points[lineVertexAfter] )
308 for (
int i = 0; i < count2; ++i )
309 pts2 << points[i + lineVertexAfter];
317 int eIdx =
point2edge( g, pt, lineVertexAfter );
331 int vIdx = g.
v.count();
332 int e1Idx = g.
e.count();
333 int e2Idx = e1Idx + 1;
339 v.
edges << e1Idx << e2Idx;
352 v1.
edges.replace( v1.
edges.indexOf( eIdx ), e1Idx );
353 v2.
edges.replace( v2.
edges.indexOf( eIdx ), e2Idx );
388 if ( eIdx >= g.
e.count() )
392 for (
int i = 0; i < v1.
edges.count(); ++i )
394 if ( v1.
edges[i] >= g.
e.count() )
395 v1.
edges.remove( i-- );
400 for (
int i = 0; i < v2.
edges.count(); ++i )
402 if ( v2.
edges[i] >= g.
e.count() )
403 v2.
edges.remove( i-- );
420 if ( !segmentizedGeomV2 )
458 bool QgsTracer::initGraph()
463 mHasTopologyProblem =
false;
472 QTime t1, t2, t2a, t3;
475 int featuresCounted = 0;
481 if ( !mExtent.isEmpty() )
493 if ( mMaxFeatureCount != 0 && featuresCounted >= mMaxFeatureCount )
497 int timeExtract = t1.elapsed();
503 int timeNodingCall = 0;
516 timeNodingCall = t2a.elapsed();
519 noded.
fromGeos( allNoded.release() );
523 catch ( GEOSException &e )
528 mHasTopologyProblem =
true;
530 QgsDebugMsg( QString(
"Tracer Noding Exception: %1" ).arg( e.what() ) );
534 int timeNoding = t2.elapsed();
540 int timeMake = t3.elapsed();
542 Q_UNUSED( timeExtract );
543 Q_UNUSED( timeNoding );
544 Q_UNUSED( timeNodingCall );
545 Q_UNUSED( timeMake );
546 QgsDebugMsg( QString(
"tracer extract %1 ms, noding %2 ms (call %3 ms), make %4 ms" )
547 .arg( timeExtract ).arg( timeNoding ).arg( timeNodingCall ).arg( timeMake ) );
558 if ( mLayers == layers )
566 disconnect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
576 connect( layer, &QObject::destroyed,
this, &QgsTracer::onLayerDestroyed );
585 mTransformContext = context;
591 if ( mExtent == extent )
605 quadSegments = mOffsetSegments;
606 joinStyle = mOffsetJoinStyle;
607 miterLimit = mOffsetMiterLimit;
612 mOffsetSegments = quadSegments;
613 mOffsetJoinStyle = joinStyle;
614 mOffsetMiterLimit = miterLimit;
631 mGraph.reset(
nullptr );
653 void QgsTracer::onLayerDestroyed( QObject *obj )
656 mLayers.removeAll( static_cast<QgsVectorLayer *>( obj ) );
665 if ( error ) *error = ErrTooManyFeatures;
666 return QVector<QgsPointXY>();
673 int tPrep = t.elapsed();
677 if ( error ) *error = ErrPoint1;
678 return QVector<QgsPointXY>();
682 if ( error ) *error = ErrPoint2;
683 return QVector<QgsPointXY>();
689 int tPath = t2.elapsed();
693 QgsDebugMsg( QString(
"path timing: prep %1 ms, path %2 ms" ).arg( tPrep ).arg( tPath ) );
697 if ( !points.isEmpty() && mOffset != 0 )
699 QVector<QgsPointXY> pointsInput( points );
702 std::unique_ptr<QgsAbstractGeometry> linestringOffset( linestringEngine->offsetCurve( mOffset, mOffsetSegments, mOffsetJoinStyle, mOffsetMiterLimit ) );
703 if (
QgsLineString *ls2 = qgsgeometry_cast<QgsLineString *>( linestringOffset.get() ) )
706 for (
int i = 0; i < ls2->numPoints(); ++i )
710 if ( points.count() >= 2 )
712 QgsPointXY res1 = points.first(), res2 = points.last();
713 double diffNormal = res1.
distance( p1 ) + res2.distance( p2 );
714 double diffReversed = res1.
distance( p2 ) + res2.distance( p1 );
715 if ( diffReversed < diffNormal )
716 std::reverse( points.begin(), points.end() );
722 *error = points.isEmpty() ? ErrNoPath : ErrNone;
737 int e =
point2edge( *mGraph, pt, lineVertexAfter );
QVector< E > e
Edges of the graph.
QgsFeatureRequest & setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the destination crs for feature's geometries.
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
int pointInGraph(QgsTracerGraph &g, const QgsPointXY &pt)
QVector< QgsPointXY > coords
coordinates of the edge (including endpoints)
int point2vertex(const QgsTracerGraph &g, const QgsPointXY &pt, double epsilon=1e-6)
int joinedVertices
Temporarily added vertices (for each there are two extra edges)
QgsWkbTypes::Type wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
A class to represent a 2D point.
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
void setExtent(const QgsRectangle &extent)
Set extent to which graph's features will be limited (empty extent means no limit) ...
QVector< QgsPolylineXY > QgsPolygonXY
Polygon: first item of the list is outer ring, inner rings (if any) start from second item...
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
QgsTracerGraph * makeGraph(const QVector< QgsPolylineXY > &edges)
A geometry is the spatial representation of a feature.
void splitLinestring(const QgsPolylineXY &points, const QgsPointXY &pt, int lineVertexAfter, QgsPolylineXY &pts1, QgsPolylineXY &pts2)
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
bool hasGeometry() const
Returns true if the feature has an associated geometry.
int joinVertexToGraph(QgsTracerGraph &g, const QgsPointXY &pt)
void featureDeleted(QgsFeatureId fid)
Emitted when a feature has been deleted.
std::pair< int, double > DijkstraQueueItem
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
QgsMultiPolylineXY asMultiPolyline() const
Returns contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list.
void setOffsetParameters(int quadSegments, int joinStyle, double miterLimit)
Set extra parameters for offset curve algorithm (used when offset is non-zero)
void setDestinationCrs(const QgsCoordinateReferenceSystem &crs, const QgsCoordinateTransformContext &context)
Sets the crs and transform context used for tracing.
QSet< int > inactiveEdges
Temporarily removed edges.
QgsPolygonXY asPolygon() const
Returns contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list...
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
PathError
Possible errors that may happen when calling findShortestPath()
This class wraps a request for features to a vector layer (or directly its vector data provider)...
void fromGeos(GEOSGeometry *geos)
Set the geometry, feeding in a geometry in GEOS format.
QgsFeatureRequest & setFilterRect(const QgsRectangle &rectangle)
Sets the rectangle from which features will be taken.
void setOffset(double offset)
Set offset in map units that should be applied to the traced paths returned from findShortestPath().
int point2edge(const QgsTracerGraph &g, const QgsPointXY &pt, int &lineVertexAfter, double epsilon=1e-6)
void geometryChanged(QgsFeatureId fid, const QgsGeometry &geometry)
Is emitted whenever a geometry change is done in the edit buffer.
QVector< QgsPointXY > shortestPath(const QgsTracerGraph &g, int v1, int v2)
void featureAdded(QgsFeatureId fid)
Emitted when a new feature has been added to the layer.
Simple graph structure for shortest path search.
Abstract base class for all geometries.
Contains information about the context in which a coordinate transform is executed.
QgsGeometry geometry() const
Returns the geometry associated with this feature.
double distance(double x, double y) const
Returns the distance between this point and a specified x, y coordinate.
void resetGraph(QgsTracerGraph &g)
double closestSegment(const QgsPolylineXY &pl, const QgsPointXY &pt, int &vertexAfter, double epsilon)
static QgsGeometryEngine * createGeometryEngine(const QgsAbstractGeometry *geometry)
Creates and returns a new geometry engine.
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
double distance2D(const QgsPolylineXY &coords)
QgsTracer()
Constructor for QgsTracer.
QVector< V > v
Vertices of the graph.
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
QVector< int > edges
indices of adjacent edges (used in Dijkstra algorithm)
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
static bool isCurvedType(Type type)
Returns true if the WKB type is a curved type or can contain curved geometries.
GEOSGeometry * exportToGeos(double precision=0) const
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
void invalidateGraph()
Destroy the existing graph structure if any (de-initialize)
void extractLinework(const QgsGeometry &g, QgsMultiPolylineXY &mpl)
Line string geometry type, with support for z-dimension and m-values.
QgsPointXY pt
location of the vertex
This class represents a coordinate reference system (CRS).
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.
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.
bool init()
Build the internal data structures.
void offsetParameters(int &quadSegments, int &joinStyle, double &miterLimit)
Get extra parameters for offset curve algorithm (used when offset is non-zero)
QgsPolylineXY asPolyline() const
Returns contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list...
QList< int > QgsAttributeList
bool nextFeature(QgsFeature &f)
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...
int otherVertex(int v0) const
bool operator()(DijkstraQueueItem a, DijkstraQueueItem b)
Represents a vector layer which manages a vector based data sets.
static Type flatType(Type type)
Returns the flat type for a WKB type.
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
QgsMultiPolygonXY asMultiPolygon() const
Returns contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty list.
void setLayers(const QList< QgsVectorLayer *> &layers)
Set layers used for tracing.
int v1
vertices that the edge connects