QGIS API Documentation  3.14.0-Pi (9f7028fd23)
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 
26 QString QgsShortestPathPointToLayerAlgorithm::name() const
27 {
28  return QStringLiteral( "shortestpathpointtolayer" );
29 }
30 
31 QString QgsShortestPathPointToLayerAlgorithm::displayName() const
32 {
33  return QObject::tr( "Shortest path (point to layer)" );
34 }
35 
36 QStringList QgsShortestPathPointToLayerAlgorithm::tags() const
37 {
38  return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
39 }
40 
41 QString 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 
46 QgsShortestPathPointToLayerAlgorithm *QgsShortestPathPointToLayerAlgorithm::createInstance() const
47 {
48  return new QgsShortestPathPointToLayerAlgorithm();
49 }
50 
51 void 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 >() << QgsProcessing::TypeVectorPoint ) );
56 
57  addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), QgsProcessing::TypeVectorLine ) );
58 }
59 
60 QVariantMap QgsShortestPathPointToLayerAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
61 {
62  loadCommonParams( parameters, context, feedback );
63 
64  QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
65 
66  std::unique_ptr< QgsFeatureSource > endPoints( parameterAsSource( parameters, QStringLiteral( "END_POINTS" ), context ) );
67  if ( !endPoints )
68  throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "END_POINTS" ) ) );
69 
70  QgsFields fields = endPoints->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, QgsWkbTypes::LineString, mNetwork->sourceCrs(), QgsFeatureSink::RegeneratePrimaryKey ) );
77  if ( !sink )
78  throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
79 
80  QVector< QgsPointXY > points;
81  points.push_front( startPoint );
82  QHash< int, QgsAttributes > sourceAttributes;
83  loadPoints( endPoints.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  QgsGraph *graph = mBuilder->graph();
91  int idxStart = graph->findVertex( snappedPoints[0] );
92  int idxEnd;
93 
94  QVector< int > tree;
95  QVector< double > costs;
96  QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
97 
98  QVector<QgsPointXY> route;
99  double cost;
100 
101  QgsFeature feat;
102  feat.setFields( fields );
103  QgsAttributes attributes;
104 
105  int 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  idxEnd = graph->findVertex( snappedPoints[i] );
114  if ( tree.at( idxEnd ) == -1 )
115  {
116  feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
117  .arg( startPoint.toString(),
118  points[i].toString() ) );
119  feat.clearGeometry();
120  attributes = sourceAttributes.value( i );
121  attributes.append( QVariant() );
122  attributes.append( points[i].toString() );
123  feat.setAttributes( attributes );
124  sink->addFeature( feat, QgsFeatureSink::FastInsert );
125  continue;
126  }
127 
128  route.clear();
129  route.push_front( graph->vertex( idxEnd ).point() );
130  cost = costs.at( idxEnd );
131  while ( idxEnd != idxStart )
132  {
133  idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
134  route.push_front( graph->vertex( idxEnd ).point() );
135  }
136 
138  QgsFeature feat;
139  feat.setFields( fields );
140  attributes = sourceAttributes.value( i );
141  attributes.append( startPoint.toString() );
142  attributes.append( points[i].toString() );
143  attributes.append( cost / mMultiplier );
144  feat.setAttributes( attributes );
145  feat.setGeometry( geom );
146  sink->addFeature( feat, QgsFeatureSink::FastInsert );
147 
148  feedback->setProgress( i * step );
149  }
150 
151  QVariantMap outputs;
152  outputs.insert( QStringLiteral( "OUTPUT" ), dest );
153  return outputs;
154 }
155 
QgsFeedback::setProgress
void setProgress(double progress)
Sets the current progress for the feedback object.
Definition: qgsfeedback.h:75
QgsGraph
Mathematical graph representation.
Definition: qgsgraph.h:141
QgsGraphVertex::point
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:114
QgsGeometry::fromPolylineXY
static QgsGeometry fromPolylineXY(const QgsPolylineXY &polyline)
Creates a new LineString geometry from a list of QgsPointXY points.
Definition: qgsgeometry.cpp:174
QgsProcessingFeedback
Definition: qgsprocessingfeedback.h:37
QgsProcessingFeedback::pushInfo
virtual void pushInfo(const QString &info)
Pushes a general informational message from the algorithm.
Definition: qgsprocessingfeedback.cpp:48
QgsProcessingFeedback::reportError
virtual void reportError(const QString &error, bool fatalError=false)
Reports that the algorithm encountered an error while executing.
Definition: qgsprocessingfeedback.cpp:39
QgsWkbTypes::LineString
@ LineString
Definition: qgswkbtypes.h:72
QgsFields
Definition: qgsfields.h:44
QgsProcessing::TypeVectorLine
@ TypeVectorLine
Vector line layers.
Definition: qgsprocessing.h:49
QgsProcessingParameterFeatureSource
Definition: qgsprocessingparameters.h:2612
QgsFields::append
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
QgsGraphEdge::fromVertex
int fromVertex() const
Returns the index of the vertex at the start of this edge.
Definition: qgsgraph.cpp:88
QgsProcessing::TypeVectorPoint
@ TypeVectorPoint
Vector point layers.
Definition: qgsprocessing.h:48
QgsGraph::vertex
const QgsGraphVertex & vertex(int idx) const
Returns vertex at given index.
Definition: qgsgraph.cpp:45
QgsFeature::clearGeometry
void clearGeometry()
Removes any geometry associated with the feature.
Definition: qgsfeature.cpp:151
QgsProcessingParameterFeatureSink
Definition: qgsprocessingparameters.h:2773
QgsGraph::edge
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:50
QgsFeature::setGeometry
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
Definition: qgsfeature.cpp:137
QgsFeature::setFields
void setFields(const QgsFields &fields, bool initAttributes=false)
Assign a field map with the feature to allow attribute access by attribute name.
Definition: qgsfeature.cpp:162
QgsProcessingContext
Definition: qgsprocessingcontext.h:43
QgsPointXY::toString
QString toString(int precision=-1) const
Returns a string representation of the point (x, y) with a preset precision.
Definition: qgspointxy.cpp:51
QgsGraph::findVertex
int findVertex(const QgsPointXY &pt) const
Find vertex by associated point.
Definition: qgsgraph.cpp:65
QgsFeatureSink::RegeneratePrimaryKey
@ RegeneratePrimaryKey
This flag indicates, that a primary key field cannot be guaranteed to be unique and the sink should i...
Definition: qgsfeaturesink.h:55
QgsProcessingParameterPoint
Definition: qgsprocessingparameters.h:1535
QgsPointXY
Definition: qgspointxy.h:43
QgsFeedback::isCanceled
bool isCanceled() const
Tells whether the operation has been canceled already.
Definition: qgsfeedback.h:66
QgsGeometry
Definition: qgsgeometry.h:122
qgsalgorithmshortestpathpointtolayer.h
QgsAttributes
Definition: qgsattributes.h:57
qgsgraphanalyzer.h
QgsFeature
Definition: qgsfeature.h:55
QgsFeature::setAttributes
void setAttributes(const QgsAttributes &attrs)
Sets the feature's attributes.
Definition: qgsfeature.cpp:127
QgsProcessingException
Definition: qgsexception.h:82
QgsGraphAnalyzer::dijkstra
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.
Definition: qgsgraphanalyzer.cpp:25
QgsFeatureSink::FastInsert
@ FastInsert
Use faster inserts, at the cost of updating the passed features to reflect changes made at the provid...
Definition: qgsfeaturesink.h:70
qgsmessagelog.h
QgsField
Definition: qgsfield.h:49