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
|
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):
if not self.parent:
return self
else:
return self.parent.find_root()
def union(self, other):
this = self.find_root()
other = other.find_root()
if this == other:
return
if this.size < other.size:
this, other = other, this
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])
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 using union-find
forest = defaultdict(dict) # contains {root: tree}
for node_id, node in nodes.items():
forest[node.find_root().id][node_id] = node
# find the largest disjoin tree
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]
|
