Skip to content

Commit 2f70f1f

Browse files
alexbruyalexbruy
committedDec 13, 2016
[processing] add algorithm for calculating shortest path to multiple end
points defined by vector layer
·
ltr-3_40final-3_0_0
1 parent 729567d commit 2f70f1f

File tree

2 files changed

+262
-2
lines changed

2 files changed

+262
-2
lines changed
 

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -185,6 +185,7 @@
185185
from .Heatmap import Heatmap
186186
from .Orthogonalize import Orthogonalize
187187
from .ShortestPathPointToPoint import ShortestPathPointToPoint
188+
from .ShortestPathPointToLayer import ShortestPathPointToLayer
188189
from .ServiceAreaFromPoint import ServiceAreaFromPoint
189190
from .ServiceAreaFromLayer import ServiceAreaFromLayer
190191

@@ -252,8 +253,8 @@ def __init__(self):
252253
ExtractSpecificNodes(), GeometryByExpression(), SnapGeometriesToLayer(),
253254
PoleOfInaccessibility(), CreateAttributeIndex(), DropGeometry(),
254255
BasicStatisticsForField(), RasterCalculator(), Heatmap(),
255-
Orthogonalize(), ShortestPathPointToPoint(), ServiceAreaFromPoint(),
256-
ServiceAreaFromLayer()
256+
Orthogonalize(), ShortestPathPointToPoint(), ShortestPathPointToLayer(),
257+
ServiceAreaFromPoint(), ServiceAreaFromLayer()
257258
]
258259

259260
if hasMatplotlib:

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

