QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
qgsalgorithmshortestpathlayertopoint.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsalgorithmshortestpathlayertopoint.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 QgsShortestPathLayerToPointAlgorithm::name() const
27{
28 return QStringLiteral( "shortestpathlayertopoint" );
29}
30
31QString QgsShortestPathLayerToPointAlgorithm::displayName() const
32{
33 return QObject::tr( "Shortest path (layer to point)" );
34}
35
36QStringList QgsShortestPathLayerToPointAlgorithm::tags() const
37{
38 return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
39}
40
41QString QgsShortestPathLayerToPointAlgorithm::shortHelpString() const
42{
43 return QObject::tr( "This algorithm computes optimal (shortest or fastest) route from multiple start points defined by vector layer and given end point." );
44}
45
46QgsShortestPathLayerToPointAlgorithm *QgsShortestPathLayerToPointAlgorithm::createInstance() const
47{
48 return new QgsShortestPathLayerToPointAlgorithm();
49}
50
51void QgsShortestPathLayerToPointAlgorithm::initAlgorithm( const QVariantMap & )
52{
53 addCommonParams();
54 addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "START_POINTS" ), QObject::tr( "Vector layer with start points" ), QList< int >() << static_cast< int >( Qgis::ProcessingSourceType::VectorPoint ) ) );
55 addParameter( new QgsProcessingParameterPoint( QStringLiteral( "END_POINT" ), QObject::tr( "End point" ) ) );
56
57 std::unique_ptr< QgsProcessingParameterNumber > maxEndPointDistanceFromNetwork = std::make_unique < QgsProcessingParameterDistance >( QStringLiteral( "POINT_TOLERANCE" ), QObject::tr( "Maximum point distance from network" ), QVariant(), QStringLiteral( "INPUT" ), true, 0 );
58 maxEndPointDistanceFromNetwork->setFlags( maxEndPointDistanceFromNetwork->flags() | Qgis::ProcessingParameterFlag::Advanced );
59 maxEndPointDistanceFromNetwork->setHelp( QObject::tr( "Specifies an optional limit on the distance from the start and end points to the network layer. If the start feature is further from the network than this distance it will be treated as non-routable. If the end point is further from the network than this distance an error will be raised." ) );
60 addParameter( maxEndPointDistanceFromNetwork.release() );
61
62 addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), Qgis::ProcessingSourceType::VectorLine ) );
63
64 std::unique_ptr< QgsProcessingParameterFeatureSink > outputNonRoutable = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT_NON_ROUTABLE" ), QObject::tr( "Non-routable features" ),
66 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)." ) );
67 outputNonRoutable->setCreateByDefault( false );
68 addParameter( outputNonRoutable.release() );
69}
70
71QVariantMap QgsShortestPathLayerToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
72{
73 loadCommonParams( parameters, context, feedback );
74
75 const QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
76
77 std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
78 if ( !startPoints )
79 throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
80
81 QgsFields fields = startPoints->fields();
82 fields.append( QgsField( QStringLiteral( "start" ), QMetaType::Type::QString ) );
83 fields.append( QgsField( QStringLiteral( "end" ), QMetaType::Type::QString ) );
84 fields.append( QgsField( QStringLiteral( "cost" ), QMetaType::Type::Double ) );
85
86 QString dest;
87 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, Qgis::WkbType::LineString, mNetwork->sourceCrs() ) );
88 if ( !sink )
89 throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
90
91 QString nonRoutableSinkId;
92 std::unique_ptr< QgsFeatureSink > nonRoutableSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_NON_ROUTABLE" ), context, nonRoutableSinkId, startPoints->fields(),
93 Qgis::WkbType::Point, mNetwork->sourceCrs() ) );
94
95 const double pointDistanceThreshold = parameters.value( QStringLiteral( "POINT_TOLERANCE" ) ).isValid() ? parameterAsDouble( parameters, QStringLiteral( "POINT_TOLERANCE" ), context ) : -1;
96
97 QVector< QgsPointXY > points;
98 points.push_front( endPoint );
99 QHash< int, QgsAttributes > sourceAttributes;
100 loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
101
102 feedback->pushInfo( QObject::tr( "Building graph…" ) );
103 QVector< QgsPointXY > snappedPoints;
104 mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
105
106 const QgsPointXY snappedEndPoint = snappedPoints[0];
107
108 if ( pointDistanceThreshold >= 0 )
109 {
110 double distanceEndPointToNetwork = 0;
111 try
112 {
113 distanceEndPointToNetwork = mBuilder->distanceArea()->measureLine( endPoint, snappedEndPoint );
114 }
115 catch ( QgsCsException & )
116 {
117 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
118 }
119
120 if ( distanceEndPointToNetwork > pointDistanceThreshold )
121 {
122 throw QgsProcessingException( QObject::tr( "End point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceEndPointToNetwork ).arg( pointDistanceThreshold ) );
123 }
124 }
125
126 feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
127 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
128 const int idxEnd = graph->findVertex( snappedEndPoint );
129 int idxStart;
130 int currentIdx;
131
132 QVector< int > tree;
133 QVector< double > costs;
134
135 QVector<QgsPointXY> route;
136 double cost;
137
138 QgsFeature feat;
139 feat.setFields( fields );
140 QgsAttributes attributes;
141
142 const double step = points.size() > 0 ? 100.0 / points.size() : 1;
143 for ( int i = 1; i < points.size(); i++ )
144 {
145 if ( feedback->isCanceled() )
146 {
147 break;
148 }
149
150 const QgsPointXY snappedPoint = snappedPoints.at( i );
151 const QgsPointXY originalPoint = points.at( i );
152
153 if ( pointDistanceThreshold >= 0 )
154 {
155 double distancePointToNetwork = 0;
156 try
157 {
158 distancePointToNetwork = mBuilder->distanceArea()->measureLine( originalPoint, snappedPoint );
159 }
160 catch ( QgsCsException & )
161 {
162 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
163 }
164
165 if ( distancePointToNetwork > pointDistanceThreshold )
166 {
167 feedback->pushWarning( QObject::tr( "Point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distancePointToNetwork ).arg( pointDistanceThreshold ) );
168 if ( nonRoutableSink )
169 {
170 feat.setGeometry( QgsGeometry::fromPointXY( originalPoint ) );
171 attributes = sourceAttributes.value( i );
172 feat.setAttributes( attributes );
173 if ( !nonRoutableSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
174 throw QgsProcessingException( writeFeatureError( nonRoutableSink.get(), parameters, QStringLiteral( "OUTPUT_NON_ROUTABLE" ) ) );
175 }
176
177 feedback->setProgress( i * step );
178 continue;
179 }
180 }
181
182 idxStart = graph->findVertex( snappedPoint );
183 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
184
185 if ( tree.at( idxEnd ) == -1 )
186 {
187 feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
188 .arg( originalPoint.toString(),
189 endPoint.toString() ) );
190 feat.clearGeometry();
191 attributes = sourceAttributes.value( i );
192 attributes.append( originalPoint.toString() );
193 feat.setAttributes( attributes );
194 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
195 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
196 continue;
197 }
198
199 route.clear();
200 route.push_front( graph->vertex( idxEnd ).point() );
201 cost = costs.at( idxEnd );
202 currentIdx = idxEnd;
203 while ( currentIdx != idxStart )
204 {
205 currentIdx = graph->edge( tree.at( currentIdx ) ).fromVertex();
206 route.push_front( graph->vertex( currentIdx ).point() );
207 }
208
209 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
210 QgsFeature feat;
211 feat.setFields( fields );
212 attributes = sourceAttributes.value( i );
213 attributes.append( originalPoint.toString() );
214 attributes.append( endPoint.toString() );
215 attributes.append( cost / mMultiplier );
216 feat.setAttributes( attributes );
217 feat.setGeometry( geom );
218 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
219 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
220
221 feedback->setProgress( i * step );
222 }
223
224 QVariantMap outputs;
225 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
226 if ( nonRoutableSink )
227 {
228 outputs.insert( QStringLiteral( "OUTPUT_NON_ROUTABLE" ), nonRoutableSinkId );
229 }
230 return outputs;
231}
232
@ VectorPoint
Vector point layers.
@ VectorLine
Vector line layers.
@ 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...
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.