diff options
| -rw-r--r-- | algorithms.py | 20 | ||||
| -rw-r--r-- | server.py | 21 | ||||
| -rw-r--r-- | store.py | 62 | ||||
| -rw-r--r-- | templates/index.html | 13 | ||||
| -rw-r--r-- | templates/index.js | 5 |
5 files changed, 108 insertions, 13 deletions
diff --git a/algorithms.py b/algorithms.py index 9f3fd78..9d4f538 100644 --- a/algorithms.py +++ b/algorithms.py @@ -1,5 +1,6 @@ import heapq import math +from store import get_relevant_neighbours def length_haversine(p1, p2): @@ -17,6 +18,7 @@ def length_haversine(p1, p2): return 6372797.560856 * c # return the distance in meters +<<<<<<< HEAD def grid_search(grid, source_node): """ Finds closest node to source node by comparing distance to nodes within @@ -72,19 +74,25 @@ def get_closest_node(nodes, source_node): Searches through all nodes in a specified grid and return node closes to source node. """ +def get_closest_node_id(nodes, source_node, transport_mode): + """ Search through all nodes and return the id of the node + that is closest to 'source_node'. """ min_node = None min_value = None for node in nodes: length = length_haversine(source_node, node) - if min_node is None or length < min_value: + + relevant_neighbours = get_relevant_neighbours(node, transport_mode) + + if (min_node is None or length < min_value) and relevant_neighbours: min_node = node min_value = length return min_node -def find_shortest_path(nodes, source_id, target_id): +def find_shortest_path(nodes, source_id, target_id, transport_mode: str): """ Return the shortest path using Dijkstra's algortihm. """ # queue contains multiple (walk_dist, (node_0, node_1, ... node_n))-tuples # where (node_0, node_1, ... node_n) is a walk to node_n @@ -102,10 +110,15 @@ def find_shortest_path(nodes, source_id, target_id): if walk_end in visited: # there exists a shorter walk to walk_end continue + # otherwise this is the shortest walk to walk_end visited.add(walk_end) # consider all our neighbours - for neighbour in nodes[walk_end].neighbours: + end_node = nodes[walk_end] + + relevant_neighbours = get_relevant_neighbours(end_node, transport_mode) + + for neighbour in relevant_neighbours: if neighbour in visited: # there exists a shorter walk to neighbour continue @@ -114,5 +127,6 @@ def find_shortest_path(nodes, source_id, target_id): new_dist = walk_dist + length_haversine(nodes[walk_end], neighbour) new_walk = walk + (neighbour.id,) heapq.heappush(queue, (new_dist, new_walk)) + # no path found return None @@ -47,17 +47,28 @@ def show_unconnected_nodes(): @post('/shortest-path') def shortest_path(body): body = json.loads(body) +<<<<<<< HEAD source_id = algorithms.grid_search(grid, store.Node(-1, body['lat1'], body['lng1'])) target_id = algorithms.grid_search(grid, store.Node(-1, body['lat2'], body['lng2'])) - - path = algorithms.find_shortest_path(nodes, source_id, target_id) - print(path) - response = { - "path": [(nodes[node].lat, nodes[node].lng) for node in path]} +======= + transport_mode = body['transport_mode'] + + source_id = algorithms.get_closest_node_id(nodes, + store.Node(-1, body['lat1'], + body['lng1']) + transport_mode) + target_id = algorithms.get_closest_node_id(nodes, + store.Node(-1, body['lat2'], + body['lng2']) + transport_mode) +>>>>>>> 532c0cb... wip + + path = algorithms.find_shortest_path(nodes, source_id, target_id, transport_mode) + response = {"path": [(nodes[node].lat, nodes[node].lng) for node in path]} return json.dumps(response) @@ -7,7 +7,8 @@ class Node: self.id = id self.lat = float(lat) self.lng = float(lng) - self.neighbours = [] + self.neighbours_bike = [] + self.neighbours_car = [] self.parent = None self.size = 1 @@ -45,25 +46,43 @@ class Node: parser = None # Have a global reusable parser object -def add_neighbours(nodes): +def add_neighbours_bike(nodes): for way in parser.iter_ways(): if 'highway' not in way['tags']: continue + print(way) + road = way['road'] for i in range(len(road) - 1): node1 = road[i] node2 = road[i + 1] +<<<<<<< HEAD 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]) +======= + if suitable_car(way): + nodes[node1].neighbours_car.append(nodes[node2]) + nodes[node2].neighbours_car.append(nodes[node1]) + + if suitable_bike(way): + nodes[node1].neighbours_bike.append(nodes[node2]) + nodes[node2].neighbours_bike.append(nodes[node1]) +>>>>>>> 532c0cb... wip return nodes +def add_neighbours_car(nodes): + for way in parser.iter_ways(): + if 'highway' not in way['tags']: + continue + + def extract_osm_nodes(f_name): global parser parser = get_default_parser(f_name) @@ -78,7 +97,7 @@ def extract_osm_nodes(f_name): # Remove nodes without neighbours for node_id, node in nodes.copy().items(): - if not node.neighbours: + if not node.neighbours_car or not node.neighbours_bike: del nodes[node_id] # Construct a forest of disjoint trees. @@ -131,3 +150,40 @@ 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 diff --git a/templates/index.html b/templates/index.html index b29f84f..00e6208 100644 --- a/templates/index.html +++ b/templates/index.html @@ -9,6 +9,17 @@ <form id="path-form"> <div class="row" > <div class="col"> + Mode of transport: + <div> + <input type="radio" name="transport-mode" id="transport-mode-bike" checked="true" /> + <label for="transport-mode-bike">Bike</label> + </div> + <div> + <input type="radio" name="transport-mode" id="transport-mode-car" /> + <label for="transport-mode-car">Car</label> + </div> + </div> + <div class="col"> Place marker for: <div> <input type="radio" name="marker-point" id="marker-point-start" checked="true" /> @@ -47,4 +58,4 @@ {{ templates/index.js }} </body> -</html>
\ No newline at end of file +</html> diff --git a/templates/index.js b/templates/index.js index 01e3880..42f8398 100644 --- a/templates/index.js +++ b/templates/index.js @@ -19,7 +19,10 @@ async function postShortestPath(event){ if(!lat1 || !lng1 || !lat2 || !lng2) return alert('Formatting Error: Coordinates are not float values.') - req = {lat1, lng1, lat2, lng2} // Dictionary auto-keys + const transport_mode_elem = document.getElementById("transport-mode-bike") + const transport_mode = transport_mode_elem.checked ? "bike" : "car" + + req = {lat1, lng1, lat2, lng2, transport_mode} // Dictionary auto-keys res = await fetch('/shortest-path', { method:'POST', |