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
|
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()
for node in parser.iter_nodes():
nodes[node['id']] = Node(node['id'], node['lat'], node['lon'])
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)
return best_tree, 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]
|