Lines changed: 259 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,259 @@
1+
# -*- coding: utf-8 -*-
2+
3+
"""
4+
***************************************************************************
5+
ShortestPathPointToLayer.py
6+
---------------------
7+
Date : December 2016
8+
Copyright : (C) 2016 by Alexander Bruy
9+
Email : alexander dot bruy at gmail dot com
10+
***************************************************************************
11+
* *
12+
* This program is free software; you can redistribute it and/or modify *
13+
* it under the terms of the GNU General Public License as published by *
14+
* the Free Software Foundation; either version 2 of the License, or *
15+
* (at your option) any later version. *
16+
* *
17+
***************************************************************************
18+
"""
19+
20+
__author__ = 'Alexander Bruy'
21+
__date__ = 'December 2016'
22+
__copyright__ = '(C) 2016, Alexander Bruy'
23+
24+
# This will get replaced with a git SHA1 when you do a git archive
25+
26+
__revision__ = '$Format:%H$'
27+
28+
import os
29+
30+
from qgis.PyQt.QtCore import QVariant
31+
from qgis.PyQt.QtGui import QIcon
32+
33+
from qgis.core import QgsWkbTypes, QgsUnitTypes, QgsFeature, QgsGeometry, QgsPoint, QgsFields, QgsField, QgsFeatureRequest
34+
from qgis.analysis import (QgsVectorLayerDirector,
35+
QgsNetworkDistanceStrategy,
36+
QgsNetworkSpeedStrategy,
37+
QgsGraphBuilder,
38+
QgsGraphAnalyzer
39+
)
40+
from qgis.utils import iface
41+
42+
from processing.core.GeoAlgorithm import GeoAlgorithm
43+
from processing.core.GeoAlgorithmExecutionException import GeoAlgorithmExecutionException
44+
from processing.core.ProcessingLog import ProcessingLog
45+
from processing.core.parameters import (ParameterVector,
46+
ParameterPoint,
47+
ParameterNumber,
48+
ParameterString,
49+
ParameterTableField,
50+
ParameterSelection
51+
)
52+
from processing.core.outputs import OutputVector
53+
from processing.tools import dataobjects, vector
54+
55+
pluginPath = os.path.split(os.path.split(os.path.dirname(__file__))[0])[0]
56+
57+
58+
class ShortestPathPointToLayer(GeoAlgorithm):
59+
60+
INPUT_VECTOR = 'INPUT_VECTOR'
61+
START_POINT = 'START_POINT'
62+
END_POINTS = 'END_POINTS'
63+
STRATEGY = 'STRATEGY'
64+
DIRECTION_FIELD = 'DIRECTION_FIELD'
65+
VALUE_FORWARD = 'VALUE_FORWARD'
66+
VALUE_BACKWARD = 'VALUE_BACKWARD'
67+
VALUE_BOTH = 'VALUE_BOTH'
68+
DEFAULT_DIRECTION = 'DEFAULT_DIRECTION'
69+
SPEED_FIELD = 'SPEED_FIELD'
70+
DEFAULT_SPEED = 'DEFAULT_SPEED'
71+
TOLERANCE = 'TOLERANCE'
72+
OUTPUT_LAYER = 'OUTPUT_LAYER'
73+
74+
def getIcon(self):
75+
return QIcon(os.path.join(pluginPath, 'images', 'networkanalysis.svg'))
76+
77+
def defineCharacteristics(self):
78+
self.DIRECTIONS = {self.tr('Forward direction'): QgsVectorLayerDirector.DirectionForward,
79+
self.tr('Backward direction'): QgsVectorLayerDirector.DirectionForward,
80+
self.tr('Both directions'): QgsVectorLayerDirector.DirectionForward
81+
}
82+
83+
self.STRATEGIES = [self.tr('Shortest'),
84+
self.tr('Fastest')
85+
]
86+
87+
self.name, self.i18n_name = self.trAlgorithm('Shortest path (point to layer)')
88+
self.group, self.i18n_group = self.trAlgorithm('Network analysis')
89+
90+
self.addParameter(ParameterVector(self.INPUT_VECTOR,
91+
self.tr('Vector layer representing network'),
92+
[dataobjects.TYPE_VECTOR_LINE]))
93+
self.addParameter(ParameterPoint(self.START_POINT,
94+
self.tr('Start point')))
95+
self.addParameter(ParameterVector(self.END_POINTS,
96+
self.tr('Vector layer with end points'),
97+
[dataobjects.TYPE_VECTOR_POINT]))
98+
self.addParameter(ParameterSelection(self.STRATEGY,
99+
self.tr('Path type to calculate'),
100+
self.STRATEGIES,
101+
default=0))
102+
103+
params = []
104+
params.append(ParameterTableField(self.DIRECTION_FIELD,
105+
self.tr('Direction field'),
106+
self.INPUT_VECTOR,
107+
optional=True))
108+
params.append(ParameterString(self.VALUE_FORWARD,
109+
self.tr('Value for forward direction'),
110+
'',
111+
optional=True))
112+
params.append(ParameterString(self.VALUE_BACKWARD,
113+
self.tr('Value for backward direction'),
114+
'',
115+
optional=True))
116+
params.append(ParameterString(self.VALUE_BOTH,
117+
self.tr('Value for both directions'),
118+
'',
119+
optional=True))
120+
params.append(ParameterSelection(self.DEFAULT_DIRECTION,
121+
self.tr('Default direction'),
122+
list(self.DIRECTIONS.keys()),
123+
default=2))
124+
params.append(ParameterTableField(self.SPEED_FIELD,
125+
self.tr('Speed field'),
126+
self.INPUT_VECTOR,
127+
optional=True))
128+
params.append(ParameterNumber(self.DEFAULT_SPEED,
129+
self.tr('Default speed (km/h)'),
130+
0.0, 99999999.999999, 5.0))
131+
params.append(ParameterNumber(self.TOLERANCE,
132+
self.tr('Topology tolerance'),
133+
0.0, 99999999.999999, 0.0))
134+
135+
for p in params:
136+
p.isAdvanced = True
137+
self.addParameter(p)
138+
139+
self.addOutput(OutputVector(self.OUTPUT_LAYER,
140+
self.tr('Shortest path'),
141+
datatype=[dataobjects.TYPE_VECTOR_LINE]))
142+
143+
def processAlgorithm(self, progress):
144+
layer = dataobjects.getObjectFromUri(
145+
self.getParameterValue(self.INPUT_VECTOR))
146+
startPoint = self.getParameterValue(self.START_POINT)
147+
endPoints = dataobjects.getObjectFromUri(
148+
self.getParameterValue(self.END_POINTS))
149+
strategy = self.getParameterValue(self.STRATEGY)
150+
151+
directionFieldName = self.getParameterValue(self.DIRECTION_FIELD)
152+
forwardValue = self.getParameterValue(self.VALUE_FORWARD)
153+
backwardValue = self.getParameterValue(self.VALUE_BACKWARD)
154+
bothValue = self.getParameterValue(self.VALUE_BOTH)
155+
defaultDirection = self.getParameterValue(self.DEFAULT_DIRECTION)
156+
bothValue = self.getParameterValue(self.VALUE_BOTH)
157+
defaultDirection = self.getParameterValue(self.DEFAULT_DIRECTION)
158+
speedFieldName = self.getParameterValue(self.SPEED_FIELD)
159+
defaultSpeed = self.getParameterValue(self.DEFAULT_SPEED)
160+
tolerance = self.getParameterValue(self.TOLERANCE)
161+
162+
fields = QgsFields()
163+
fields.append(QgsField('start', QVariant.String, '', 254, 0))
164+
fields.append(QgsField('end', QVariant.String, '', 254, 0))
165+
fields.append(QgsField('cost', QVariant.Double, '', 20, 7))
166+
167+
feat = QgsFeature()
168+
feat.setFields(fields)
169+
170+
writer = self.getOutputFromName(
171+
self.OUTPUT_LAYER).getVectorWriter(
172+
fields.toList(),
173+
QgsWkbTypes.LineString,
174+
layer.crs())
175+
176+
tmp = startPoint.split(',')
177+
startPoint = QgsPoint(float(tmp[0]), float(tmp[1]))
178+
179+
directionField = -1
180+
if directionFieldName is not None:
181+
directionField = layer.fields().lookupField(directionFieldName)
182+
speedField = -1
183+
if speedFieldName is not None:
184+
speedField = layer.fields().lookupField(speedFieldName)
185+
186+
director = QgsVectorLayerDirector(layer,
187+
directionField,
188+
forwardValue,
189+
backwardValue,
190+
bothValue,
191+
defaultDirection)
192+
193+
distUnit = iface.mapCanvas().mapSettings().destinationCrs().mapUnits()
194+
multiplier = QgsUnitTypes.fromUnitToUnitFactor(distUnit, QgsUnitTypes.DistanceMeters)
195+
if strategy == 0:
196+
strategy = QgsNetworkDistanceStrategy()
197+
else:
198+
strategy = QgsNetworkSpeedStrategy(speedField,
199+
defaultSpeed,
200+
multiplier * 1000.0 / 3600.0)
201+
multiplier = 3600
202+
203+
director.addStrategy(strategy)
204+
builder = QgsGraphBuilder(iface.mapCanvas().mapSettings().destinationCrs(),
205+
iface.mapCanvas().hasCrsTransformEnabled(),
206+
tolerance)
207+
208+
progress.setInfo(self.tr('Loading end points...'))
209+
request = QgsFeatureRequest()
210+
request.setFlags(request.flags() ^ QgsFeatureRequest.SubsetOfAttributes)
211+
features = vector.features(endPoints, request)
212+
count = len(features)
213+
214+
points = [startPoint]
215+
for f in features:
216+
points.append(f.geometry().asPoint())
217+
218+
progress.setInfo(self.tr('Building graph...'))
219+
snappedPoints = director.makeGraph(builder, points)
220+
221+
progress.setInfo(self.tr('Calculating shortest paths...'))
222+
graph = builder.graph()
223+
224+
idxStart = graph.findVertex(snappedPoints[0])
225+
tree, cost = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
226+
route = []
227+
228+
total = 100.0 / count
229+
for i in range(1, count +1):
230+
idxEnd = graph.findVertex(snappedPoints[i])
231+
232+
if tree[idxEnd] == -1:
233+
msg = self.tr('There is no route from start point ({}) to end point ({}).'.format(startPoint.toString(), points[i].toString()))
234+
progress.setText(msg)
235+
ProcessingLog.addToLog(ProcessingLog.LOG_WARNING, msg)
236+
continue
237+
238+
cost = 0.0
239+
current = idxEnd
240+
while current != idxStart:
241+
cost += graph.edge(tree[current]).cost(0)
242+
route.append(graph.vertex(graph.edge(tree[current]).inVertex()).point())
243+
current = graph.edge(tree[current]).outVertex()
244+
245+
route.append(snappedPoints[0])
246+
route.reverse()
247+
248+
geom = QgsGeometry.fromPolyline(route)
249+
feat.setGeometry(geom)
250+
feat['start'] = startPoint.toString()
251+
feat['end'] = points[i].toString()
252+
feat['cost'] = cost / multiplier
253+
writer.addFeature(feat)
254+
255+
route[:] = []
256+
257+
progress.setPercentage(int(i * total))
258+
259+
del writer

0 commit comments

Comments
 (0)
Please sign in to comment.