diff options
| -rw-r--r-- | algorithms.py | 65 | ||||
| -rw-r--r-- | lib.py | 77 | ||||
| -rw-r--r-- | server.py | 37 | ||||
| -rw-r--r-- | store.py | 82 | ||||
| -rw-r--r-- | templates/index.js | 10 |
5 files changed, 225 insertions, 46 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,30 +4,55 @@ 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 - nodes = store.extract_osm_nodes("linkoping.osm") + global grid + global unconnected_nodes + + nodes, grid, unconnected_nodes = store.extract_osm_nodes("linkoping.osm") + return read_html('templates/index.html') @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") + return json.dumps({node.id: node.coord_tuple() for node in 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) response = {"path": [(nodes[node].lat, nodes[node].lng) for node in path]} @@ -1,4 +1,5 @@ from osm_parser import get_default_parser +from collections import defaultdict class Node: @@ -8,6 +9,34 @@ class Node: 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 @@ -26,6 +55,8 @@ def add_neighbours(nodes, parser): 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 @@ -33,18 +64,63 @@ def add_neighbours(nodes, parser): def extract_osm_nodes(f_name): 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, parser) - # remove nodes without neighbours + # Remove nodes without neighbours for node_id, node in nodes.copy().items(): if not node.neighbours: del nodes[node_id] - return nodes + # 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) + + 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): diff --git a/templates/index.js b/templates/index.js index b7b3b58..01e3880 100644 --- a/templates/index.js +++ b/templates/index.js @@ -49,7 +49,6 @@ map.on('click', handleMapClick) function showMarker(){ var marker = L.marker([58.3984, 15.5733]).addTo(map) } - showMarker() async function showMarkers() { @@ -59,5 +58,12 @@ async function showMarkers() { var marker = L.marker(res[key]).addTo(map) } } - showMarkers() + +async function showUnconnectedMarkers() { + const res = await fetch('/show-unconnected-nodes').then(res => res.json()); + for (let key in res) { + var marker = L.marker(res[key]).addTo(map) + } +} +showUnconnectedMarkers() |