Skip to content

Commit 72d13ac

Browse files
alexbruyalexbruy
committedJul 30, 2018
[processing] port shortest path (layer to point) alg to c++
·
ltr-3_40final-3_4_0
1 parent d999923 commit 72d13ac

File tree

6 files changed

+217
-3
lines changed

6 files changed

+217
-3
lines changed
 

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -125,7 +125,7 @@
125125
from .SetRasterStyle import SetRasterStyle
126126
from .SetVectorStyle import SetVectorStyle
127127
from .SetZValue import SetZValue
128-
from .ShortestPathLayerToPoint import ShortestPathLayerToPoint
128+
#from .ShortestPathLayerToPoint import ShortestPathLayerToPoint
129129
#from .ShortestPathPointToLayer import ShortestPathPointToLayer
130130
#from .ShortestPathPointToPoint import ShortestPathPointToPoint
131131
from .SingleSidedBuffer import SingleSidedBuffer
@@ -239,7 +239,7 @@ def getAlgs(self):
239239
SetRasterStyle(),
240240
SetVectorStyle(),
241241
SetZValue(),
242-
ShortestPathLayerToPoint(),
242+
#ShortestPathLayerToPoint(),
243243
#ShortestPathPointToLayer(),
244244
#ShortestPathPointToPoint(),
245245
SingleSidedBuffer(),

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -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

‎src/analysis/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,7 @@ SET(QGIS_ANALYSIS_SRCS
7777
processing/qgsalgorithmrotate.cpp
7878
processing/qgsalgorithmsaveselectedfeatures.cpp
7979
processing/qgsalgorithmsegmentize.cpp
80+
processing/qgsalgorithmshortestpathlayertopoint.cpp
8081
processing/qgsalgorithmshortestpathpointtolayer.cpp
8182
processing/qgsalgorithmshortestpathpointtopoint.cpp
8283
processing/qgsalgorithmsimplify.cpp

‎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/qgsnativealgorithms.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,7 @@
7474
#include "qgsalgorithmrotate.h"
7575
#include "qgsalgorithmsaveselectedfeatures.h"
7676
#include "qgsalgorithmsegmentize.h"
77+
#include "qgsalgorithmshortestpathlayertopoint.h"
7778
#include "qgsalgorithmshortestpathpointtolayer.h"
7879
#include "qgsalgorithmshortestpathpointtopoint.h"
7980
#include "qgsalgorithmsimplify.h"
@@ -198,6 +199,7 @@ void QgsNativeAlgorithms::loadAlgorithms()
198199
addAlgorithm( new QgsSegmentizeByMaximumAngleAlgorithm() );
199200
addAlgorithm( new QgsSegmentizeByMaximumDistanceAlgorithm() );
200201
addAlgorithm( new QgsSelectByLocationAlgorithm() );
202+
addAlgorithm( new QgsShortestPathLayerToPointAlgorithm() );
201203
addAlgorithm( new QgsShortestPathPointToLayerAlgorithm() );
202204
addAlgorithm( new QgsShortestPathPointToPointAlgorithm() );
203205
addAlgorithm( new QgsSimplifyAlgorithm() );

0 commit comments

Comments
 (0)
Please sign in to comment.