Merge branch 'grid-search' into 'master'

Grid search

See merge request tdde25-2020/tdde25-2020-projekt-sg3-maps-05!10

4 files changed, 91 insertions, 18 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
diff --git a/lib.py b/lib.py
index 2ceb51d..8a31276 100644
--- a/lib.py
+++ b/lib.py
@@ -23,7 +23,7 @@ def format_py(code):
         return highlight(code, PythonLexer(), formatter)
     else:
         return "<code>{}</code>".format(code).replace("\n", "\n<br>") \
-                                             .replace(" ", "&nbsp;")
+            .replace(" ", "&nbsp;")
 
 
 def find_get(path):
@@ -61,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')
@@ -75,7 +75,7 @@ def read_html(relative_file_path):
 
 
 def inject_external_files(html_content):
-    """ [Internal] - Replaces {{ 'file_path' }} with the file content of that file 
+    """ [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
@@ -102,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):
@@ -134,7 +134,7 @@ class Handler(BaseHTTPRequestHandler):
 
     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`.
         """
         status, res = find_get(self.path)
         self.send_response(status)
@@ -162,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
diff --git a/server.py b/server.py
index 9a275e9..4ba7506 100644
--- a/server.py
+++ b/server.py
@@ -4,13 +4,17 @@ import algorithms
 import store
 from lib import run_server, get, post, read_html
 
+grid = None
 nodes = None
 
 
 @get('/')
 def index():
     global nodes
-    nodes = store.extract_osm_nodes("university.osm")
+    global grid
+
+    nodes, grid = store.extract_osm_nodes("university.osm")
+
     return read_html('templates/index.html')
 
 
@@ -43,7 +47,8 @@ def shortest_path(body):
 
     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)
 
diff --git a/store.py b/store.py
index 4af13ef..315b836 100644
--- a/store.py
+++ b/store.py
@@ -1,4 +1,5 @@
 from osm_parser import get_default_parser
+from collections import defaultdict
 
 
 class Node:
@@ -36,18 +37,32 @@ 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)
 
-    # 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
+    # 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
 
 
 def select_nodes_in_rectangle(nodes, min_lat, max_lat, min_long, max_long):