QGIS API Documentation 3.39.0-Master (67e056379ed)
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
46QgsShortestPathPointToLayerAlgorithm *QgsShortestPathPointToLayerAlgorithm::createInstance() const
47{
48 return new QgsShortestPathPointToLayerAlgorithm();
49}
50
51void QgsShortestPathPointToLayerAlgorithm::initAlgorithm( const QVariantMap & )
52{
53 addCommonParams();
54 addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
55 addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "END_POINTS" ), QObject::tr( "Vector layer with end points" ), QList< int >() << static_cast< int >( Qgis::ProcessingSourceType::VectorPoint ) ) );
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 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." ) );
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 QgsShortestPathPointToLayerAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
72{
73 loadCommonParams( parameters, context, feedback );
74
75 const QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
76
77 std::unique_ptr< QgsFeatureSource > endPoints( parameterAsSource( parameters, QStringLiteral( "END_POINTS" ), context ) );
78 if ( !endPoints )
79 throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "END_POINTS" ) ) );
80
81 QgsFields fields = endPoints->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(), QgsFeatureSink::RegeneratePrimaryKey ) );
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, endPoints->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( startPoint );
99 QHash< int, QgsAttributes > sourceAttributes;
100 loadPoints( endPoints.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 snappedStartPoint = snappedPoints[0];
107
108 if ( pointDistanceThreshold >= 0 )
109 {
110 const double distanceStartPointToNetwork = mBuilder->distanceArea()->measureLine( startPoint, snappedStartPoint );
111 if ( distanceStartPointToNetwork > pointDistanceThreshold )
112 {
113 throw QgsProcessingException( QObject::tr( "Start point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceStartPointToNetwork ).arg( pointDistanceThreshold ) );
114 }
115 }
116
117 feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
118 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
119 const int idxStart = graph->findVertex( snappedStartPoint );
120 int idxEnd;
121
122 QVector< int > tree;
123 QVector< double > costs;
124 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
125
126 QVector<QgsPointXY> route;
127 double cost;
128
129 QgsFeature feat;
130 feat.setFields( fields );
131 QgsAttributes attributes;
132
133 const double step = points.size() > 0 ? 100.0 / points.size() : 1;
134 for ( int i = 1; i < points.size(); i++ )
135 {
136 if ( feedback->isCanceled() )
137 {
138 break;
139 }
140
141 const QgsPointXY snappedPoint = snappedPoints.at( i );
142 const QgsPointXY originalPoint = points.at( i );
143
144 if ( pointDistanceThreshold >= 0 )
145 {
146 const double distancePointToNetwork = mBuilder->distanceArea()->measureLine( originalPoint, snappedPoint );
147 if ( distancePointToNetwork > pointDistanceThreshold )
148 {
149 feedback->pushWarning( QObject::tr( "Point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distancePointToNetwork ).arg( pointDistanceThreshold ) );
150 if ( nonRoutableSink )
151 {
152 feat.setGeometry( QgsGeometry::fromPointXY( originalPoint ) );
153 attributes = sourceAttributes.value( i );
154 feat.setAttributes( attributes );
155 if ( !nonRoutableSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
156 throw QgsProcessingException( writeFeatureError( nonRoutableSink.get(), parameters, QStringLiteral( "OUTPUT_NON_ROUTABLE" ) ) );
157 }
158
159 feedback->setProgress( i * step );
160 continue;
161 }
162 }
163
164 idxEnd = graph->findVertex( snappedPoint );
165 if ( tree.at( idxEnd ) == -1 )
166 {
167 feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
168 .arg( startPoint.toString(),
169 originalPoint.toString() ) );
170 feat.clearGeometry();
171 attributes = sourceAttributes.value( i );
172 attributes.append( QVariant() );
173 attributes.append( originalPoint.toString() );
174 feat.setAttributes( attributes );
175 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
176 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
177 continue;
178 }
179
180 route.clear();
181 route.push_front( graph->vertex( idxEnd ).point() );
182 cost = costs.at( idxEnd );
183 while ( idxEnd != idxStart )
184 {
185 idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
186 route.push_front( graph->vertex( idxEnd ).point() );
187 }
188
189 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
190 QgsFeature feat;
191 feat.setFields( fields );
192 attributes = sourceAttributes.value( i );
193 attributes.append( startPoint.toString() );
194 attributes.append( originalPoint.toString() );
195 attributes.append( cost / mMultiplier );
196 feat.setAttributes( attributes );
197 feat.setGeometry( geom );
198 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
199 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
200
201 feedback->setProgress( i * step );
202 }
203
204 QVariantMap outputs;
205 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
206 if ( nonRoutableSink )
207 {
208 outputs.insert( QStringLiteral( "OUTPUT_NON_ROUTABLE" ), nonRoutableSinkId );
209 }
210 return outputs;
211}
212
@ 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.
@ 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.