Grid search

1 files changed, 59 insertions, 6 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