QGIS API Documentation  3.20.0-Odense (decaadbb31)
qgsalgorithmshortestpathpointtopoint.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsalgorithmshortestpathpointtopoint.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 
23 
24 QString QgsShortestPathPointToPointAlgorithm::name() const
25 {
26  return QStringLiteral( "shortestpathpointtopoint" );
27 }
28 
29 QString QgsShortestPathPointToPointAlgorithm::displayName() const
30 {
31  return QObject::tr( "Shortest path (point to point)" );
32 }
33 
34 QStringList QgsShortestPathPointToPointAlgorithm::tags() const
35 {
36  return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
37 }
38 
39 QString QgsShortestPathPointToPointAlgorithm::shortHelpString() const
40 {
41  return QObject::tr( "This algorithm computes optimal (shortest or fastest) route between given start and end points." );
42 }
43 
44 QgsShortestPathPointToPointAlgorithm *QgsShortestPathPointToPointAlgorithm::createInstance() const
45 {
46  return new QgsShortestPathPointToPointAlgorithm();
47 }
48 
49 void QgsShortestPathPointToPointAlgorithm::initAlgorithm( const QVariantMap & )
50 {
51  addCommonParams();
52  addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
53  addParameter( new QgsProcessingParameterPoint( QStringLiteral( "END_POINT" ), QObject::tr( "End point" ) ) );
54 
55  addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), QgsProcessing::TypeVectorLine ) );
56  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "TRAVEL_COST" ), QObject::tr( "Travel cost" ) ) );
57 }
58 
59 QVariantMap QgsShortestPathPointToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
60 {
61  loadCommonParams( parameters, context, feedback );
62 
63  QgsFields fields;
64  fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
65  fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
66  fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
67 
68  QString dest;
69  std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::LineString, mNetwork->sourceCrs() ) );
70  if ( !sink )
71  throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
72 
73  QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
74  QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
75 
76  feedback->pushInfo( QObject::tr( "Building graph…" ) );
77  QVector< QgsPointXY > points;
78  points << startPoint << endPoint;
79  QVector< QgsPointXY > snappedPoints;
80  mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
81 
82  feedback->pushInfo( QObject::tr( "Calculating shortest path…" ) );
83  QgsGraph *graph = mBuilder->graph();
84  int idxStart = graph->findVertex( snappedPoints[0] );
85  int idxEnd = graph->findVertex( snappedPoints[1] );
86 
87  QVector< int > tree;
88  QVector< double > costs;
89  QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
90 
91  if ( tree.at( idxEnd ) == -1 )
92  {
93  throw QgsProcessingException( QObject::tr( "There is no route from start point to end point." ) );
94  }
95 
96  QVector<QgsPointXY> route;
97  route.push_front( graph->vertex( idxEnd ).point() );
98  double cost = costs.at( idxEnd );
99  while ( idxEnd != idxStart )
100  {
101  idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
102  route.push_front( graph->vertex( idxEnd ).point() );
103  }
104 
105  feedback->pushInfo( QObject::tr( "Writing results…" ) );
107  QgsFeature feat;
108  feat.setFields( fields );
109  QgsAttributes attributes;
110  attributes << startPoint.toString() << endPoint.toString() << cost / mMultiplier;
111  feat.setGeometry( geom );
112  feat.setAttributes( attributes );
113  sink->addFeature( feat, QgsFeatureSink::FastInsert );
114 
115  QVariantMap outputs;
116  outputs.insert( QStringLiteral( "OUTPUT" ), dest );
117  outputs.insert( QStringLiteral( "TRAVEL_COST" ), cost / mMultiplier );
118  return outputs;
119 }
120 
A vector of attributes.
Definition: qgsattributes.h:58
@ 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:135
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:170
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
Definition: qgsfeature.cpp:145
Encapsulate a field in an attribute table or data source.
Definition: qgsfield.h:51
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:124
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.
int fromVertex() const
Returns the index of the vertex at the start of this edge.
Definition: qgsgraph.cpp:88
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:114
Mathematical graph representation.
Definition: qgsgraph.h:142
const QgsGraphVertex & vertex(int idx) const
Returns vertex at given index.
Definition: qgsgraph.cpp:45
int findVertex(const QgsPointXY &pt) const
Find vertex by associated point.
Definition: qgsgraph.cpp:65
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:50
A class to represent a 2D point.
Definition: qgspointxy.h:59
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.
A numeric output for processing algorithms.
A feature sink output for processing algorithms.
A point parameter for processing algorithms.
@ TypeVectorLine
Vector line layers.
Definition: qgsprocessing.h:50