Skip to content

Commit bbc3330

Browse files
alexbruyalexbruy
authoredAug 1, 2018
Merge pull request #7505 from alexbruy/network-analysis
[processing] port shortest path algs to C++
·
ltr-3_40final-3_4_0
2 parents 9792b56 + 7539415 commit bbc3330

17 files changed

+1646
-856
lines changed
 

‎images/images.qrc

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -98,6 +98,7 @@
9898
<file>themes/default/algorithms/mAlgorithmMergeLayers.svg</file>
9999
<file>themes/default/algorithms/mAlgorithmMultiToSingle.svg</file>
100100
<file>themes/default/algorithms/mAlgorithmNearestNeighbour.svg</file>
101+
<file>themes/default/algorithms/mAlgorithmNetworkAnalysis.svg</file>
101102
<file>themes/default/algorithms/mAlgorithmPolygonToLine.svg</file>
102103
<file>themes/default/algorithms/mAlgorithmRandomPointsWithinPolygon.svg</file>
103104
<file>themes/default/algorithms/mAlgorithmRandomPointsWithinExtent.svg</file>

‎images/themes/default/algorithms/mAlgorithmNetworkAnalysis.svg

Lines changed: 798 additions & 0 deletions
Loading

‎python/plugins/processing/algs/qgis/QgisAlgorithmProvider.py

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -125,9 +125,6 @@
125125
from .SetRasterStyle import SetRasterStyle
126126
from .SetVectorStyle import SetVectorStyle
127127
from .SetZValue import SetZValue
128-
from .ShortestPathLayerToPoint import ShortestPathLayerToPoint
129-
from .ShortestPathPointToLayer import ShortestPathPointToLayer
130-
from .ShortestPathPointToPoint import ShortestPathPointToPoint
131128
from .SingleSidedBuffer import SingleSidedBuffer
132129
from .Slope import Slope
133130
from .SnapGeometries import SnapGeometriesToLayer
@@ -239,9 +236,6 @@ def getAlgs(self):
239236
SetRasterStyle(),
240237
SetVectorStyle(),
241238
SetZValue(),
242-
ShortestPathLayerToPoint(),
243-
ShortestPathPointToLayer(),
244-
ShortestPathPointToPoint(),
245239
SingleSidedBuffer(),
246240
Slope(),
247241
SnapGeometriesToLayer(),

‎python/plugins/processing/algs/qgis/ShortestPathLayerToPoint.py

Lines changed: 0 additions & 295 deletions
This file was deleted.

‎python/plugins/processing/algs/qgis/ShortestPathPointToLayer.py

Lines changed: 0 additions & 295 deletions
This file was deleted.

‎python/plugins/processing/algs/qgis/ShortestPathPointToPoint.py

Lines changed: 0 additions & 255 deletions
This file was deleted.

‎python/plugins/processing/tests/testdata/qgis_algorithm_tests.yaml

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2977,7 +2977,7 @@ tests:
29772977
name: expected/join_attribute_table_subset.gml
29782978
type: vector
29792979

2980-
- algorithm: qgis:shortestpathpointtopoint
2980+
- algorithm: native:shortestpathpointtopoint
29812981
name: Shortest path (point to point, shortest route)
29822982
params:
29832983
DEFAULT_DIRECTION: 2
@@ -3006,7 +3006,7 @@ tests:
30063006
start: skip
30073007
end: skip
30083008

3009-
- algorithm: qgis:shortestpathpointtopoint
3009+
- algorithm: native:shortestpathpointtopoint
30103010
name: Shortest path (point to point, fastest route)
30113011
params:
30123012
DEFAULT_DIRECTION: 2
@@ -3036,7 +3036,7 @@ tests:
30363036
start: skip
30373037
end: skip
30383038

3039-
- algorithm: qgis:shortestpathlayertopoint
3039+
- algorithm: native:shortestpathlayertopoint
30403040
name: Shortest path layer to point
30413041
params:
30423042
DEFAULT_DIRECTION: 2
@@ -3066,7 +3066,7 @@ tests:
30663066
start: skip
30673067
end: skip
30683068

3069-
- algorithm: qgis:shortestpathpointtolayer
3069+
- algorithm: native:shortestpathpointtolayer
30703070
name: Shortest path point to layer
30713071
params:
30723072
DEFAULT_DIRECTION: 2
@@ -5799,7 +5799,7 @@ tests:
57995799
OUTPUT:
58005800
name: expected/dbscan_multiple_clusters.gml
58015801
type: vector
5802-
5802+
58035803
- algorithm: qgis:rastersampling
58045804
name: Single band raster
58055805
params:

