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
|
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]
nodes[node1].neighbours.append(nodes[node2])
nodes[node2].neighbours.append(nodes[node1])
# These two are neighbours and should be part of the same tree.
nodes[node1].union(nodes[node2])
return nodes
def extract_osm_nodes(f_name):
global parser
parser = get_default_parser(f_name)
nodes = dict()
grid = defaultdict()
for node in parser.iter_nodes():
new_node = Node(node['id'], node['lat'], node['lon'])
nodes[node['id']] = new_node
add_neighbours(nodes)
# Remove nodes without neighbours
for node_id, node in nodes.copy().items():
if not node.neighbours:
del nodes[node_id]
# 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
# 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 nodes, grid, unconnected_nodes
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]
|
