QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
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
24QString QgsShortestPathPointToPointAlgorithm::name() const
25{
26 return QStringLiteral( "shortestpathpointtopoint" );
27}
28
29QString QgsShortestPathPointToPointAlgorithm::displayName() const
30{
31 return QObject::tr( "Shortest path (point to point)" );
32}
33
34QStringList QgsShortestPathPointToPointAlgorithm::tags() const
35{
36 return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
37}
38
39QString QgsShortestPathPointToPointAlgorithm::shortHelpString() const
40{
41 return QObject::tr( "This algorithm computes optimal (shortest or fastest) route between given start and end points." );
42}
43
44QgsShortestPathPointToPointAlgorithm *QgsShortestPathPointToPointAlgorithm::createInstance() const
45{
46 return new QgsShortestPathPointToPointAlgorithm();
47}
48
49void 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" ), Qgis::ProcessingSourceType::VectorLine ) );
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 either point is further from the network than this distance an error will be raised." ) );
60 addParameter( maxEndPointDistanceFromNetwork.release() );
61
62 addOutput( new QgsProcessingOutputNumber( QStringLiteral( "TRAVEL_COST" ), QObject::tr( "Travel cost" ) ) );
63}
64
65QVariantMap QgsShortestPathPointToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
66{
67 loadCommonParams( parameters, context, feedback );
68
69 QgsFields fields;
70 fields.append( QgsField( QStringLiteral( "start" ), QMetaType::Type::QString ) );
71 fields.append( QgsField( QStringLiteral( "end" ), QMetaType::Type::QString ) );
72 fields.append( QgsField( QStringLiteral( "cost" ), QMetaType::Type::Double ) );
73
74 QString dest;
75 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, Qgis::WkbType::LineString, mNetwork->sourceCrs() ) );
76 if ( !sink )
77 throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
78
79 const QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
80 const QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
81
82 feedback->pushInfo( QObject::tr( "Building graph…" ) );
83 QVector< QgsPointXY > snappedPoints;
84 mDirector->makeGraph( mBuilder.get(), { startPoint, endPoint }, snappedPoints, feedback );
85 const QgsPointXY snappedStartPoint = snappedPoints[0];
86 const QgsPointXY snappedEndPoint = snappedPoints[1];
87
88 // check distance for the snapped start/end points
89 if ( parameters.value( QStringLiteral( "POINT_TOLERANCE" ) ).isValid() )
90 {
91 const double pointDistanceThreshold = parameterAsDouble( parameters, QStringLiteral( "POINT_TOLERANCE" ), context );
92
93 double distanceStartPointToNetwork = 0;
94 try
95 {
96 distanceStartPointToNetwork = mBuilder->distanceArea()->measureLine( startPoint, snappedStartPoint );
97 }
98 catch ( QgsCsException & )
99 {
100 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
101 }
102
103 if ( distanceStartPointToNetwork > pointDistanceThreshold )
104 {
105 throw QgsProcessingException( QObject::tr( "Start point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceStartPointToNetwork ).arg( pointDistanceThreshold ) );
106 }
107
108 double distanceEndPointToNetwork = 0;
109 try
110 {
111 distanceEndPointToNetwork = mBuilder->distanceArea()->measureLine( endPoint, snappedEndPoint );
112 }
113 catch ( QgsCsException & )
114 {
115 throw QgsProcessingException( QObject::tr( "An error occurred while calculating length" ) );
116 }
117
118 if ( distanceEndPointToNetwork > pointDistanceThreshold )
119 {
120 throw QgsProcessingException( QObject::tr( "End point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceEndPointToNetwork ).arg( pointDistanceThreshold ) );
121 }
122 }
123
124 feedback->pushInfo( QObject::tr( "Calculating shortest path…" ) );
125 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
126
127 const int idxStart = graph->findVertex( snappedStartPoint );
128 int idxEnd = graph->findVertex( snappedEndPoint );
129
130 QVector< int > tree;
131 QVector< double > costs;
132 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
133
134 if ( tree.at( idxEnd ) == -1 )
135 {
136 throw QgsProcessingException( QObject::tr( "There is no route from start point to end point." ) );
137 }
138
139 QVector<QgsPointXY> route;
140 route.push_front( graph->vertex( idxEnd ).point() );
141 const double cost = costs.at( idxEnd );
142 while ( idxEnd != idxStart )
143 {
144 idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
145 route.push_front( graph->vertex( idxEnd ).point() );
146 }
147
148 feedback->pushInfo( QObject::tr( "Writing results…" ) );
149 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
150 QgsFeature feat;
151 feat.setFields( fields );
152 QgsAttributes attributes;
153 attributes << startPoint.toString() << endPoint.toString() << cost / mMultiplier;
154 feat.setGeometry( geom );
155 feat.setAttributes( attributes );
156 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
157 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
158
159 QVariantMap outputs;
160 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
161 outputs.insert( QStringLiteral( "TRAVEL_COST" ), cost / mMultiplier );
162 return outputs;
163}
164
@ 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 setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
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 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.
A numeric output for processing algorithms.
A feature sink output for processing algorithms.
A point parameter for processing algorithms.