‎src/analysis/CMakeLists.txt

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,9 @@ SET(QGIS_ANALYSIS_SRCS
7777
processing/qgsalgorithmrotate.cpp
7878
processing/qgsalgorithmsaveselectedfeatures.cpp
7979
processing/qgsalgorithmsegmentize.cpp
80+
processing/qgsalgorithmshortestpathlayertopoint.cpp
81+
processing/qgsalgorithmshortestpathpointtolayer.cpp
82+
processing/qgsalgorithmshortestpathpointtopoint.cpp
8083
processing/qgsalgorithmsimplify.cpp
8184
processing/qgsalgorithmsmooth.cpp
8285
processing/qgsalgorithmsnaptogrid.cpp
@@ -95,6 +98,8 @@ SET(QGIS_ANALYSIS_SRCS
9598
processing/qgsalgorithmwedgebuffers.cpp
9699
processing/qgsalgorithmzonalhistogram.cpp
97100

101+
processing/qgsalgorithmnetworkanalysisbase.cpp
102+
98103
processing/qgsnativealgorithms.cpp
99104
processing/qgsoverlayutils.cpp
100105
processing/qgsrasteranalysisutils.cpp

‎src/analysis/processing/qgsalgorithmnetworkanalysisbase.cpp

Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
/***************************************************************************
2+
qgsalgorithmnetworkanalysisbase.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 "qgsalgorithmnetworkanalysisbase.h"
19+
20+
#include "qgsgraphanalyzer.h"
21+
#include "qgsnetworkspeedstrategy.h"
22+
#include "qgsnetworkdistancestrategy.h"
23+
24+
///@cond PRIVATE
25+
26+
//
27+
// QgsNetworkAnalysisAlgorithmBase
28+
//
29+
30+
QString QgsNetworkAnalysisAlgorithmBase::group() const
31+
{
32+
return QObject::tr( "Network analysis" );
33+
}
34+
35+
QString QgsNetworkAnalysisAlgorithmBase::groupId() const
36+
{
37+
return QStringLiteral( "networkanalysis" );
38+
}
39+
40+
void QgsNetworkAnalysisAlgorithmBase::addCommonParams()
41+
{
42+
addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "INPUT" ), QObject::tr( "Vector layer representing network" ), QList< int >() << QgsProcessing::TypeVectorLine ) );
43+
addParameter( new QgsProcessingParameterEnum( QStringLiteral( "STRATEGY" ), QObject::tr( "Path type to calculate" ), QStringList() << QObject::tr( "Shortest" ) << QObject::tr( "Fastest" ), false, 0 ) );
44+
45+
std::unique_ptr< QgsProcessingParameterField > directionField = qgis::make_unique< QgsProcessingParameterField >( QStringLiteral( "DIRECTION_FIELD" ),
46+
QObject::tr( "Direction field" ), QVariant(), QStringLiteral( "INPUT" ), QgsProcessingParameterField::Any, false, true );
47+
directionField->setFlags( directionField->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
48+
addParameter( directionField.release() );
49+
50+
std::unique_ptr< QgsProcessingParameterString > forwardValue = qgis::make_unique< QgsProcessingParameterString >( QStringLiteral( "VALUE_FORWARD" ),
51+
QObject::tr( "Value for forward direction" ), QVariant(), false, true );
52+
forwardValue->setFlags( forwardValue->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
53+
addParameter( forwardValue.release() );
54+
55+
std::unique_ptr< QgsProcessingParameterString > backwardValue = qgis::make_unique< QgsProcessingParameterString >( QStringLiteral( "VALUE_BACKWARD" ),
56+
QObject::tr( "Value for backward direction" ), QVariant(), false, true );
57+
backwardValue->setFlags( backwardValue->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
58+
addParameter( backwardValue.release() );
59+
60+
std::unique_ptr< QgsProcessingParameterString > bothValue = qgis::make_unique< QgsProcessingParameterString >( QStringLiteral( "VALUE_BOTH" ),
61+
QObject::tr( "Value for both directions" ), QVariant(), false, true );
62+
bothValue->setFlags( bothValue->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
63+
addParameter( bothValue.release() );
64+
65+
std::unique_ptr< QgsProcessingParameterEnum > directionValue = qgis::make_unique< QgsProcessingParameterEnum >( QStringLiteral( "DEFAULT_DIRECTION" ),
66+
QObject::tr( "Default direction" ), QStringList() << QObject::tr( "Forward direction" ) << QObject::tr( "Backward direction" ) << QObject::tr( "Both directions" ), false, 2 );
67+
directionValue->setFlags( directionValue->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
68+
addParameter( directionValue.release() );
69+
70+
std::unique_ptr< QgsProcessingParameterField > speedField = qgis::make_unique< QgsProcessingParameterField >( QStringLiteral( "SPEED_FIELD" ),
71+
QObject::tr( "Speed field" ), QVariant(), QStringLiteral( "INPUT" ), QgsProcessingParameterField::Numeric, false, true );
72+
speedField->setFlags( speedField->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
73+
addParameter( speedField.release() );
74+
75+
std::unique_ptr< QgsProcessingParameterNumber > speed = qgis::make_unique< QgsProcessingParameterNumber >( QStringLiteral( "DEFAULT_SPEED" ), QObject::tr( "Default speed (km/h)" ), QgsProcessingParameterNumber::Double, 50, false, 0 );
76+
speed->setFlags( speed->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
77+
addParameter( speed.release() );
78+
79+
std::unique_ptr< QgsProcessingParameterNumber > tolerance = qgis::make_unique < QgsProcessingParameterDistance >( QStringLiteral( "TOLERANCE" ), QObject::tr( "Topology tolerance" ), 0, QStringLiteral( "INPUT" ), false, 0 );
80+
tolerance->setFlags( tolerance->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
81+
addParameter( tolerance.release() );
82+
}
83+
84+
void QgsNetworkAnalysisAlgorithmBase::loadCommonParams( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
85+
{
86+
Q_UNUSED( feedback );
87+
88+
mNetwork.reset( parameterAsSource( parameters, QStringLiteral( "INPUT" ), context ) );
89+
if ( !mNetwork )
90+
throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "INPUT" ) ) );
91+
92+
int strategy = parameterAsInt( parameters, QStringLiteral( "STRATEGY" ), context );
93+
QString directionFieldName = parameterAsString( parameters, QStringLiteral( "DIRECTION_FIELD" ), context );
94+
QString forwardValue = parameterAsString( parameters, QStringLiteral( "VALUE_FORWARD" ), context );
95+
QString backwardValue = parameterAsString( parameters, QStringLiteral( "VALUE_BACKWARD" ), context );
96+
QString bothValue = parameterAsString( parameters, QStringLiteral( "VALUE_BOTH" ), context );
97+
QgsVectorLayerDirector::Direction defaultDirection = static_cast< QgsVectorLayerDirector::Direction>( parameterAsInt( parameters, QStringLiteral( "DEFAULT_DIRECTION" ), context ) );
98+
QString speedFieldName = parameterAsString( parameters, QStringLiteral( "SPEED_FIELD" ), context );
99+
double defaultSpeed = parameterAsDouble( parameters, QStringLiteral( "DEFAULT_SPEED" ), context );
100+
double tolerance = parameterAsDouble( parameters, QStringLiteral( "TOLERANCE" ), context );
101+
102+
int directionField = -1;
103+
if ( !directionFieldName.isEmpty() )
104+
{
105+
directionField = mNetwork->fields().lookupField( directionFieldName );
106+
}
107+
108+
int speedField = -1;
109+
if ( !speedFieldName.isEmpty() )
110+
{
111+
speedField = mNetwork->fields().lookupField( speedFieldName );
112+
}
113+
114+
mDirector = new QgsVectorLayerDirector( mNetwork.get(), directionField, forwardValue, backwardValue, bothValue, defaultDirection );
115+
116+
QgsUnitTypes::DistanceUnit distanceUnits = context.project()->crs().mapUnits();
117+
mMultiplier = QgsUnitTypes::fromUnitToUnitFactor( distanceUnits, QgsUnitTypes::DistanceMeters );
118+
119+
if ( strategy )
120+
{
121+
mDirector->addStrategy( new QgsNetworkSpeedStrategy( speedField, defaultSpeed, mMultiplier * 1000.0 / 3600.0 ) );
122+
mMultiplier = 3600;
123+
}
124+
else
125+
{
126+
mDirector->addStrategy( new QgsNetworkDistanceStrategy() );
127+
}
128+
129+
mBuilder = qgis::make_unique< QgsGraphBuilder >( mNetwork->sourceCrs(), true, tolerance );
130+
}
131+
132+
void QgsNetworkAnalysisAlgorithmBase::loadPoints( QgsFeatureSource *source, QVector< QgsPointXY > &points, QHash< int, QgsAttributes > &attributes, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
133+
{
134+
feedback->pushInfo( QObject::tr( "Loading points…" ) );
135+
136+
QgsFeature feat;
137+
int i = 0;
138+
int pointId = 1;
139+
double step = source->featureCount() > 0 ? 100.0 / source->featureCount() : 0;
140+
QgsFeatureIterator features = source->getFeatures( QgsFeatureRequest().setDestinationCrs( mNetwork->sourceCrs(), context.transformContext() ) );
141+
142+
while ( features.nextFeature( feat ) )
143+
{
144+
i++;
145+
if ( feedback->isCanceled() )
146+
{
147+
break;
148+
}
149+
150+
feedback->setProgress( i * step );
151+
if ( !feat.hasGeometry() )
152+
continue;
153+
154+
QgsGeometry geom = feat.geometry();
155+
QgsAbstractGeometry::vertex_iterator it = geom.vertices_begin();
156+
while ( it != geom.vertices_end() )
157+
{
158+
points.push_back( QgsPointXY( *it ) );
159+
attributes.insert( pointId, feat.attributes() );
160+
it++;
161+
pointId++;
162+
}
163+
}
164+
}
165+
166+
///@endcond

‎src/analysis/processing/qgsalgorithmnetworkanalysisbase.h

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/***************************************************************************
2+
qgsalgorithmnetworkanalysisbase.h
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+
#ifndef QGSALGORITHMNETWORKANALYSISBASE_H
19+
#define QGSALGORITHMNETWORKANALYSISBASE_H
20+
21+
#define SIP_NO_FILE
22+
23+
#include "qgis.h"
24+
#include "qgsprocessingalgorithm.h"
25+
26+
#include "qgsgraph.h"
27+
#include "qgsgraphbuilder.h"
28+
#include "qgsvectorlayerdirector.h"
29+
30+
///@cond PRIVATE
31+
32+
/**
33+
* Base class for networkanalysis algorithms.
34+
*/
35+
class QgsNetworkAnalysisAlgorithmBase : public QgsProcessingAlgorithm
36+
{
37+
public:
38+
39+
QString group() const final;
40+
QString groupId() const final;
41+
QIcon icon() const override { return QgsApplication::getThemeIcon( QStringLiteral( "/algorithms/mAlgorithmNetworkAnalysis.svg" ) ); }
42+
QString svgIconPath() const override { return QgsApplication::iconPath( QStringLiteral( "/algorithms/mAlgorithmNetworkAnalysis.svg" ) ); }
43+
44+
protected:
45+
46+
/**
47+
* Adds common algorithm parameters.
48+
*/
49+
void addCommonParams();
50+
51+
/**
52+
* Populates common parameters with values.
53+
*/
54+
void loadCommonParams( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback );
55+
56+
/**
57+
* Loads point from the feature source for further processing.
58+
*/
59+
void loadPoints( QgsFeatureSource *source, QVector< QgsPointXY > &points, QHash< int, QgsAttributes > &attributes, QgsProcessingContext &context, QgsProcessingFeedback *feedback );
60+
61+
std::unique_ptr< QgsFeatureSource > mNetwork;
62+
QgsVectorLayerDirector *mDirector = nullptr;
63+
std::unique_ptr< QgsGraphBuilder > mBuilder;
64+
std::unique_ptr< QgsGraph > mGraph;
65+
double mMultiplier = 1;
66+
};
67+
68+
///@endcond PRIVATE
69+
70+
#endif // QGSALGORITHMNETWORKANALYSISBASE_H
71+

‎src/analysis/processing/qgsalgorithmshortestpathlayertopoint.cpp

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
/***************************************************************************
2+
qgsalgorithmshortestpathlayertopoint.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 "qgsalgorithmshortestpathlayertopoint.h"
19+
20+
#include "qgsgraphanalyzer.h"
21+
22+
#include "qgsmessagelog.h"
23+
24+
///@cond PRIVATE
25+
26+
QString QgsShortestPathLayerToPointAlgorithm::name() const
27+
{
28+
return QStringLiteral( "shortestpathlayertopoint" );
29+
}
30+
31+
QString QgsShortestPathLayerToPointAlgorithm::displayName() const
32+
{
33+
return QObject::tr( "Shortest path (layer to point)" );
34+
}
35+
36+
QStringList QgsShortestPathLayerToPointAlgorithm::tags() const
37+
{
38+
return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
39+
}
40+
41+
QString QgsShortestPathLayerToPointAlgorithm::shortHelpString() const
42+
{
43+
return QObject::tr( "This algorithm computes optimal (shortest or fastest) route from multiple start points defined by vector layer and given end point." );
44+
}
45+
46+
QgsShortestPathLayerToPointAlgorithm *QgsShortestPathLayerToPointAlgorithm::createInstance() const
47+
{
48+
return new QgsShortestPathLayerToPointAlgorithm();
49+
}
50+
51+
void QgsShortestPathLayerToPointAlgorithm::initAlgorithm( const QVariantMap & )
52+
{
53+
addCommonParams();
54+
addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "START_POINTS" ), QObject::tr( "Vector layer with start points" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
55+
addParameter( new QgsProcessingParameterPoint( QStringLiteral( "END_POINT" ), QObject::tr( "End point" ) ) );
56+
57+
addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), QgsProcessing::TypeVectorLine ) );
58+
}
59+
60+
QVariantMap QgsShortestPathLayerToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
61+
{
62+
loadCommonParams( parameters, context, feedback );
63+
64+
QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
65+
66+
std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
67+
if ( !startPoints )
68+
throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
69+
70+
QgsFields fields = startPoints->fields();
71+
fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
72+
fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
73+
fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
74+
75+
QString dest;
76+
std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::LineString, mNetwork->sourceCrs() ) );
77+
if ( !sink )
78+
throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
79+
80+
QVector< QgsPointXY > points;
81+
points.push_front( endPoint );
82+
QHash< int, QgsAttributes > sourceAttributes;
83+
loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
84+
85+
feedback->pushInfo( QObject::tr( "Building graph…" ) );
86+
QVector< QgsPointXY > snappedPoints;
87+
mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
88+
89+
feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
90+
QgsGraph *graph = mBuilder->graph();
91+
int idxEnd = graph->findVertex( snappedPoints[0] );
92+
int idxStart;
93+
int currentIdx;
94+
95+
QVector< int > tree;
96+
QVector< double > costs;
97+
98+
QVector<QgsPointXY> route;
99+
double cost;
100+
101+
QgsFeature feat;
102+
feat.setFields( fields );
103+
QgsAttributes attributes;
104+
105+
int step = points.size() > 0 ? 100.0 / points.size() : 1;
106+
for ( int i = 1; i < points.size(); i++ )
107+
{
108+
if ( feedback->isCanceled() )
109+
{
110+
break;
111+
}
112+
113+
idxStart = graph->findVertex( snappedPoints[i] );
114+
QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
115+
116+
if ( tree.at( idxEnd ) == -1 )
117+
{
118+
feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
119+
.arg( points[i].toString() )
120+
.arg( endPoint.toString() ) );
121+
feat.clearGeometry();
122+
attributes = sourceAttributes.value( i );
123+
attributes.append( points[i].toString() );
124+
feat.setAttributes( attributes );
125+
sink->addFeature( feat, QgsFeatureSink::FastInsert );
126+
continue;
127+
}
128+
129+
route.clear();
130+
route.push_front( graph->vertex( idxEnd ).point() );
131+
cost = costs.at( idxEnd );
132+
currentIdx = idxEnd;
133+
while ( currentIdx != idxStart )
134+
{
135+
currentIdx = graph->edge( tree.at( currentIdx ) ).fromVertex();
136+
route.push_front( graph->vertex( currentIdx ).point() );
137+
}
138+
139+
QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
140+
QgsFeature feat;
141+
feat.setFields( fields );
142+
attributes = sourceAttributes.value( i );
143+
attributes.append( points[i].toString() );
144+
attributes.append( endPoint.toString() );
145+
attributes.append( cost / mMultiplier );
146+
feat.setAttributes( attributes );
147+
feat.setGeometry( geom );
148+
sink->addFeature( feat, QgsFeatureSink::FastInsert );
149+
150+
feedback->setProgress( i * step );
151+
}
152+
153+
QVariantMap outputs;
154+
outputs.insert( QStringLiteral( "OUTPUT" ), dest );
155+
return outputs;
156+
}
157+
158+
///@endcond

‎src/analysis/processing/qgsalgorithmshortestpathlayertopoint.h

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/***************************************************************************
2+
qgsalgorithmshortestpathlayertopoint.h
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+
#ifndef QGSALGORITHMSHORTESTPATHLAYERTOPOINT_H
19+
#define QGSALGORITHMSHORTESTPATHLAYERTOPOINT_H
20+
21+
#define SIP_NO_FILE
22+
23+
#include "qgis.h"
24+
#include "qgsalgorithmnetworkanalysisbase.h"
25+
26+
///@cond PRIVATE
27+
28+
/**
29+
* Native shortest path (layer to point) algorithm.
30+
*/
31+
class QgsShortestPathLayerToPointAlgorithm : public QgsNetworkAnalysisAlgorithmBase
32+
{
33+
34+
public:
35+
36+
QgsShortestPathLayerToPointAlgorithm() = default;
37+
void initAlgorithm( const QVariantMap &configuration = QVariantMap() ) override;
38+
QString name() const override;
39+
QString displayName() const override;
40+
QStringList tags() const override;
41+
QString shortHelpString() const override;
42+
QgsShortestPathLayerToPointAlgorithm *createInstance() const override SIP_FACTORY;
43+
44+
protected:
45+
46+
QVariantMap processAlgorithm( const QVariantMap &parameters,
47+
QgsProcessingContext &context, QgsProcessingFeedback *feedback ) override;
48+
49+
};
50+
51+
///@endcond PRIVATE
52+
53+
#endif // QGSALGORITHMSHORTESTPATHLAYERTOPOINT_H

‎src/analysis/processing/qgsalgorithmshortestpathpointtolayer.cpp

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
/***************************************************************************
2+
qgsalgorithmshortestpathpointtolayer.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 "qgsalgorithmshortestpathpointtolayer.h"
19+
20+
#include "qgsgraphanalyzer.h"
21+
22+
#include "qgsmessagelog.h"
23+
24+
///@cond PRIVATE
25+
26+
QString QgsShortestPathPointToLayerAlgorithm::name() const
27+
{
28+
return QStringLiteral( "shortestpathpointtolayer" );
29+
}
30+
31+
QString QgsShortestPathPointToLayerAlgorithm::displayName() const
32+
{
33+
return QObject::tr( "Shortest path (point to layer)" );
34+
}
35+
36+
QStringList QgsShortestPathPointToLayerAlgorithm::tags() const
37+
{
38+
return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
39+
}
40+
41+
QString QgsShortestPathPointToLayerAlgorithm::shortHelpString() const
42+
{
43+
return QObject::tr( "This algorithm computes optimal (shortest or fastest) route between given start point and multiple end points defined by point vector layer." );
44+
}
45+
46+
QgsShortestPathPointToLayerAlgorithm *QgsShortestPathPointToLayerAlgorithm::createInstance() const
47+
{
48+
return new QgsShortestPathPointToLayerAlgorithm();
49+
}
50+
51+
void QgsShortestPathPointToLayerAlgorithm::initAlgorithm( const QVariantMap & )
52+
{
53+
addCommonParams();
54+
addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
55+
addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "END_POINTS" ), QObject::tr( "Vector layer with end points" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
56+
57+
addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), QgsProcessing::TypeVectorLine ) );
58+
}
59+
60+
QVariantMap QgsShortestPathPointToLayerAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
61+
{
62+
loadCommonParams( parameters, context, feedback );
63+
64+
QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
65+
66+
std::unique_ptr< QgsFeatureSource > endPoints( parameterAsSource( parameters, QStringLiteral( "END_POINTS" ), context ) );
67+
if ( !endPoints )
68+
throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "END_POINTS" ) ) );
69+
70+
QgsFields fields = endPoints->fields();
71+
fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
72+
fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
73+
fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
74+
75+
QString dest;
76+
std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::LineString, mNetwork->sourceCrs() ) );
77+
if ( !sink )
78+
throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
79+
80+
QVector< QgsPointXY > points;
81+
points.push_front( startPoint );
82+
QHash< int, QgsAttributes > sourceAttributes;
83+
loadPoints( endPoints.get(), points, sourceAttributes, context, feedback );
84+
85+
feedback->pushInfo( QObject::tr( "Building graph…" ) );
86+
QVector< QgsPointXY > snappedPoints;
87+
mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
88+
89+
feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
90+
QgsGraph *graph = mBuilder->graph();
91+
int idxStart = graph->findVertex( snappedPoints[0] );
92+
int idxEnd;
93+
94+
QVector< int > tree;
95+
QVector< double > costs;
96+
QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
97+
98+
QVector<QgsPointXY> route;
99+
double cost;
100+
101+
QgsFeature feat;
102+
feat.setFields( fields );
103+
QgsAttributes attributes;
104+
105+
int step = points.size() > 0 ? 100.0 / points.size() : 1;
106+
for ( int i = 1; i < points.size(); i++ )
107+
{
108+
if ( feedback->isCanceled() )
109+
{
110+
break;
111+
}
112+
113+
idxEnd = graph->findVertex( snappedPoints[i] );
114+
if ( tree.at( idxEnd ) == -1 )
115+
{
116+
feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
117+
.arg( startPoint.toString() )
118+
.arg( points[i].toString() ) );
119+
feat.clearGeometry();
120+
attributes = sourceAttributes.value( i );
121+
attributes.append( QVariant() );
122+
attributes.append( points[i].toString() );
123+
feat.setAttributes( attributes );
124+
sink->addFeature( feat, QgsFeatureSink::FastInsert );
125+
continue;
126+
}
127+
128+
route.clear();
129+
route.push_front( graph->vertex( idxEnd ).point() );
130+
cost = costs.at( idxEnd );
131+
while ( idxEnd != idxStart )
132+
{
133+
idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
134+
route.push_front( graph->vertex( idxEnd ).point() );
135+
}
136+
137+
QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
138+
QgsFeature feat;
139+
feat.setFields( fields );
140+
attributes = sourceAttributes.value( i );
141+
attributes.append( startPoint.toString() );
142+
attributes.append( points[i].toString() );
143+
attributes.append( cost / mMultiplier );
144+
feat.setAttributes( attributes );
145+
feat.setGeometry( geom );
146+
sink->addFeature( feat, QgsFeatureSink::FastInsert );
147+
148+
feedback->setProgress( i * step );
149+
}
150+
151+
QVariantMap outputs;
152+
outputs.insert( QStringLiteral( "OUTPUT" ), dest );
153+
return outputs;
154+
}
155+
156+
///@endcond

‎src/analysis/processing/qgsalgorithmshortestpathpointtolayer.h

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/***************************************************************************
2+
qgsalgorithmshortestpathpointtolayer.h
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+
#ifndef QGSALGORITHMSHORTESTPATHPOINTTOLAYER_H
19+
#define QGSALGORITHMSHORTESTPATHPOINTTOLAYER_H
20+
21+
#define SIP_NO_FILE
22+
23+
#include "qgis.h"
24+
#include "qgsalgorithmnetworkanalysisbase.h"
25+
26+
///@cond PRIVATE
27+
28+
/**
29+
* Native shortest path (point to layer) algorithm.
30+
*/
31+
class QgsShortestPathPointToLayerAlgorithm : public QgsNetworkAnalysisAlgorithmBase
32+
{
33+
34+
public:
35+
36+
QgsShortestPathPointToLayerAlgorithm() = default;
37+
void initAlgorithm( const QVariantMap &configuration = QVariantMap() ) override;
38+
QString name() const override;
39+
QString displayName() const override;
40+
QStringList tags() const override;
41+
QString shortHelpString() const override;
42+
QgsShortestPathPointToLayerAlgorithm *createInstance() const override SIP_FACTORY;
43+
44+
protected:
45+
46+
QVariantMap processAlgorithm( const QVariantMap &parameters,
47+
QgsProcessingContext &context, QgsProcessingFeedback *feedback ) override;
48+
49+
};
50+
51+
///@endcond PRIVATE
52+
53+
#endif // QGSALGORITHMSHORTESTPATHPOINTTOLAYER_H

‎src/analysis/processing/qgsalgorithmshortestpathpointtopoint.cpp

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
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+
18+
#include "qgsalgorithmshortestpathpointtopoint.h"
19+
20+
#include "qgsgraphanalyzer.h"
21+
22+
///@cond PRIVATE
23+
24+
QString QgsShortestPathPointToPointAlgorithm::name() const
25+
{
26+
return QStringLiteral( "shortestpathpointtopoint" );
27+
}
28+
29+
QString QgsShortestPathPointToPointAlgorithm::displayName() const
30+
{
31+
return QObject::tr( "Shortest path (point to point)" );
32+
}
33+
34+
QStringList QgsShortestPathPointToPointAlgorithm::tags() const
35+
{
36+
return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
37+
}
38+
39+
QString QgsShortestPathPointToPointAlgorithm::shortHelpString() const
40+
{
41+
return QObject::tr( "This algorithm computes optimal (shortest or fastest) route between given start and end points." );
42+
}
43+
44+
QgsShortestPathPointToPointAlgorithm *QgsShortestPathPointToPointAlgorithm::createInstance() const
45+
{
46+
return new QgsShortestPathPointToPointAlgorithm();
47+
}
48+
49+
void 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" ), QgsProcessing::TypeVectorLine ) );
56+
addOutput( new QgsProcessingOutputNumber( QStringLiteral( "TRAVEL_COST" ), QObject::tr( "Travel cost" ) ) );
57+
}
58+
59+
QVariantMap QgsShortestPathPointToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
60+
{
61+
loadCommonParams( parameters, context, feedback );
62+
63+
QgsFields fields;
64+
fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
65+
fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
66+
fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
67+
68+
QString dest;
69+
std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::LineString, mNetwork->sourceCrs() ) );
70+
if ( !sink )
71+
throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
72+
73+
QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
74+
QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
75+
76+
feedback->pushInfo( QObject::tr( "Building graph…" ) );
77+
QVector< QgsPointXY > points;
78+
points << startPoint << endPoint;
79+
QVector< QgsPointXY > snappedPoints;
80+
mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
81+
82+
feedback->pushInfo( QObject::tr( "Calculating shortest path…" ) );
83+
QgsGraph *graph = mBuilder->graph();
84+
int idxStart = graph->findVertex( snappedPoints[0] );
85+
int idxEnd = graph->findVertex( snappedPoints[1] );
86+
87+
QVector< int > tree;
88+
QVector< double > costs;
89+
QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
90+
91+
if ( tree.at( idxEnd ) == -1 )
92+
{
93+
throw QgsProcessingException( QObject::tr( "There is no route from start point to end point." ) );
94+
}
95+
96+
QVector<QgsPointXY> route;
97+
route.push_front( graph->vertex( idxEnd ).point() );
98+
double cost = costs.at( idxEnd );
99+
while ( idxEnd != idxStart )
100+
{
101+
idxEnd = graph->edge( tree.at( idxEnd ) ).fromVertex();
102+
route.push_front( graph->vertex( idxEnd ).point() );
103+
}
104+
105+
feedback->pushInfo( QObject::tr( "Writing results…" ) );
106+
QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
107+
QgsFeature feat;
108+
feat.setFields( fields );
109+
QgsAttributes attributes;
110+
attributes << startPoint.toString() << endPoint.toString() << cost / mMultiplier;
111+
feat.setGeometry( geom );
112+
feat.setAttributes( attributes );
113+
sink->addFeature( feat, QgsFeatureSink::FastInsert );
114+
115+
QVariantMap outputs;
116+
outputs.insert( QStringLiteral( "OUTPUT" ), dest );
117+
outputs.insert( QStringLiteral( "TRAVEL_COST" ), cost / mMultiplier );
118+
return outputs;
119+
}
120+
121+
///@endcond

