diff options
| -rw-r--r-- | algorithms.py | 15 | ||||
| -rw-r--r-- | server.py | 33 | ||||
| -rw-r--r-- | templates/index.js | 2 |
3 files changed, 37 insertions, 13 deletions
diff --git a/algorithms.py b/algorithms.py index 1e70fa1..11f9e6b 100644 --- a/algorithms.py +++ b/algorithms.py @@ -69,24 +69,29 @@ def find_shortest_path(nodes, source_id, target_id): """ Return the shortest path using Dijkstra's algortihm. """ # queue contains multiple (walk_dist, (node_0, node_1, ... node_n))-tuples # where (node_0, node_1, ... node_n) is a walk to node_n - # and walk_dist is the total length of the walk in meters + # and walk_dist is the total length of the walk in meters. + # iterations is the number of iterations the algorithm took before finding + # this node and is used for coloring. queue = [(0, (source_id,))] iterations = 0 - visited = set() + visited = {} while queue: # consider an unchecked walk walk_dist, walk = heapq.heappop(queue) - walk_end = walk[-1] iterations += 1 + walk_end = walk[-1] if walk_end == target_id: # you have reached your destination - return walk, iterations + return walk, iterations, visited if walk_end in visited: # there exists a shorter walk to walk_end continue # otherwise this is the shortest walk to walk_end - visited.add(walk_end) + if len(walk) == 1: + visited[walk_end] = (walk[-1], walk[-1], iterations) + else: + visited[walk_end] = (walk[-2], walk[-1], iterations) # consider all our neighbours for neighbour in nodes[walk_end].neighbours: if neighbour in visited: @@ -23,20 +23,39 @@ def show_area(): return json.dumps(rect) +def color_edges(nodes, colorer): + """ Color all edges in a list of nodes with a coloring function. """ + return [{"path": [[node0.lat, node0.lng], + [node1.lat, node1.lng]], + "color": colorer(colorer_t)} + for node0, node1, colorer_t in 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'])) - path, iterations = algorithms.find_shortest_path(nodes, source_id, target_id) - edges = [] - for i in range(len(path)-1): - edges.append({"path": [[nodes[path[i]].lat, nodes[path[i]].lng], - [nodes[path[i+1]].lat, nodes[path[i+1]].lng]], - "color": "#ff0000"}) + path, total_iters, edges = algorithms.find_shortest_path(nodes, source_id, target_id) + + def shortest_path_color(_): + """ Color edge as the shortest path. """ + return "#2674CA" + + def edge_color_iter(iters): + """ Color edge depending on how many iterations were taken to get there. """ + return algorithms.lerp_color("#ff0000", "#00cc00", iters/total_iters) + + shortest_path = color_edges([(nodes[path[i+0]], nodes[path[i+1]], None) + for i in range(len(path)-1)], + shortest_path_color) + + all_edges = color_edges([(nodes[node0], nodes[node1], iterations) + for node0, node1, iterations in edges.values()], + edge_color_iter) - return json.dumps({"edges": edges}) + return json.dumps({"edges": all_edges + shortest_path}) run_server() diff --git a/templates/index.js b/templates/index.js index a7cfd90..f7550c0 100644 --- a/templates/index.js +++ b/templates/index.js @@ -30,7 +30,7 @@ async function postShortestPath(event){ res = await res.json() for (edge of res.edges) { - console.log(edge.path) + console.log(edge) L.polyline(edge.path, { color: edge.color }).addTo(map) |