QGIS API Documentation  3.14.0-Pi (9f7028fd23)
qgsalgorithmserviceareafromlayer.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsalgorithmserviceareafromlayer.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 
25 QString QgsServiceAreaFromLayerAlgorithm::name() const
26 {
27  return QStringLiteral( "serviceareafromlayer" );
28 }
29 
30 QString QgsServiceAreaFromLayerAlgorithm::displayName() const
31 {
32  return QObject::tr( "Service area (from layer)" );
33 }
34 
35 QStringList QgsServiceAreaFromLayerAlgorithm::tags() const
36 {
37  return QObject::tr( "network,service,area,shortest,fastest" ).split( ',' );
38 }
39 
40 QString QgsServiceAreaFromLayerAlgorithm::shortHelpString() const
41 {
42  return QObject::tr( "This algorithm creates a new vector with all the edges or parts of "
43  "edges of a network line layer that can be reached within a distance "
44  "or a time, starting from features of a point layer. The distance and "
45  "the time (both referred to as \"travel cost\") must be specified "
46  "respectively in the network layer units or in hours." );
47 }
48 
49 QgsServiceAreaFromLayerAlgorithm *QgsServiceAreaFromLayerAlgorithm::createInstance() const
50 {
51  return new QgsServiceAreaFromLayerAlgorithm();
52 }
53 
54 void QgsServiceAreaFromLayerAlgorithm::initAlgorithm( const QVariantMap & )
55 {
56  addCommonParams();
57  addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "START_POINTS" ), QObject::tr( "Vector layer with start points" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
58 
59  std::unique_ptr< QgsProcessingParameterNumber > travelCost = qgis::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')" ),
64  QgsProcessingParameterNumber::Double, 0, false, 0 ) );
65 
66  std::unique_ptr< QgsProcessingParameterBoolean > includeBounds = qgis::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 = qgis::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 = qgis::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 
81 QVariantMap QgsServiceAreaFromLayerAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
82 {
83  loadCommonParams( parameters, context, feedback );
84 
85  std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
86  if ( !startPoints )
87  throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
88 
89  // use older deprecated travel cost style if specified, to maintain old api
90  const bool useOldTravelCost = parameters.value( QStringLiteral( "TRAVEL_COST" ) ).isValid();
91  double travelCost = parameterAsDouble( parameters, useOldTravelCost ? QStringLiteral( "TRAVEL_COST" ) : QStringLiteral( "TRAVEL_COST2" ), context );
92 
93  int strategy = parameterAsInt( parameters, QStringLiteral( "STRATEGY" ), context );
94  if ( strategy && !useOldTravelCost )
95  travelCost *= mMultiplier;
96 
97  bool includeBounds = true; // default to true to maintain 3.0 API
98  if ( parameters.contains( QStringLiteral( "INCLUDE_BOUNDS" ) ) )
99  {
100  includeBounds = parameterAsBool( parameters, QStringLiteral( "INCLUDE_BOUNDS" ), context );
101  }
102 
103  QVector< QgsPointXY > points;
104  QHash< int, QgsAttributes > sourceAttributes;
105  loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
106 
107  feedback->pushInfo( QObject::tr( "Building graph…" ) );
108  QVector< QgsPointXY > snappedPoints;
109  mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
110 
111  feedback->pushInfo( QObject::tr( "Calculating service areas…" ) );
112  QgsGraph *graph = mBuilder->graph();
113 
114  QgsFields fields = startPoints->fields();
115  fields.append( QgsField( QStringLiteral( "type" ), QVariant::String ) );
116  fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
117 
118  QString pointsSinkId;
119  std::unique_ptr< QgsFeatureSink > pointsSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, pointsSinkId, fields,
120  QgsWkbTypes::MultiPoint, mNetwork->sourceCrs() ) );
121 
122  QString linesSinkId;
123  std::unique_ptr< QgsFeatureSink > linesSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_LINES" ), context, linesSinkId, fields,
124  QgsWkbTypes::MultiLineString, mNetwork->sourceCrs() ) );
125 
126  int idxStart;
127  QString origPoint;
128  QVector< int > tree;
129  QVector< double > costs;
130 
131  int inboundEdgeIndex;
132  double startVertexCost, endVertexCost;
133  QgsPointXY startPoint, endPoint;
134  QgsGraphEdge edge;
135 
136  QgsFeature feat;
137  QgsAttributes attributes;
138 
139  int step = snappedPoints.size() > 0 ? 100.0 / snappedPoints.size() : 1;
140  for ( int i = 0; i < snappedPoints.size(); i++ )
141  {
142  if ( feedback->isCanceled() )
143  {
144  break;
145  }
146 
147  idxStart = graph->findVertex( snappedPoints.at( i ) );
148  origPoint = points.at( i ).toString();
149 
150  QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
151 
152  QgsMultiPointXY areaPoints;
153  QgsMultiPolylineXY lines;
154  QSet< int > vertices;
155 
156  for ( int j = 0; j < costs.size(); j++ )
157  {
158  inboundEdgeIndex = tree.at( j );
159 
160  if ( inboundEdgeIndex == -1 && j != idxStart )
161  {
162  // unreachable vertex
163  continue;
164  }
165 
166  startVertexCost = costs.at( j );
167  if ( startVertexCost > travelCost )
168  {
169  // vertex is too expensive, discard
170  continue;
171  }
172 
173  vertices.insert( j );
174  startPoint = graph->vertex( j ).point();
175 
176  // find all edges coming from this vertex
177  const QList< int > outgoingEdges = graph->vertex( j ).outgoingEdges() ;
178  for ( int edgeId : outgoingEdges )
179  {
180  edge = graph->edge( edgeId );
181  endVertexCost = startVertexCost + edge.cost( 0 ).toDouble();
182  endPoint = graph->vertex( edge.toVertex() ).point();
183  if ( endVertexCost <= travelCost )
184  {
185  // end vertex is cheap enough to include
186  vertices.insert( edge.toVertex() );
187  lines.push_back( QgsPolylineXY() << startPoint << endPoint );
188  }
189  else
190  {
191  // travelCost sits somewhere on this edge, interpolate position
192  QgsPointXY interpolatedEndPoint = QgsGeometryUtils::interpolatePointOnLineByValue( startPoint.x(), startPoint.y(), startVertexCost,
193  endPoint.x(), endPoint.y(), endVertexCost, travelCost );
194 
195  areaPoints.push_back( interpolatedEndPoint );
196  lines.push_back( QgsPolylineXY() << startPoint << interpolatedEndPoint );
197  }
198  } // edges
199  } // costs
200 
201  // convert to list and sort to maintain same order of points between algorithm runs
202  QList< int > verticesList = qgis::setToList( vertices );
203  areaPoints.reserve( verticesList.size() );
204  std::sort( verticesList.begin(), verticesList.end() );
205  for ( int v : verticesList )
206  {
207  areaPoints.push_back( graph->vertex( v ).point() );
208  }
209 
210  if ( pointsSink )
211  {
212  QgsGeometry geomPoints = QgsGeometry::fromMultiPointXY( areaPoints );
213  feat.setGeometry( geomPoints );
214  attributes = sourceAttributes.value( i + 1 );
215  attributes << QStringLiteral( "within" ) << origPoint;
216  feat.setAttributes( attributes );
217  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
218 
219  if ( includeBounds )
220  {
221  QgsMultiPointXY upperBoundary, lowerBoundary;
222  QVector< int > nodes;
223  nodes.reserve( costs.size() );
224 
225  int vertexId;
226  for ( int v = 0; v < costs.size(); v++ )
227  {
228  if ( costs.at( v ) > travelCost && tree.at( v ) != -1 )
229  {
230  vertexId = graph->edge( tree.at( v ) ).fromVertex();
231  if ( costs.at( vertexId ) <= travelCost )
232  {
233  nodes.push_back( v );
234  }
235  }
236  } // costs
237 
238  for ( int n : qgis::as_const( nodes ) )
239  {
240  upperBoundary.push_back( graph->vertex( graph->edge( tree.at( n ) ).toVertex() ).point() );
241  lowerBoundary.push_back( graph->vertex( graph->edge( tree.at( n ) ).fromVertex() ).point() );
242  } // nodes
243 
244  QgsGeometry geomUpper = QgsGeometry::fromMultiPointXY( upperBoundary );
245  QgsGeometry geomLower = QgsGeometry::fromMultiPointXY( lowerBoundary );
246 
247  feat.setGeometry( geomUpper );
248  attributes = sourceAttributes.value( i + 1 );
249  attributes << QStringLiteral( "upper" ) << origPoint;
250  feat.setAttributes( attributes );
251  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
252 
253  feat.setGeometry( geomLower );
254  attributes = sourceAttributes.value( i + 1 );
255  attributes << QStringLiteral( "lower" ) << origPoint;
256  feat.setAttributes( attributes );
257  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
258  } // includeBounds
259  }
260 
261  if ( linesSink )
262  {
263  QgsGeometry geomLines = QgsGeometry::fromMultiPolylineXY( lines );
264  feat.setGeometry( geomLines );
265  attributes = sourceAttributes.value( i + 1 );
266  attributes << QStringLiteral( "lines" ) << origPoint;
267  feat.setAttributes( attributes );
268  linesSink->addFeature( feat, QgsFeatureSink::FastInsert );
269  }
270 
271  feedback->setProgress( i * step );
272  } // snappedPoints
273 
274  QVariantMap outputs;
275  if ( pointsSink )
276  {
277  outputs.insert( QStringLiteral( "OUTPUT" ), pointsSinkId );
278  }
279  if ( linesSink )
280  {
281  outputs.insert( QStringLiteral( "OUTPUT_LINES" ), linesSinkId );
282  }
283 
284  return outputs;
285 }
286 
QgsFeedback::setProgress
void setProgress(double progress)
Sets the current progress for the feedback object.
Definition: qgsfeedback.h:75
QgsProcessingParameterNumber::Double
@ Double
Double/float values.
Definition: qgsprocessingparameters.h:1846
QgsPointXY::y
double y
Definition: qgspointxy.h:48
QgsGraph
Mathematical graph representation.
Definition: qgsgraph.h:141
QgsGraphVertex::outgoingEdges
QgsGraphEdgeIds outgoingEdges() const
Returns outgoing edge ids, i.e.
Definition: qgsgraph.cpp:109
QgsGraphVertex::point
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:114
QgsGraphEdge
This class implements a graph edge.
Definition: qgsgraph.h:43
QgsProcessingParameterNumber
Definition: qgsprocessingparameters.h:1838
QgsProcessingFeedback
Definition: qgsprocessingfeedback.h:37
QgsGeometry::fromMultiPolylineXY
static QgsGeometry fromMultiPolylineXY(const QgsMultiPolylineXY &multiline)
Creates a new geometry from a QgsMultiPolylineXY object.
Definition: qgsgeometry.cpp:209
QgsProcessingFeedback::pushInfo
virtual void pushInfo(const QString &info)
Pushes a general informational message from the algorithm.
Definition: qgsprocessingfeedback.cpp:48
QgsPolylineXY
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
Definition: qgsgeometry.h:50
QgsFields
Definition: qgsfields.h:44
QgsProcessingParameterDefinition::FlagAdvanced
@ FlagAdvanced
Parameter is an advanced parameter which should be hidden from users by default.
Definition: qgsprocessingparameters.h:419
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
QgsMultiPointXY
QVector< QgsPointXY > QgsMultiPointXY
A collection of QgsPoints that share a common collection of attributes.
Definition: qgsgeometry.h:80
QgsGeometryUtils::interpolatePointOnLineByValue
static QgsPointXY interpolatePointOnLineByValue(double x1, double y1, double v1, double x2, double y2, double v2, double value)
Interpolates the position of a point along the line from (x1, y1) to (x2, y2).
Definition: qgsgeometryutils.cpp:1403
QgsWkbTypes::MultiLineString
@ MultiLineString
Definition: qgswkbtypes.h:76
QgsGraph::edge
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:50
QgsGraphEdge::cost
QVariant cost(int strategyIndex) const
Returns edge cost calculated using specified strategy.
Definition: qgsgraph.cpp:78
QgsFeature::setGeometry
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
Definition: qgsfeature.cpp:137
QgsGeometry::fromMultiPointXY
static QgsGeometry fromMultiPointXY(const QgsMultiPointXY &multipoint)
Creates a new geometry from a QgsMultiPointXY object.
Definition: qgsgeometry.cpp:199
QgsProcessingContext
Definition: qgsprocessingcontext.h:43
qgsalgorithmserviceareafromlayer.h
QgsGraphEdge::toVertex
int toVertex() const
Returns the index of the vertex at the end of this edge.
Definition: qgsgraph.cpp:93
QgsGraph::findVertex
int findVertex(const QgsPointXY &pt) const
Find vertex by associated point.
Definition: qgsgraph.cpp:65
QgsMultiPolylineXY
QVector< QgsPolylineXY > QgsMultiPolylineXY
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:84
qgsgeometryutils.h
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
QgsProcessingParameterDefinition::FlagHidden
@ FlagHidden
Parameter is hidden and should not be shown to users.
Definition: qgsprocessingparameters.h:420
QgsWkbTypes::MultiPoint
@ MultiPoint
Definition: qgswkbtypes.h:75
QgsPointXY::x
double x
Definition: qgspointxy.h:47
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
QgsField
Definition: qgsfield.h:49