‎src/analysis/processing/qgsalgorithmshortestpathpointtopoint.h

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/***************************************************************************
2+
qgsalgorithmshortestpathpointtopoint.h
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+
#ifndef QGSALGORITHMSHORTESTPATHPOINTTOPOINT_H
19+
#define QGSALGORITHMSHORTESTPATHPOINTTOPOINT_H
20+
21+
#define SIP_NO_FILE
22+
23+
#include "qgis.h"
24+
#include "qgsalgorithmnetworkanalysisbase.h"
25+
26+
///@cond PRIVATE
27+
28+
/**
29+
* Native shortest path (point to point) algorithm.
30+
*/
31+
class QgsShortestPathPointToPointAlgorithm : public QgsNetworkAnalysisAlgorithmBase
32+
{
33+
34+
public:
35+
36+
QgsShortestPathPointToPointAlgorithm() = default;
37+
void initAlgorithm( const QVariantMap &configuration = QVariantMap() ) override;
38+
QString name() const override;
39+
QString displayName() const override;
40+
QStringList tags() const override;
41+
QString shortHelpString() const override;
42+
QgsShortestPathPointToPointAlgorithm *createInstance() const override SIP_FACTORY;
43+
44+
protected:
45+
46+
QVariantMap processAlgorithm( const QVariantMap &parameters,
47+
QgsProcessingContext &context, QgsProcessingFeedback *feedback ) override;
48+
49+
};
50+
51+
///@endcond PRIVATE
52+
53+
#endif // QGSALGORITHMSHORTESTPATHPOINTTOPOINT_H

