diff options
Diffstat (limited to 'algorithms.py')
| -rw-r--r-- | algorithms.py | 51 |
1 files changed, 26 insertions, 25 deletions
diff --git a/algorithms.py b/algorithms.py index 9f3fd78..8c63968 100644 --- a/algorithms.py +++ b/algorithms.py @@ -1,8 +1,14 @@ import heapq import math +import store def length_haversine(p1, p2): + """ + The distance in meters between two coordinates on a sphere. + + Assumes p1=(lat1, lng1) and p2=(lat2, lng2) in degrees. + """ lat1 = p1.lat lng1 = p1.lng lat2 = p2.lat @@ -10,67 +16,62 @@ 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 grid_search(grid, source_node): +def grid_search(grid, lat, lng): """ 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)) - + source_node = store.Node(-1, lat, lng) + source_key = ( + int(round(source_node.lat, 3) * 1000), + int(round(source_node.lng, 3) * 1000), + ) + + closest_tiles = find_nodes(grid, source_key) + closest_nodes = [get_closest_node(tile_nodes, source_node) + for tile_nodes in closest_tiles] closest_node_id = get_closest_node(closest_nodes, source_node).id - return closest_node_id -def find_nodes(offset, grid, source_key): +def find_nodes(grid, source_key, offset=0): """ Searches a grid in an outward "spiral" from source node fetching all tiles which contain nodes. """ tiles = None + # search further out until we find nodes while not tiles: - tiles = look_for_nodes(offset, grid, source_key) + tiles = look_for_nodes(grid, source_key, offset) offset += 1 - return tiles + look_for_nodes(offset + 1, grid, source_key) + # include another layer since they might contain closer nodes + return tiles + look_for_nodes(grid, source_key, offset + 1) -def look_for_nodes(offset, grid, source_key): - """Search for nearest tile containing nodes in an outward spiral.""" +def look_for_nodes(grid, source_key, offset): + """Search for nearest tile containing nodes in a 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. + Search through all nodes in a specified grid and return the node + closest to source_node. """ min_node = None min_value = None |