QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
qgsalgorithmshortestpathpointtolayer.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsalgorithmshortestpathpointtolayer.cpp
3 ---------------------
4 begin : July 2018
5 copyright : (C) 2018 by Alexander Bruy
6 email : alexander dot bruy at gmail dot com
7 ***************************************************************************/
8
9/***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
17
19
20#include "qgsgraphanalyzer.h"
21
22#include "qgsmessagelog.h"
23
25
26QString QgsShortestPathPointToLayerAlgorithm::name() const
27{
28 return QStringLiteral( "shortestpathpointtolayer" );
29}
30
31QString QgsShortestPathPointToLayerAlgorithm::displayName() const
32{
33 return QObject::tr( "Shortest path (point to layer)" );
34}
35
36QStringList QgsShortestPathPointToLayerAlgorithm::tags() const
37{
38 return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
39}
40
41QString QgsShortestPathPointToLayerAlgorithm::shortHelpString() const
42{
43 return QObject::tr( "This algorithm computes optimal (shortest or fastest) route between given start point and multiple end points defined by point vector layer." );
44}
45
46Qgis::ProcessingAlgorithmDocumentationFlags QgsShortestPathPointToLayerAlgorithm::documentationFlags() const
47{
49}
50
51QgsShortestPathPointToLayerAlgorithm *QgsShortestPathPointToLayerAlgorithm::createInstance() const
52{
53 return new QgsShortestPathPointToLayerAlgorithm();
54}
55
56void QgsShortestPathPointToLayerAlgorithm::initAlgorithm( const QVariantMap & )
57{
58 addCommonParams();
59 addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
60 addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "END_POINTS" ), QObject::tr( "Vector layer with end points" ), QList< int >() << static_cast< int >( Qgis::ProcessingSourceType::VectorPoint ) ) );
61
62 std::unique_ptr< QgsProcessingParameterNumber > maxEndPointDistanceFromNetwork = std::make_unique < QgsProcessingParameterDistance >( QStringLiteral( "POINT_TOLERANCE" ), QObject::tr( "Maximum point distance from network" ), QVariant(), QStringLiteral( "INPUT" ), true, 0 );
63 maxEndPointDistanceFromNetwork->setFlags( maxEndPointDistanceFromNetwork->flags() | Qgis::ProcessingParameterFlag::Advanced );
64 maxEndPointDistanceFromNetwork->setHelp( QObject::tr( "Specifies an optional limit on the distance from the start and end points to the network layer.If the start point is further from the network than this distance an error will be raised. If the end feature is further from the network than this distance it will be treated as non-routable." ) );
65 addParameter( maxEndPointDistanceFromNetwork.release() );
66
67 addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), Qgis::ProcessingSourceType::VectorLine ) );
68
69 std::unique_ptr< QgsProcessingParameterFeatureSink > outputNonRoutable = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT_NON_ROUTABLE" ), QObject::tr( "Non-routable features" ),
71 outputNonRoutable->setHelp( QObject::tr( "An optional output which will be used to store any input features which could not be routed (e.g. those which are too far from the network layer)." ) );
72 outputNonRoutable->setCreateByDefault( false );
73 addParameter( outputNonRoutable.release() );
74}
75
76QVariantMap QgsShortestPathPointToLayerAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
77{
78 loadCommonParams( parameters, context, feedback );
79
80 const QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
81
82 std::unique_ptr< QgsFeatureSource > endPoints( parameterAsSource( parameters, QStringLiteral( "END_POINTS" ), context ) );
83 if ( !endPoints )
84 throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "END_POINTS" ) ) );
85
86 QgsFields fields = endPoints->fields();
87 fields.append( QgsField( QStringLiteral( "start" ), QMetaType::Type::QString ) );
88 fields.append( QgsField( QStringLiteral( "end" ), QMetaType::Type::QString ) );
89 fields.append( QgsField( QStringLiteral( "cost" ), QMetaType::Type::Double ) );
90
91 QString dest;
92 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, Qgis::WkbType::LineString, mNetwork->sourceCrs(), QgsFeatureSink::RegeneratePrimaryKey ) );
93 if ( !sink )
94 throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
95
96 QString nonRoutableSinkId;
97 std::unique_ptr< QgsFeatureSink > nonRoutableSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_NON_ROUTABLE" ), context, nonRoutableSinkId, endPoints->fields(),
98 Qgis::WkbType::Point, mNetwork->sourceCrs() ) );
99
100 const double pointDistanceThreshold = parameters.value( QStringLiteral( "POINT_TOLERANCE" ) ).isValid() ? parameterAsDouble( parameters, QStringLiteral( "POINT_TOLERANCE" ), context ) : -1;
101
102 QVector< QgsPointXY > points;
103 points.push_front( startPoint );
104 QHash< int, QgsAttributes > sourceAttributes;
105 loadPoints( endPoints.get(), points, sourceAttributes, context, feedback );
106
107 feedback->pushInfo( QObject::tr( "Building graph…" ) );
108 QVector< QgsPointXY > snappedPoints;
109 mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
110
111 const QgsPointXY snappedStartPoint = snappedPoints[0];
112
113 if ( pointDistanceThreshold >= 0 )
114 {
115 double distanceStartPointToNetwork = 0;
116 try
117 {
118 distanceStartPointToNetwork = mBuilder->distanceArea()->measureLine( startPoint, snappedStartPoint );
119 }
120 catch ( QgsCsException & )
121 {
122 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
123 }
124
125 if ( distanceStartPointToNetwork > pointDistanceThreshold )
126 {
127 throw QgsProcessingException( QObject::tr( "Start point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceStartPointToNetwork ).arg( pointDistanceThreshold ) );
128 }
129 }
130
131 feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
132 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
133 const int idxStart = graph->findVertex( snappedStartPoint );
134 int idxEnd;
135
136 QVector< int > tree;
137 QVector< double > costs;
138 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
139
140 QVector<QgsPointXY> route;
141 double cost;
142
143 QgsFeature feat;
144 feat.setFields( fields );
145 QgsAttributes attributes;
146
147 const double step = points.size() > 0 ? 100.0 / points.size() : 1;
148 for ( int i = 1; i < points.size(); i++ )
149 {
150 if ( feedback->isCanceled() )
151 {
152 break;
153 }
154
155 const QgsPointXY snappedPoint = snappedPoints.at( i );
156 const QgsPointXY originalPoint = points.at( i );
157
158 if ( pointDistanceThreshold >= 0 )
159 {
160 double distancePointToNetwork = 0;
161 try
162 {
163 distancePointToNetwork = mBuilder->distanceArea()->measureLine( originalPoint, snappedPoint );
164 }
165 catch ( QgsCsException & )
166 {
167 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
168 }
169
170 if ( distancePointToNetwork > pointDistanceThreshold )
171 {
172 feedback->pushWarning( QObject::tr( "Point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distancePointToNetwork ).arg( pointDistanceThreshold ) );
173 if ( nonRoutableSink )
174 {
175 feat.setGeometry( QgsGeometry::fromPointXY( originalPoint ) );
176 attributes = sourceAttributes.value( i );
177 feat.setAttributes( attributes );
178 if ( !nonRoutableSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
179 throw QgsProcessingException( writeFeatureError( nonRoutableSink.get(), parameters, QStringLiteral( "OUTPUT_NON_ROUTABLE" ) ) );
180 }
181
182 feedback->setProgress( i * step );
183 continue;
184 }
185 }
186
187 idxEnd = graph->findVertex( snappedPoint );
188 if ( tree.at( idxEnd ) == -1 )
189 {
190 feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
191 .arg( startPoint.toString(),
192 originalPoint.toString() ) );
193 feat.clearGeometry();
194 attributes = sourceAttributes.value( i );
195 attributes.append( QVariant() );
196 attributes.append( originalPoint.toString() );
197 feat.setAttributes( attributes );
198 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
199 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
200 continue;
201 }
202
203 route.clear();
204 route.push_front( graph->vertex( idxEnd ).point() );
205 cost = costs.at( idxEnd );
206 while ( idxEnd != idxStart )
207 {
208 idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
209 route.push_front( graph->vertex( idxEnd ).point() );
210 }
211
212 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
213 QgsFeature feat;
214 feat.setFields( fields );
215 attributes = sourceAttributes.value( i );
216 attributes.append( startPoint.toString() );
217 attributes.append( originalPoint.toString() );
218 attributes.append( cost / mMultiplier );
219 feat.setAttributes( attributes );
220 feat.setGeometry( geom );
221 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
222 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
223
224 feedback->setProgress( i * step );
225 }
226
227 QVariantMap outputs;
228 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
229 if ( nonRoutableSink )
230 {
231 outputs.insert( QStringLiteral( "OUTPUT_NON_ROUTABLE" ), nonRoutableSinkId );
232 }
233 return outputs;
234}
235
@ VectorPoint
Vector point layers.
@ VectorLine
Vector line layers.
@ RegeneratesPrimaryKey
Algorithm always drops any existing primary keys or FID values and regenerates them in outputs.
QFlags< ProcessingAlgorithmDocumentationFlag > ProcessingAlgorithmDocumentationFlags
Flags describing algorithm behavior for documentation purposes.
Definition qgis.h:3359
@ LineString
LineString.
@ Advanced
Parameter is an advanced parameter which should be hidden from users by default.
A vector of attributes.
Custom exception class for Coordinate Reference System related exceptions.
@ FastInsert
Use faster inserts, at the cost of updating the passed features to reflect changes made at the provid...
@ RegeneratePrimaryKey
This flag indicates, that a primary key field cannot be guaranteed to be unique and the sink should i...
The feature class encapsulates a single feature including its unique ID, geometry and a list of field...
Definition qgsfeature.h:58
void setAttributes(const QgsAttributes &attrs)
Sets the feature's attributes.
void setFields(const QgsFields &fields, bool initAttributes=false)
Assigns a field map with the feature to allow attribute access by attribute name.
void clearGeometry()
Removes any geometry associated with the feature.
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
bool isCanceled() const
Tells whether the operation has been canceled already.
Definition qgsfeedback.h:53
void setProgress(double progress)
Sets the current progress for the feedback object.
Definition qgsfeedback.h:61
Encapsulate a field in an attribute table or data source.
Definition qgsfield.h:53
Container of fields for a vector layer.
Definition qgsfields.h:46
bool append(const QgsField &field, Qgis::FieldOrigin origin=Qgis::FieldOrigin::Provider, int originIndex=-1)
Appends a field.
Definition qgsfields.cpp:69
A geometry is the spatial representation of a feature.
static QgsGeometry fromPolylineXY(const QgsPolylineXY &polyline)
Creates a new LineString geometry from a list of QgsPointXY points.
static QgsGeometry fromPointXY(const QgsPointXY &point)
Creates a new geometry from a QgsPointXY object.
static void dijkstra(const QgsGraph *source, int startVertexIdx, int criterionNum, QVector< int > *resultTree=nullptr, QVector< double > *resultCost=nullptr)
Solve shortest path problem using Dijkstra algorithm.
A class to represent a 2D point.
Definition qgspointxy.h:60
QString toString(int precision=-1) const
Returns a string representation of the point (x, y) with a preset precision.
Contains information about the context in which a processing algorithm is executed.
Custom exception class for processing related exceptions.
Base class for providing feedback from a processing algorithm.
virtual void pushInfo(const QString &info)
Pushes a general informational message from the algorithm.
virtual void pushWarning(const QString &warning)
Pushes a warning informational message from the algorithm.
virtual void reportError(const QString &error, bool fatalError=false)
Reports that the algorithm encountered an error while executing.
A feature sink output for processing algorithms.
An input feature source (such as vector layers) parameter for processing algorithms.
A point parameter for processing algorithms.