‎src/analysis/processing/qgsnativealgorithms.cpp

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,9 @@
7474
#include "qgsalgorithmrotate.h"
7575
#include "qgsalgorithmsaveselectedfeatures.h"
7676
#include "qgsalgorithmsegmentize.h"
77+
#include "qgsalgorithmshortestpathlayertopoint.h"
78+
#include "qgsalgorithmshortestpathpointtolayer.h"
79+
#include "qgsalgorithmshortestpathpointtopoint.h"
7780
#include "qgsalgorithmsimplify.h"
7881
#include "qgsalgorithmsmooth.h"
7982
#include "qgsalgorithmsnaptogrid.h"
@@ -196,6 +199,9 @@ void QgsNativeAlgorithms::loadAlgorithms()
196199
addAlgorithm( new QgsSegmentizeByMaximumAngleAlgorithm() );
197200
addAlgorithm( new QgsSegmentizeByMaximumDistanceAlgorithm() );
198201
addAlgorithm( new QgsSelectByLocationAlgorithm() );
202+
addAlgorithm( new QgsShortestPathLayerToPointAlgorithm() );
203+
addAlgorithm( new QgsShortestPathPointToLayerAlgorithm() );
204+
addAlgorithm( new QgsShortestPathPointToPointAlgorithm() );
199205
addAlgorithm( new QgsSimplifyAlgorithm() );
200206
addAlgorithm( new QgsSmoothAlgorithm() );
201207
addAlgorithm( new QgsSnapToGridAlgorithm() );

0 commit comments

Comments
 (0)
Please sign in to comment.