QGIS API Documentation 3.28.0-Firenze (ed3ad0430f)
qgsalgorithmserviceareafrompoint.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsalgorithmserviceareafrompoint.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 "qgsgeometryutils.h"
21#include "qgsgraphanalyzer.h"
22
24
25QString QgsServiceAreaFromPointAlgorithm::name() const
26{
27 return QStringLiteral( "serviceareafrompoint" );
28}
29
30QString QgsServiceAreaFromPointAlgorithm::displayName() const
31{
32 return QObject::tr( "Service area (from point)" );
33}
34
35QStringList QgsServiceAreaFromPointAlgorithm::tags() const
36{
37 return QObject::tr( "network,service,area,shortest,fastest" ).split( ',' );
38}
39
40QString QgsServiceAreaFromPointAlgorithm::shortHelpString() const
41{
42 return QObject::tr( "This algorithm creates a new vector with all the edges or parts of edges "
43 "of a network line layer that can be reached within a distance or a time, "
44 "starting from a point feature. The distance and the time (both referred to "
45 "as \"travel cost\") must be specified respectively in the network layer "
46 "units or in hours." );
47}
48
49QgsServiceAreaFromPointAlgorithm *QgsServiceAreaFromPointAlgorithm::createInstance() const
50{
51 return new QgsServiceAreaFromPointAlgorithm();
52}
53
54void QgsServiceAreaFromPointAlgorithm::initAlgorithm( const QVariantMap & )
55{
56 addCommonParams();
57 addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
58
59 std::unique_ptr< QgsProcessingParameterNumber > travelCost = std::make_unique< QgsProcessingParameterNumber >( QStringLiteral( "TRAVEL_COST" ), QObject::tr( "Travel cost (distance for 'Shortest', time for 'Fastest')" ), QgsProcessingParameterNumber::Double, 0, true, 0 );
60 travelCost->setFlags( travelCost->flags() | QgsProcessingParameterDefinition::FlagHidden );
61 addParameter( travelCost.release() );
62
63 addParameter( new QgsProcessingParameterNumber( QStringLiteral( "TRAVEL_COST2" ), QObject::tr( "Travel cost (distance for 'Shortest', time for 'Fastest')" ),
65
66 std::unique_ptr< QgsProcessingParameterBoolean > includeBounds = std::make_unique< QgsProcessingParameterBoolean >( QStringLiteral( "INCLUDE_BOUNDS" ), QObject::tr( "Include upper/lower bound points" ), false, true );
67 includeBounds->setFlags( includeBounds->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
68 addParameter( includeBounds.release() );
69
70 std::unique_ptr< QgsProcessingParameterFeatureSink > outputLines = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT_LINES" ), QObject::tr( "Service area (lines)" ),
71 QgsProcessing::TypeVectorLine, QVariant(), true );
72 outputLines->setCreateByDefault( true );
73 addParameter( outputLines.release() );
74
75 std::unique_ptr< QgsProcessingParameterFeatureSink > outputPoints = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT" ), QObject::tr( "Service area (boundary nodes)" ),
76 QgsProcessing::TypeVectorPoint, QVariant(), true );
77 outputPoints->setCreateByDefault( false );
78 addParameter( outputPoints.release() );
79}
80
81QVariantMap QgsServiceAreaFromPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
82{
83 loadCommonParams( parameters, context, feedback );
84
85 const QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
86
87 // use older deprecated travel cost style if specified, to maintain old api
88 const bool useOldTravelCost = parameters.value( QStringLiteral( "TRAVEL_COST" ) ).isValid();
89 double travelCost = parameterAsDouble( parameters, useOldTravelCost ? QStringLiteral( "TRAVEL_COST" ) : QStringLiteral( "TRAVEL_COST2" ), context );
90
91 const int strategy = parameterAsInt( parameters, QStringLiteral( "STRATEGY" ), context );
92 if ( strategy && !useOldTravelCost )
93 travelCost *= mMultiplier;
94
95 bool includeBounds = true; // default to true to maintain 3.0 API
96 if ( parameters.contains( QStringLiteral( "INCLUDE_BOUNDS" ) ) )
97 {
98 includeBounds = parameterAsBool( parameters, QStringLiteral( "INCLUDE_BOUNDS" ), context );
99 }
100
101 feedback->pushInfo( QObject::tr( "Building graph…" ) );
102 QVector< QgsPointXY > snappedPoints;
103 mDirector->makeGraph( mBuilder.get(), QVector< QgsPointXY >() << startPoint, snappedPoints, feedback );
104
105 feedback->pushInfo( QObject::tr( "Calculating service area…" ) );
106 std::unique_ptr< QgsGraph> graph( mBuilder->takeGraph() );
107 const int idxStart = graph->findVertex( snappedPoints[0] );
108
109 QVector< int > tree;
110 QVector< double > costs;
111 QgsGraphAnalyzer::dijkstra( graph.get(), idxStart, 0, &tree, &costs );
112
113 QgsMultiPointXY points;
114 QgsMultiPolylineXY lines;
115 QSet< int > vertices;
116
117 int inboundEdgeIndex;
118 double startVertexCost, endVertexCost;
119 QgsPointXY edgeStart, edgeEnd;
120 QgsGraphEdge edge;
121
122 for ( int i = 0; i < costs.size(); i++ )
123 {
124 inboundEdgeIndex = tree.at( i );
125 if ( inboundEdgeIndex == -1 && i != idxStart )
126 {
127 // unreachable vertex
128 continue;
129 }
130
131 startVertexCost = costs.at( i );
132 if ( startVertexCost > travelCost )
133 {
134 // vertex is too expensive, discard
135 continue;
136 }
137
138 vertices.insert( i );
139 edgeStart = graph->vertex( i ).point();
140
141 // find all edges coming from this vertex
142 const QList< int > outgoingEdges = graph->vertex( i ).outgoingEdges() ;
143 for ( const int edgeId : outgoingEdges )
144 {
145 edge = graph->edge( edgeId );
146 endVertexCost = startVertexCost + edge.cost( 0 ).toDouble();
147 edgeEnd = graph->vertex( edge.toVertex() ).point();
148 if ( endVertexCost <= travelCost )
149 {
150 // end vertex is cheap enough to include
151 vertices.insert( edge.toVertex() );
152 lines.push_back( QgsPolylineXY() << edgeStart << edgeEnd );
153 }
154 else
155 {
156 // travelCost sits somewhere on this edge, interpolate position
157 const QgsPointXY interpolatedEndPoint = QgsGeometryUtils::interpolatePointOnLineByValue( edgeStart.x(), edgeStart.y(), startVertexCost,
158 edgeEnd.x(), edgeEnd.y(), endVertexCost, travelCost );
159
160 points.push_back( interpolatedEndPoint );
161 lines.push_back( QgsPolylineXY() << edgeStart << interpolatedEndPoint );
162 }
163 } // edges
164 } // costs
165
166 // convert to list and sort to maintain same order of points between algorithm runs
167 QList< int > verticesList = qgis::setToList( vertices );
168 points.reserve( verticesList.size() );
169 std::sort( verticesList.begin(), verticesList.end() );
170 for ( const int v : verticesList )
171 {
172 points.push_back( graph->vertex( v ).point() );
173 }
174
175 feedback->pushInfo( QObject::tr( "Writing results…" ) );
176
177 QVariantMap outputs;
178
179 QgsFields fields;
180 fields.append( QgsField( QStringLiteral( "type" ), QVariant::String ) );
181 fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
182
183 QgsFeature feat;
184 feat.setFields( fields );
185
186 QString pointsSinkId;
187 std::unique_ptr< QgsFeatureSink > pointsSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, pointsSinkId, fields,
188 QgsWkbTypes::MultiPoint, mNetwork->sourceCrs() ) );
189
190 if ( pointsSink )
191 {
192 outputs.insert( QStringLiteral( "OUTPUT" ), pointsSinkId );
193
194 const QgsGeometry geomPoints = QgsGeometry::fromMultiPointXY( points );
195 feat.setGeometry( geomPoints );
196 feat.setAttributes( QgsAttributes() << QStringLiteral( "within" ) << startPoint.toString() );
197 if ( !pointsSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
198 throw QgsProcessingException( writeFeatureError( pointsSink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
199
200 if ( includeBounds )
201 {
202 QgsMultiPointXY upperBoundary, lowerBoundary;
203 QVector< int > nodes;
204
205 int vertexId;
206 for ( int i = 0; i < costs.size(); i++ )
207 {
208 if ( costs.at( i ) > travelCost && tree.at( i ) != -1 )
209 {
210 vertexId = graph->edge( tree.at( i ) ).fromVertex();
211 if ( costs.at( vertexId ) <= travelCost )
212 {
213 nodes.push_back( i );
214 }
215 }
216 } // costs
217
218 upperBoundary.reserve( nodes.size() );
219 lowerBoundary.reserve( nodes.size() );
220 for ( const int i : nodes )
221 {
222 upperBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).toVertex() ).point() );
223 lowerBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).fromVertex() ).point() );
224 } // nodes
225
226 const QgsGeometry geomUpper = QgsGeometry::fromMultiPointXY( upperBoundary );
227 const QgsGeometry geomLower = QgsGeometry::fromMultiPointXY( lowerBoundary );
228
229 feat.setGeometry( geomUpper );
230 feat.setAttributes( QgsAttributes() << QStringLiteral( "upper" ) << startPoint.toString() );
231 if ( !pointsSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
232 throw QgsProcessingException( writeFeatureError( pointsSink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
233
234 feat.setGeometry( geomLower );
235 feat.setAttributes( QgsAttributes() << QStringLiteral( "lower" ) << startPoint.toString() );
236 if ( !pointsSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
237 throw QgsProcessingException( writeFeatureError( pointsSink.get(), parameters, QStringLiteral( "OUTPUT" ) ) );
238 } // includeBounds
239 }
240
241 QString linesSinkId;
242 std::unique_ptr< QgsFeatureSink > linesSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_LINES" ), context, linesSinkId, fields,
243 QgsWkbTypes::MultiLineString, mNetwork->sourceCrs() ) );
244
245 if ( linesSink )
246 {
247 outputs.insert( QStringLiteral( "OUTPUT_LINES" ), linesSinkId );
248 const QgsGeometry geomLines = QgsGeometry::fromMultiPolylineXY( lines );
249 feat.setGeometry( geomLines );
250 feat.setAttributes( QgsAttributes() << QStringLiteral( "lines" ) << startPoint.toString() );
251 if ( !linesSink->addFeature( feat, QgsFeatureSink::FastInsert ) )
252 throw QgsProcessingException( writeFeatureError( linesSink.get(), parameters, QStringLiteral( "OUTPUT_LINES" ) ) );
253 }
254
255 return outputs;
256}
257
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:198
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
Definition: qgsfeature.cpp:170
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
static QgsPointXY interpolatePointOnLineByValue(double x1, double y1, double v1, double x2, double y2, double v2, double value) SIP_HOLDGIL
Interpolates the position of a point along the line from (x1, y1) to (x2, y2).
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:164
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
static QgsGeometry fromMultiPointXY(const QgsMultiPointXY &multipoint)
Creates a new geometry from a QgsMultiPointXY object.
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.
This class implements a graph edge.
Definition: qgsgraph.h:45
int toVertex() const
Returns the index of the vertex at the end of this edge.
Definition: qgsgraph.cpp:184
QVariant cost(int strategyIndex) const
Returns edge cost calculated using specified strategy.
Definition: qgsgraph.cpp:169
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
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
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.
@ FlagAdvanced
Parameter is an advanced parameter which should be hidden from users by default.
@ FlagHidden
Parameter is hidden and should not be shown to users.
A numeric parameter for processing algorithms.
A point parameter for processing algorithms.
@ TypeVectorLine
Vector line layers.
Definition: qgsprocessing.h:50
@ TypeVectorPoint
Vector point layers.
Definition: qgsprocessing.h:49
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:86
QVector< QgsPointXY > QgsMultiPointXY
A collection of QgsPoints that share a common collection of attributes.
Definition: qgsgeometry.h:82
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:63