diff options
| -rw-r--r-- | algorithms.py | 65 | ||||
| -rw-r--r-- | lib.py | 77 | ||||
| -rw-r--r-- | server.py | 32 | ||||
| -rw-r--r-- | store.py | 19 |
4 files changed, 149 insertions, 44 deletions
diff --git a/algorithms.py b/algorithms.py index 6e01287..9f3fd78 100644 --- a/algorithms.py +++ b/algorithms.py @@ -10,22 +10,75 @@ def length_haversine(p1, p2): lat1, lng1, lat2, lng2 = map(math.radians, [lat1, lng1, lat2, lng2]) dlat = lat2 - lat1 dlng = lng2 - lng1 - a = math.sin(dlat / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlng / 2) ** 2 + a = math.sin(dlat / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin( + dlng / 2) ** 2 c = 2 * math.asin(math.sqrt(a)) return 6372797.560856 * c # return the distance in meters -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'. """ +def grid_search(grid, source_node): + """ + Finds closest node to source node by comparing distance to nodes within + nearest tiles in the grid. + """ + closest_nodes = [] + + source_key = (int(round(source_node.lat, 3) * 1000), int(round( + source_node.lng, 3) * 1000)) + + closest_tiles = find_nodes(0, grid, source_key) + + for tile_nodes in closest_tiles: + closest_nodes.append(get_closest_node(tile_nodes, source_node)) + + closest_node_id = get_closest_node(closest_nodes, source_node).id + + return closest_node_id + + +def find_nodes(offset, grid, source_key): + """ + Searches a grid in an outward "spiral" from source node fetching all tiles + which contain nodes. + """ + tiles = None + + while not tiles: + tiles = look_for_nodes(offset, grid, source_key) + offset += 1 + + return tiles + look_for_nodes(offset + 1, grid, source_key) + + +def look_for_nodes(offset, grid, source_key): + """Search for nearest tile containing nodes in an outward spiral.""" + tiles = [] + for i in range(-offset, offset + 1): + for j in range(-offset, offset + 1): + + if i in (-offset, offset) or j in (-offset, offset): + + key = (source_key[0] + j, source_key[1] + i) + + if key in grid.keys(): + tiles.append(grid[key]) + + return tiles + + +def get_closest_node(nodes, source_node): + """ + Searches through all nodes in a specified grid and return node + closes to source node. + """ min_node = None min_value = None - for node_id, node in nodes.items(): + for node in nodes: length = length_haversine(source_node, node) if min_node is None or length < min_value: - min_node = node_id + min_node = node min_value = length return min_node @@ -1,31 +1,57 @@ import os import re +import sys +import traceback from http.server import HTTPServer, BaseHTTPRequestHandler +try: + from pygments import highlight + from pygments.lexers import PythonLexer + from pygments.formatters import HtmlFormatter + have_pygment = True +except ModuleNotFoundError: + have_pygment = False + posts = {} gets = {} +def format_py(code): + if have_pygment: + formatter = HtmlFormatter() + formatter.noclasses = True # inline styles + return highlight(code, PythonLexer(), formatter) + else: + return "<code>{}</code>".format(code).replace("\n", "\n<br>") \ + .replace(" ", " ") + + def find_get(path): """ [Internal] - Used by the Handler class to try and find the correct handler for a GET request. """ + if path not in gets: + return 404, "" try: - return gets[path]() - except Exception as e: - print(type(e), e) - return "404" + return 200, gets[path]() + except Exception: + tb = traceback.format_exc() + print(tb, file=sys.stderr) + return 500, format_py(tb) def find_post(path, request): """ [Internal] - Used by the Handler class to try and find the correct handler for a POST request. """ + if path not in posts: + return 404, "" try: - return posts[path](request) - except Exception as e: - print(type(e), e) - return "404" + return 200, posts[path](request) + except Exception: + tb = traceback.format_exc() + print(tb, file=sys.stderr) + return 500, "" def get_relative_path(): @@ -35,7 +61,7 @@ def get_relative_path(): def read_html(relative_file_path): """ Reads the html file on the file location provided and injects any external files (marked with {{file_path}} ) - that may be present. Returns the html content as a string. + that may be present. Returns the html content as a string. Example: >>> html_string = read_html('templates/index.html') @@ -49,8 +75,8 @@ def read_html(relative_file_path): def inject_external_files(html_content): - """ [Internal] - Replaces {{ 'file_path' }} with the file content of that file - path. Useful for seperation of javascript and css files. + """ [Internal] - Replaces {{ 'file_path' }} with the file content of that file + pat. Useful for seperation of javascript and css files. Uses regex to capture the pattern. Here is a link to see how it works: https://regex101.com/r/v917NK/2 """ @@ -76,8 +102,8 @@ def inject_external_files(html_content): def post(route='/'): """ A decorator that takes in the route path as argument, and then - puts the post handler in the dictionary, with the route as a key. - The handler will receive one `str` argument called 'body', + puts the post handler in the dictionary, with the route as a key. + The handler will receive one `str` argument called 'body', where the body of the post request will exist. """ def decorator(handler_function): @@ -106,21 +132,14 @@ class Handler(BaseHTTPRequestHandler): different requests made to our server. """ - def _set_headers(self): - """ Sets the headers for a response. This is to tell the browser - the status of the request that was sent. '200' means that everything - went fine. - """ - self.send_response(200) - self.send_header("Content-type", "text/html") - self.end_headers() - def do_GET(self): """ Tries to find the handler for this GET request. The handler can - return either `bytes` or `str`. + return either `bytes` or `str`. """ - self._set_headers() - res = find_get(self.path) + status, res = find_get(self.path) + self.send_response(status) + self.send_header("Content-type", "text/html") + self.end_headers() if hasattr(res, 'encode'): self.wfile.write(res.encode()) else: @@ -131,11 +150,11 @@ class Handler(BaseHTTPRequestHandler): will get the 'body' of the request as the argument. The body is a `str`, formatted in JSON. """ - self.send_response(200) - self.end_headers() content_length = int(self.headers['Content-Length']) body = self.rfile.read(content_length) - res = find_post(self.path, body.decode('utf-8')) + status, res = find_post(self.path, body.decode('utf-8')) + self.send_response(status) + self.end_headers() self.wfile.write(res.encode()) @@ -143,4 +162,4 @@ def run_server(port=8314): server_address = ('127.0.0.1', port) # Should make the port a command line argument server = HTTPServer(server_address, Handler) print('Starting server on http://{}:{}.'.format(*server_address)) - server.serve_forever() + server.serve_forever()
\ No newline at end of file @@ -4,15 +4,17 @@ import algorithms import store from lib import run_server, get, post, read_html - +grid = None nodes = None - +unconnected_nodes = None @get('/') def index(): global nodes + global grid global unconnected_nodes - nodes, unconnected_nodes = store.extract_osm_nodes("university.osm") + + nodes, grid, unconnected_nodes = store.extract_osm_nodes("university.osm") return read_html('templates/index.html') @@ -20,11 +22,22 @@ def index(): @get('/show-area') def show_area(): rect = dict() - for (k, node) in enumerate(store.select_nodes_in_rectangle(nodes, 58.3984, 58.3990, 15.5733, 15.576)): + for (k, node) in enumerate( + store.select_nodes_in_rectangle(nodes, 58.3984, 58.3990, 15.5733, + 15.576)): rect[node.id] = node.coord_tuple() return json.dumps(rect) +@get('/favicon.ico') +def favicon(): + with open("data/favicon.ico", "rb") as image: + read_image = image.read() + image_bytes = bytearray(read_image) + + return image_bytes + + @get('/show-unconnected-nodes') def show_unconnected_nodes(): print(f"Showing {len(unconnected_nodes)} unconnected nodes") @@ -34,12 +47,17 @@ def show_unconnected_nodes(): @post('/shortest-path') def shortest_path(body): body = json.loads(body) - source_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat1'], body['lng1'])) - target_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat2'], body['lng2'])) + 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]} + response = { + "path": [(nodes[node].lat, nodes[node].lng) for node in path]} return json.dumps(response) @@ -68,9 +68,11 @@ def extract_osm_nodes(f_name): global parser parser = get_default_parser(f_name) nodes = dict() + grid = defaultdict() for node in parser.iter_nodes(): - nodes[node['id']] = Node(node['id'], node['lat'], node['lon']) + new_node = Node(node['id'], node['lat'], node['lon']) + nodes[node['id']] = new_node add_neighbours(nodes) @@ -109,7 +111,20 @@ def extract_osm_nodes(f_name): if node.find_root().id != best_root: unconnected_nodes.append(node) - return best_tree, unconnected_nodes + 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): |