QGIS API Documentation 3.39.0-Master (67e056379ed)
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 const double distanceStartPointToNetwork = mBuilder->distanceArea()->measureLine( startPoint, snappedStartPoint );
94 if ( distanceStartPointToNetwork > pointDistanceThreshold )
95 {
96 throw QgsProcessingException( QObject::tr( "Start point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceStartPointToNetwork ).arg( pointDistanceThreshold ) );
97 }
98
99 const double distanceEndPointToNetwork = mBuilder->distanceArea()->measureLine( endPoint, snappedEndPoint );
100 if ( distanceEndPointToNetwork > pointDistanceThreshold )
101 {
102 throw QgsProcessingException( QObject::tr( "End point is too far from the network layer (%1, maximum permitted is %2)" ).arg( distanceEndPointToNetwork ).arg( pointDistanceThreshold ) );
103 }
104 }
105
106 feedback->pushInfo( QObject::tr( "Calculating shortest path…" ) );
107 std::unique_ptr< QgsGraph > graph( mBuilder->takeGraph() );
108
109 const int idxStart = graph->findVertex( snappedStartPoint );
110 int idxEnd = graph->findVertex( snappedEndPoint );
111
112 QVector< int > tree;
113 QVector< double > costs;
114 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
115
116 if ( tree.at( idxEnd ) == -1 )
117 {
118 throw QgsProcessingException( QObject::tr( "There is no route from start point to end point." ) );
119 }
120
121 QVector<QgsPointXY> route;
122 route.push_front( graph->vertex( idxEnd ).point() );
123 const double cost = costs.at( idxEnd );
124 while ( idxEnd != idxStart )
125 {
126 idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
127 route.push_front( graph->vertex( idxEnd ).point() );
128 }
129
130 feedback->pushInfo( QObject::tr( "Writing results…" ) );
131 const QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
132 QgsFeature feat;
133 feat.setFields( fields );
134 QgsAttributes attributes;
135 attributes << startPoint.toString() << endPoint.toString() << cost / mMultiplier;
136 feat.setGeometry( geom );
137 feat.setAttributes( attributes );
138 if ( !sink->addFeature( feat, QgsFeatureSink::FastInsert ) )
139 throw QgsProcessingException( writeFeatureError( sink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
140
141 QVariantMap outputs;
142 outputs.insert( QStringLiteral( "OUTPUT" ), dest );
143 outputs.insert( QStringLiteral( "TRAVEL_COST" ), cost / mMultiplier );
144 return outputs;
145}
146
@ 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...
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.