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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
from osm_parser import get_default_parser
from collections import defaultdict
class Node:
def __init__(self, id, lat, lng):
self.id = id
self.lat = float(lat)
self.lng = float(lng)
self.neighbours = []
self.parent = None
self.size = 1
def find_root(self):
""" Recursively find the root of this node. """
if not self.parent:
return self
else:
return self.parent.find_root()
def union(self, other):
""" Mark this node and some other node as part of the same tree. """
this = self.find_root()
other = other.find_root()
# If we share the same root we are already part of the same tree
if this == other:
return
# Minimize tree size. This ensures optimal complexity.
# We could also store the rank instead.
if this.size < other.size:
this, other = other, this
# This is safe since other is a root node and currently doesn't have a
# parent.
other.parent = this
this.size += other.size
def coord_tuple(self):
return self.lat, self.lng
parser = None # Have a global reusable parser object
def add_neighbours(nodes):
for way in parser.iter_ways():
if 'highway' not in way['tags']:
continue
road = way['road']
for i in range(len(road) - 1):
node1 = road[i]
node2 = road[i + 1]
# FIXME: lots of repeated code here
if suitable_bike(way):
bike_nodes = nodes['bike']
bike_nodes[node1].neighbours.append(bike_nodes[node2])
bike_nodes[node2].neighbours.append(bike_nodes[node1])
# These two are neighbours and should be part of the same tree.
bike_nodes[node1].union(bike_nodes[node2])
if suitable_car(way):
car_nodes = nodes['car']
car_nodes[node1].neighbours.append(car_nodes[node2])
car_nodes[node2].neighbours.append(car_nodes[node1])
# These two are neighbours and should be part of the same tree.
car_nodes[node1].union(car_nodes[node2])
return nodes
def extract_osm_nodes(f_name):
global parser
parser = get_default_parser(f_name)
nodes = {
'bike': dict(),
'car': dict()
}
for node in parser.iter_nodes():
# FIXME: this can probably be solved better
nodes['bike'][node['id']] = Node(node['id'], node['lat'], node['lon'])
nodes['car'][node['id']] = Node(node['id'], node['lat'], node['lon'])
add_neighbours(nodes)
# FIXME: this can probably be solved better
# Remove nodes without neighbours
for node_id, node in nodes['bike'].copy().items():
if not node.neighbours:
del nodes['bike'][node_id]
for node_id, node in nodes['car'].copy().items():
if not node.neighbours:
del nodes['car'][node_id]
nodes['bike'], unconnected_bike = make_forest(nodes['bike'])
nodes['car'], unconnected_car = make_forest(nodes['car'])
unconnected_nodes = {
'bike': unconnected_bike,
'car': unconnected_car
}
grids = {
'bike': make_grid(nodes['bike']),
'car': make_grid(nodes['car'])
}
return nodes, grids, unconnected_nodes
def make_forest(nodes):
# Construct a forest of disjoint trees.
# The forest is a { root: tree }-dict. If we construct a relation where
# two nodes relate to each other if they are a part of the same tree,
# this can be shown to be an equivalence relation where the equivalence
# class is some node in the tree. In our case, the equivalence class
# becomes the root of each node since it will be the same for all nodes
# in the same tree due our use of union-find.
forest = defaultdict(dict)
for node_id, node in nodes.items():
forest[node.find_root().id][node_id] = node
# Find the largest disjoint tree.
# We store the root so we can easily test if a node is part of this
# tree or not.
best_size = 0
best_tree = None
best_root = None
for root in forest:
tree = forest[root]
size = len(tree)
if size > best_size:
best_size = size
best_tree = tree
best_root = root
unconnected_nodes = []
for _, node in nodes.items():
if node.find_root().id != best_root:
unconnected_nodes.append(node)
nodes = best_tree
return nodes, unconnected_nodes
def make_grid(nodes):
grid = defaultdict()
# create a "grid" by grouping nearby nodes.
for node in nodes.copy().values():
key = (int(round(node.lat, 3) * 1000), int(round(node.lng, 3)
* 1000))
if key in grid.keys():
grid[key].append(node)
else:
grid[key] = [node]
return grid
def select_nodes_in_rectangle(nodes, min_lat, max_lat, min_long, max_long):
return [node for node in nodes.values()
if min_lat <= node.lat <= max_lat
and min_long <= node.lng <= max_long]
def get_relevant_neighbours(nodes, transport_mode):
if transport_mode == "bike":
return nodes.neighbours_bike
else:
return nodes.neighbours_car
suitable_highway_types_bike = [
# Special road types
'living_street', 'service', 'pedestrian', 'track', 'road'
]
def suitable_bike(way):
tags = way['tags']
suitable_generic_type = tags['highway'] in suitable_highway_types_bike
suitable_bike = tags['bicycle'] == 'yes' if 'bicycle' in tags else False
return suitable_generic_type or suitable_bike
suitable_highway_types_car = [
# Roads
'motorway', 'trunk', 'primary', 'secondary',
'tertiary', 'unclassified', 'residential',
# Link roads
'motorway_link', 'trunk_link', 'primary_link', 'secondary_link',
'tertiary_link',
# Special road types
'living_street', 'service',
'pedestrian', 'road' # FIXME: Handle predestrian and road differently?
]
def suitable_car(way):
return way['tags']['highway'] in suitable_highway_types_car
|
