QGIS API Documentation  3.14.0-Pi (9f7028fd23)
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 
25 QString QgsServiceAreaFromPointAlgorithm::name() const
26 {
27  return QStringLiteral( "serviceareafrompoint" );
28 }
29 
30 QString QgsServiceAreaFromPointAlgorithm::displayName() const
31 {
32  return QObject::tr( "Service area (from point)" );
33 }
34 
35 QStringList QgsServiceAreaFromPointAlgorithm::tags() const
36 {
37  return QObject::tr( "network,service,area,shortest,fastest" ).split( ',' );
38 }
39 
40 QString 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 
49 QgsServiceAreaFromPointAlgorithm *QgsServiceAreaFromPointAlgorithm::createInstance() const
50 {
51  return new QgsServiceAreaFromPointAlgorithm();
52 }
53 
54 void 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 = 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 QgsServiceAreaFromPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
82 {
83  loadCommonParams( parameters, context, feedback );
84 
85  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  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  QgsGraph *graph = mBuilder->graph();
107  int idxStart = graph->findVertex( snappedPoints[0] );
108 
109  QVector< int > tree;
110  QVector< double > costs;
111  QgsGraphAnalyzer::dijkstra( graph, 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 ( 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  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 ( 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  QgsGeometry geomPoints = QgsGeometry::fromMultiPointXY( points );
195  feat.setGeometry( geomPoints );
196  feat.setAttributes( QgsAttributes() << QStringLiteral( "within" ) << startPoint.toString() );
197  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
198 
199  if ( includeBounds )
200  {
201  QgsMultiPointXY upperBoundary, lowerBoundary;
202  QVector< int > nodes;
203 
204  int vertexId;
205  for ( int i = 0; i < costs.size(); i++ )
206  {
207  if ( costs.at( i ) > travelCost && tree.at( i ) != -1 )
208  {
209  vertexId = graph->edge( tree.at( i ) ).fromVertex();
210  if ( costs.at( vertexId ) <= travelCost )
211  {
212  nodes.push_back( i );
213  }
214  }
215  } // costs
216 
217  for ( int i : nodes )
218  {
219  upperBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).toVertex() ).point() );
220  lowerBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).fromVertex() ).point() );
221  } // nodes
222 
223  QgsGeometry geomUpper = QgsGeometry::fromMultiPointXY( upperBoundary );
224  QgsGeometry geomLower = QgsGeometry::fromMultiPointXY( lowerBoundary );
225 
226  feat.setGeometry( geomUpper );
227  feat.setAttributes( QgsAttributes() << QStringLiteral( "upper" ) << startPoint.toString() );
228  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
229 
230  feat.setGeometry( geomLower );
231  feat.setAttributes( QgsAttributes() << QStringLiteral( "lower" ) << startPoint.toString() );
232  pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
233  } // includeBounds
234  }
235 
236  QString linesSinkId;
237  std::unique_ptr< QgsFeatureSink > linesSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_LINES" ), context, linesSinkId, fields,
238  QgsWkbTypes::MultiLineString, mNetwork->sourceCrs() ) );
239 
240  if ( linesSink )
241  {
242  outputs.insert( QStringLiteral( "OUTPUT_LINES" ), linesSinkId );
243  QgsGeometry geomLines = QgsGeometry::fromMultiPolylineXY( lines );
244  feat.setGeometry( geomLines );
245  feat.setAttributes( QgsAttributes() << QStringLiteral( "lines" ) << startPoint.toString() );
246  linesSink->addFeature( feat, QgsFeatureSink::FastInsert );
247  }
248 
249  return outputs;
250 }
251 
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
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
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
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
QgsProcessingParameterPoint
Definition: qgsprocessingparameters.h:1535
qgsgeometryutils.h
QgsPointXY
Definition: qgspointxy.h:43
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
qgsalgorithmserviceareafrompoint.h
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
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