QGIS API Documentation 3.37.0-Master (fdefdf9c27f)
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 addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), Qgis::ProcessingSourceType::VectorLine ) );
58}
59
60QVariantMap QgsShortestPathLayerToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
61{
62 loadCommonParams( parameters, context, feedback );
63
64 const QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
65
66 std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
67 if ( !startPoints )
68 throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
69
70 QgsFields fields = startPoints->fields();
71 fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
72 fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
73 fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
74
75 QString dest;
76 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, Qgis::WkbType::LineString, mNetwork->sourceCrs() ) );
77 if ( !sink )
78 throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
79
80 QVector< QgsPointXY > points;
81 points.push_front( endPoint );
82 QHash< int, QgsAttributes > sourceAttributes;
83 loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
84
85 feedback->pushInfo( QObject::tr( "Building graph…" ) );
86 QVector< QgsPointXY > snappedPoints;
87 mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
88
89 feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
90 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
91 const int idxEnd = graph->findVertex( snappedPoints[0] );
92 int idxStart;
93 int currentIdx;
94
95 QVector< int > tree;
96 QVector< double > costs;
97
98 QVector<QgsPointXY> route;
99 double cost;
100
101 QgsFeature feat;
102 feat.setFields( fields );
103 QgsAttributes attributes;
104
105 const double step = points.size() > 0 ? 100.0 / points.size() : 1;
106 for ( int i = 1; i < points.size(); i++ )
107 {
108 if ( feedback->isCanceled() )
109 {
110 break;
111 }
112
113 idxStart = graph->findVertex( snappedPoints[i] );
114 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
115
116 if ( tree.at( idxEnd ) == -1 )
117 {
118 feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
119 .arg( points[i].toString(),
120 endPoint.toString() ) );
121 feat.clearGeometry();
122 attributes = sourceAttributes.value( i );
123 attributes.append( points[i].toString() );
124 feat.setAttributes( attributes );
125 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
126 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
127 continue;
128 }
129
130 route.clear();
131 route.push_front( graph->vertex( idxEnd ).point() );
132 cost = costs.at( idxEnd );
133 currentIdx = idxEnd;
134 while ( currentIdx != idxStart )
135 {
136 currentIdx = graph->edge( tree.at( currentIdx ) ).fromVertex();
137 route.push_front( graph->vertex( currentIdx ).point() );
138 }
139
140 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
141 QgsFeature feat;
142 feat.setFields( fields );
143 attributes = sourceAttributes.value( i );
144 attributes.append( points[i].toString() );
145 attributes.append( endPoint.toString() );
146 attributes.append( cost / mMultiplier );
147 feat.setAttributes( attributes );
148 feat.setGeometry( geom );
149 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
150 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
151
152 feedback->setProgress( i * step );
153 }
154
155 QVariantMap outputs;
156 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
157 return outputs;
158}
159
@ VectorPoint
Vector point layers.
@ VectorLine
Vector line layers.
@ LineString
LineString.
A vector of attributes.
Definition: qgsattributes.h:59
@ 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:56
void setAttributes(const QgsAttributes &attrs)
Sets the feature's attributes.
Definition: qgsfeature.cpp:160
void setFields(const QgsFields &fields, bool initAttributes=false)
Assigns a field map with the feature to allow attribute access by attribute name.
Definition: qgsfeature.cpp:195
void clearGeometry()
Removes any geometry associated with the feature.
Definition: qgsfeature.cpp:181
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
Definition: qgsfeature.cpp:167
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:45
bool append(const QgsField &field, FieldOrigin origin=OriginProvider, int originIndex=-1)
Appends a field. The field must have unique name, otherwise it is rejected (returns false)
Definition: qgsfields.cpp:59
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:162
static QgsGeometry fromPolylineXY(const QgsPolylineXY &polyline)
Creates a new LineString geometry from a list of QgsPointXY points.
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.
Definition: qgspointxy.cpp:51
Contains information about the context in which a processing algorithm is executed.
Custom exception class for processing related exceptions.
Definition: qgsexception.h:83
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 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.