diff options
| -rw-r--r-- | algorithms.py | 11 | ||||
| -rw-r--r-- | server.py | 16 | ||||
| -rw-r--r-- | store.py | 23 |
3 files changed, 48 insertions, 2 deletions
diff --git a/algorithms.py b/algorithms.py index de954f4..cc8d35f 100644 --- a/algorithms.py +++ b/algorithms.py @@ -18,7 +18,16 @@ def length_haversine(p1, p2): def get_closest_node_id(nodes, source_node): """ Search through all nodes and return the id of the node that is closest to 'source_node'. """ - pass + min_node = None + min_value = None + + for node_id, node in nodes.items(): + length = length_haversine(source_node, node) + if min_node == None or length < min_value: + min_node = node_id + min_value = length + + return min_node def find_shortest_path(nodes, source_id, target_id): @@ -1,7 +1,8 @@ import json +import algorithms import store -from lib import run_server, get, read_html +from lib import run_server, get, post, read_html @get('/') @@ -17,4 +18,17 @@ def show_area(): return json.dumps(all) +@post('/shortest-path') +def shortest_path(body): + body = json.loads(body) + source_id = algorithms.get_closest_node_id(store.nodes, store.Node(-1, body['lat1'], body['lng1'])) + target_id = algorithms.get_closest_node_id(store.nodes, store.Node(-1, body['lat2'], body['lng2'])) + print(source_id, target_id) + source_node = store.nodes[source_id] + target_node = store.nodes[target_id] + path = [(source_node.lat, source_node.lng), (target_node.lat, target_node.lng)] + response = {'path': path} + return json.dumps(response) + + run_server() @@ -6,22 +6,45 @@ class Node: self.id = id self.lat = float(lat) self.lng = float(lng) + self.neighbors = [] + def coord_tuple(self): return self.lat, self.lng parser = None # Have a global reusable parser object +nodes = None + + +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].neighbors.append(nodes[node2]) + nodes[node2].neighbors.append(nodes[node1]) + + return nodes def extract_osm_nodes(f_name): global parser + global nodes 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) + return nodes |