-
Notifications
You must be signed in to change notification settings - Fork 1
/
pathFinder.py
82 lines (68 loc) · 2.92 KB
/
pathFinder.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import osmnx as ox
import numpy as np
class PathFinder():
def __init__(self, timeout=100):
'''
Parameters:
timeout (int): timeout for path finding algorithm
'''
self._timeout = timeout # timeout limit for finding function
def get_weight_sum(self, G, route, weight):
'''
Get the accumulated value for a path
Parameters:
G : map graph object
route : path
weight (str): path type
'''
return sum(ox.utils_graph.get_route_edge_attributes(G, route, weight))
def get_path(self, G, start, end, limit_ratio, weight='length', inverse=False):
'''
Return the path with certain constraint
Parameters:
G : map graph object
start (float tuple): coordinate for the start point
end (float tuple): coordinate for the end point
limit_ratio (float): the length restriction
weight (str): path type
inverse (bool): switch between maximum and minimum
'''
# transfer node coordinates to node ids
if type(start) is not np.int64:
start = ox.get_nearest_node(G, start)
end = ox.get_nearest_node(G, end)
# calculate shortest path
sp = ox.shortest_path(G, start, end, weight='length')
sp_len = self.get_weight_sum(G, sp, 'length')
sp_grad = self.get_weight_sum(G, sp, 'grade_abs')
# print('shortest path: ')
# print(" length: ", sp_len)
# print(" height: ", sp_grad)
path = None
if weight == 'length' and inverse is False:
path = sp
else:
if weight == 'height':
weight = 'grade_abs' if not inverse else 'inv_grade_abs'
path_gen = ox.k_shortest_paths(G, start, end, self._timeout, weight=weight)
cnt = 0
for pth in path_gen:
cnt += 1
if self.get_weight_sum(G, pth, 'length') > limit_ratio * sp_len:
continue
path = pth
# print(cnt)
# print("limit_ratio:", limit_ratio)
# print("sp_len", sp_len)
# print("sp_len * limit_ratio", limit_ratio * sp_len)
# print("now length", self.get_weight_sum(G, pth, 'length'))
# print('find path under constraint:')
# print(" length: ", self.get_weight_sum(G, path, 'length'))
# print(" height: ", self.get_weight_sum(G, path, 'grade_abs'))
break
path_length = self.get_weight_sum(G, path, 'length')
path_elevation_gain = self.get_weight_sum(G, path, 'grade_abs')
coords = []
for node in path:
coords.append((G.nodes[node]['x'], G.nodes[node]['y']))
return path, coords, int(path_length), int(path_elevation_gain), int(sp_len), int(sp_grad)