Branch data Line data Source code
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 : :
18 : : #include "qgsalgorithmserviceareafromlayer.h"
19 : :
20 : : #include "qgsgeometryutils.h"
21 : : #include "qgsgraphanalyzer.h"
22 : :
23 : : ///@cond PRIVATE
24 : :
25 : 0 : QString QgsServiceAreaFromLayerAlgorithm::name() const
26 : : {
27 : 0 : return QStringLiteral( "serviceareafromlayer" );
28 : : }
29 : :
30 : 0 : QString QgsServiceAreaFromLayerAlgorithm::displayName() const
31 : : {
32 : 0 : return QObject::tr( "Service area (from layer)" );
33 : : }
34 : :
35 : 0 : QStringList QgsServiceAreaFromLayerAlgorithm::tags() const
36 : : {
37 : 0 : return QObject::tr( "network,service,area,shortest,fastest" ).split( ',' );
38 : 0 : }
39 : :
40 : 0 : QString QgsServiceAreaFromLayerAlgorithm::shortHelpString() const
41 : : {
42 : 0 : 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 : 0 : QgsServiceAreaFromLayerAlgorithm *QgsServiceAreaFromLayerAlgorithm::createInstance() const
50 : : {
51 : 0 : return new QgsServiceAreaFromLayerAlgorithm();
52 : : }
53 : :
54 : 0 : void QgsServiceAreaFromLayerAlgorithm::initAlgorithm( const QVariantMap & )
55 : : {
56 : 0 : addCommonParams();
57 : 0 : addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "START_POINTS" ), QObject::tr( "Vector layer with start points" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
58 : :
59 : 0 : 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 : 0 : travelCost->setFlags( travelCost->flags() | QgsProcessingParameterDefinition::FlagHidden );
61 : 0 : addParameter( travelCost.release() );
62 : :
63 : 0 : addParameter( new QgsProcessingParameterNumber( QStringLiteral( "TRAVEL_COST2" ), QObject::tr( "Travel cost (distance for 'Shortest', time for 'Fastest')" ),
64 : 0 : QgsProcessingParameterNumber::Double, 0, false, 0 ) );
65 : :
66 : 0 : std::unique_ptr< QgsProcessingParameterBoolean > includeBounds = std::make_unique< QgsProcessingParameterBoolean >( QStringLiteral( "INCLUDE_BOUNDS" ), QObject::tr( "Include upper/lower bound points" ), false, true );
67 : 0 : includeBounds->setFlags( includeBounds->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
68 : 0 : addParameter( includeBounds.release() );
69 : :
70 : 0 : std::unique_ptr< QgsProcessingParameterFeatureSink > outputLines = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT_LINES" ), QObject::tr( "Service area (lines)" ),
71 : 0 : QgsProcessing::TypeVectorLine, QVariant(), true );
72 : 0 : outputLines->setCreateByDefault( true );
73 : 0 : addParameter( outputLines.release() );
74 : :
75 : 0 : std::unique_ptr< QgsProcessingParameterFeatureSink > outputPoints = std::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT" ), QObject::tr( "Service area (boundary nodes)" ),
76 : 0 : QgsProcessing::TypeVectorPoint, QVariant(), true );
77 : 0 : outputPoints->setCreateByDefault( false );
78 : 0 : addParameter( outputPoints.release() );
79 : 0 : }
80 : :
81 : 0 : QVariantMap QgsServiceAreaFromLayerAlgorithm::processAlgorithm( const QVariantMap ¶meters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
82 : : {
83 : 0 : loadCommonParams( parameters, context, feedback );
84 : :
85 : 0 : std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
86 : 0 : if ( !startPoints )
87 : 0 : throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
88 : :
89 : : // use older deprecated travel cost style if specified, to maintain old api
90 : 0 : const bool useOldTravelCost = parameters.value( QStringLiteral( "TRAVEL_COST" ) ).isValid();
91 : 0 : double travelCost = parameterAsDouble( parameters, useOldTravelCost ? QStringLiteral( "TRAVEL_COST" ) : QStringLiteral( "TRAVEL_COST2" ), context );
92 : :
93 : 0 : int strategy = parameterAsInt( parameters, QStringLiteral( "STRATEGY" ), context );
94 : 0 : if ( strategy && !useOldTravelCost )
95 : 0 : travelCost *= mMultiplier;
96 : :
97 : 0 : bool includeBounds = true; // default to true to maintain 3.0 API
98 : 0 : if ( parameters.contains( QStringLiteral( "INCLUDE_BOUNDS" ) ) )
99 : : {
100 : 0 : includeBounds = parameterAsBool( parameters, QStringLiteral( "INCLUDE_BOUNDS" ), context );
101 : 0 : }
102 : :
103 : 0 : QVector< QgsPointXY > points;
104 : 0 : QHash< int, QgsAttributes > sourceAttributes;
105 : 0 : loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
106 : :
107 : 0 : feedback->pushInfo( QObject::tr( "Building graph…" ) );
108 : 0 : QVector< QgsPointXY > snappedPoints;
109 : 0 : mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
110 : :
111 : 0 : feedback->pushInfo( QObject::tr( "Calculating service areas…" ) );
112 : 0 : QgsGraph *graph = mBuilder->graph();
113 : :
114 : 0 : QgsFields fields = startPoints->fields();
115 : 0 : fields.append( QgsField( QStringLiteral( "type" ), QVariant::String ) );
116 : 0 : fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
117 : :
118 : 0 : QString pointsSinkId;
119 : 0 : std::unique_ptr< QgsFeatureSink > pointsSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, pointsSinkId, fields,
120 : 0 : QgsWkbTypes::MultiPoint, mNetwork->sourceCrs() ) );
121 : :
122 : 0 : QString linesSinkId;
123 : 0 : std::unique_ptr< QgsFeatureSink > linesSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_LINES" ), context, linesSinkId, fields,
124 : 0 : QgsWkbTypes::MultiLineString, mNetwork->sourceCrs() ) );
125 : :
126 : : int idxStart;
127 : 0 : QString origPoint;
128 : 0 : QVector< int > tree;
129 : 0 : QVector< double > costs;
130 : :
131 : : int inboundEdgeIndex;
132 : : double startVertexCost, endVertexCost;
133 : 0 : QgsPointXY startPoint, endPoint;
134 : 0 : QgsGraphEdge edge;
135 : :
136 : 0 : QgsFeature feat;
137 : 0 : QgsAttributes attributes;
138 : :
139 : 0 : int step = snappedPoints.size() > 0 ? 100.0 / snappedPoints.size() : 1;
140 : 0 : for ( int i = 0; i < snappedPoints.size(); i++ )
141 : : {
142 : 0 : if ( feedback->isCanceled() )
143 : : {
144 : 0 : break;
145 : : }
146 : :
147 : 0 : idxStart = graph->findVertex( snappedPoints.at( i ) );
148 : 0 : origPoint = points.at( i ).toString();
149 : :
150 : 0 : QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
151 : :
152 : 0 : QgsMultiPointXY areaPoints;
153 : 0 : QgsMultiPolylineXY lines;
154 : 0 : QSet< int > vertices;
155 : :
156 : 0 : for ( int j = 0; j < costs.size(); j++ )
157 : : {
158 : 0 : inboundEdgeIndex = tree.at( j );
159 : :
160 : 0 : if ( inboundEdgeIndex == -1 && j != idxStart )
161 : : {
162 : : // unreachable vertex
163 : 0 : continue;
164 : : }
165 : :
166 : 0 : startVertexCost = costs.at( j );
167 : 0 : if ( startVertexCost > travelCost )
168 : : {
169 : : // vertex is too expensive, discard
170 : 0 : continue;
171 : : }
172 : :
173 : 0 : vertices.insert( j );
174 : 0 : startPoint = graph->vertex( j ).point();
175 : :
176 : : // find all edges coming from this vertex
177 : 0 : const QList< int > outgoingEdges = graph->vertex( j ).outgoingEdges() ;
178 : 0 : for ( int edgeId : outgoingEdges )
179 : : {
180 : 0 : edge = graph->edge( edgeId );
181 : 0 : endVertexCost = startVertexCost + edge.cost( 0 ).toDouble();
182 : 0 : endPoint = graph->vertex( edge.toVertex() ).point();
183 : 0 : if ( endVertexCost <= travelCost )
184 : : {
185 : : // end vertex is cheap enough to include
186 : 0 : vertices.insert( edge.toVertex() );
187 : 0 : lines.push_back( QgsPolylineXY() << startPoint << endPoint );
188 : 0 : }
189 : : else
190 : : {
191 : : // travelCost sits somewhere on this edge, interpolate position
192 : 0 : QgsPointXY interpolatedEndPoint = QgsGeometryUtils::interpolatePointOnLineByValue( startPoint.x(), startPoint.y(), startVertexCost,
193 : 0 : endPoint.x(), endPoint.y(), endVertexCost, travelCost );
194 : :
195 : 0 : areaPoints.push_back( interpolatedEndPoint );
196 : 0 : lines.push_back( QgsPolylineXY() << startPoint << interpolatedEndPoint );
197 : : }
198 : : } // edges
199 : 0 : } // costs
200 : :
201 : : // convert to list and sort to maintain same order of points between algorithm runs
202 : 0 : QList< int > verticesList = qgis::setToList( vertices );
203 : 0 : areaPoints.reserve( verticesList.size() );
204 : 0 : std::sort( verticesList.begin(), verticesList.end() );
205 : 0 : for ( int v : verticesList )
206 : : {
207 : 0 : areaPoints.push_back( graph->vertex( v ).point() );
208 : : }
209 : :
210 : 0 : if ( pointsSink )
211 : : {
212 : 0 : QgsGeometry geomPoints = QgsGeometry::fromMultiPointXY( areaPoints );
213 : 0 : feat.setGeometry( geomPoints );
214 : 0 : attributes = sourceAttributes.value( i + 1 );
215 : 0 : attributes << QStringLiteral( "within" ) << origPoint;
216 : 0 : feat.setAttributes( attributes );
217 : 0 : pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
218 : :
219 : 0 : if ( includeBounds )
220 : : {
221 : 0 : QgsMultiPointXY upperBoundary, lowerBoundary;
222 : 0 : QVector< int > nodes;
223 : 0 : nodes.reserve( costs.size() );
224 : :
225 : : int vertexId;
226 : 0 : for ( int v = 0; v < costs.size(); v++ )
227 : : {
228 : 0 : if ( costs.at( v ) > travelCost && tree.at( v ) != -1 )
229 : : {
230 : 0 : vertexId = graph->edge( tree.at( v ) ).fromVertex();
231 : 0 : if ( costs.at( vertexId ) <= travelCost )
232 : : {
233 : 0 : nodes.push_back( v );
234 : 0 : }
235 : 0 : }
236 : 0 : } // costs
237 : :
238 : 0 : for ( int n : std::as_const( nodes ) )
239 : : {
240 : 0 : upperBoundary.push_back( graph->vertex( graph->edge( tree.at( n ) ).toVertex() ).point() );
241 : 0 : lowerBoundary.push_back( graph->vertex( graph->edge( tree.at( n ) ).fromVertex() ).point() );
242 : : } // nodes
243 : :
244 : 0 : QgsGeometry geomUpper = QgsGeometry::fromMultiPointXY( upperBoundary );
245 : 0 : QgsGeometry geomLower = QgsGeometry::fromMultiPointXY( lowerBoundary );
246 : :
247 : 0 : feat.setGeometry( geomUpper );
248 : 0 : attributes = sourceAttributes.value( i + 1 );
249 : 0 : attributes << QStringLiteral( "upper" ) << origPoint;
250 : 0 : feat.setAttributes( attributes );
251 : 0 : pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
252 : :
253 : 0 : feat.setGeometry( geomLower );
254 : 0 : attributes = sourceAttributes.value( i + 1 );
255 : 0 : attributes << QStringLiteral( "lower" ) << origPoint;
256 : 0 : feat.setAttributes( attributes );
257 : 0 : pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
258 : 0 : } // includeBounds
259 : 0 : }
260 : :
261 : 0 : if ( linesSink )
262 : : {
263 : 0 : QgsGeometry geomLines = QgsGeometry::fromMultiPolylineXY( lines );
264 : 0 : feat.setGeometry( geomLines );
265 : 0 : attributes = sourceAttributes.value( i + 1 );
266 : 0 : attributes << QStringLiteral( "lines" ) << origPoint;
267 : 0 : feat.setAttributes( attributes );
268 : 0 : linesSink->addFeature( feat, QgsFeatureSink::FastInsert );
269 : 0 : }
270 : :
271 : 0 : feedback->setProgress( i * step );
272 : 0 : } // snappedPoints
273 : :
274 : 0 : QVariantMap outputs;
275 : 0 : if ( pointsSink )
276 : : {
277 : 0 : outputs.insert( QStringLiteral( "OUTPUT" ), pointsSinkId );
278 : 0 : }
279 : 0 : if ( linesSink )
280 : : {
281 : 0 : outputs.insert( QStringLiteral( "OUTPUT_LINES" ), linesSinkId );
282 : 0 : }
283 : :
284 : 0 : return outputs;
285 : 0 : }
286 : :
287 : : ///@endcond
|
