diff options
Diffstat (limited to 'dashboard_website')
| -rw-r--r-- | dashboard_website/router.py | 129 |
1 files changed, 75 insertions, 54 deletions
diff --git a/dashboard_website/router.py b/dashboard_website/router.py index 60b1128..99c83d2 100644 --- a/dashboard_website/router.py +++ b/dashboard_website/router.py @@ -1,5 +1,4 @@ import numpy as np -import pandas as pd import requests from sklearn.cluster import KMeans @@ -61,27 +60,20 @@ def cluster_and_optimize(clues: [db.Clue], bikes: [db.Bike], end: db.Point, time :param time_diff: the maximum time difference between the longest trip and the average trip :param max_time: the maximum time of the trip :param n: the number of routes to create - :return: the routes + :return: a list of lists of clues (ordered by position on route), and a list of json route geojsons """ - regular_points = [] - for clue in clues: - regular_points.append(db.Point(clue.latitude, clue.longitude)) # Create a new column with normalized gps coordinates and centroids - normalized_points, norm_centroids = __normalize_points([db.Point(clue.latitude, clue.longitude) for clue in clues], - [db.Point(bike.latitude, bike.longitude) for bike in bikes]) + normalized_points, norm_centroids = __normalize_points(clues, bikes) # Cluster the coordinates kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) kmeans.fit(normalized_points) - # Create a dataframe with the gps coordinates and the cluster - df = pd.DataFrame({'gps': regular_points, 'cluster': kmeans.labels_}) - - # Create the coordinate list from the bikes (the centroids) and the routes (the clues) - routes = [] - for i in range(len(bikes)): - routes.append(df[df['cluster'] == i]['gps'].tolist()) + # Split the clues into clusters based on the cluster labels + routes = [[] for i in range(len(norm_centroids))] + for i, label in enumerate(kmeans.labels_): + routes[label].append(clues[i]) routes = __minimize_route_time_diff(routes, bikes, end, time_diff, n) @@ -89,22 +81,49 @@ def cluster_and_optimize(clues: [db.Clue], bikes: [db.Bike], end: db.Point, time for i in range(len(routes)): routes[i] = __remove_longest_waypoints(routes[i], bikes[i], end, max_time) + # Get the json of the routes + route_geo = [] + for i, route in enumerate(routes): + route_geo.append( + __get_json(__clues_to_string(route), __clues_to_string([bikes[i]]), __clues_to_string([end])[:-1])[ + 'waypoints']) + + # Use the waypoint_index to reorder each route + for i, route in enumerate(routes): + route = [route[j] for j in route_geo[i][0]['waypoint_index']] + routes[i] = route + return routes -def __points_to_string(point: [db.Point]): +def __clues_to_string(points: [db.Clue]): """ Takes a list of points and returns a string of the list of points - :param point: a list of points + :param points: a list of points :return: a string of the list of points """ string = '' - for i in point: + for i in points: string += str(i.longitude) + ',' + str(i.latitude) + ';' return string +def __get_json(coordinate_string, start, end): + """ + Takes a string of coordinates and returns the json of the route + :param coordinate_string: a string of coordinates + :param start: the start point of the trip + :param end: the end point of the trip + :return: the json of the route + """ + coordinates = requests.get( + 'http://acetyl.net:5000/trip/v1/bike/' + start + coordinate_string + end + '?roundtrip=false&source=first&destination=last&geometries=geojson') + coordinates = coordinates.json() + + return coordinates + + def __get_trip_time(coordinate_string, num_waypoints, start, end, time_per_waypoint=90): """ Takes a string of coordinates and returns the trip time in hours @@ -127,7 +146,7 @@ def __get_trip_time(coordinate_string, num_waypoints, start, end, time_per_waypo return total_time_hours -def __minimize_route_time_diff(routes: [db.Point], starts: [db.Point], end: db.Point, time_diff, n): +def __minimize_route_time_diff(routes: [db.Clue], starts: [db.Point], end: db.Point, time_diff, n): """ Takes a list of lists of coordinates, a list of start points, an end point, a time difference, and a number of routes :param routes: the list of lists of coordinates @@ -140,8 +159,8 @@ def __minimize_route_time_diff(routes: [db.Point], starts: [db.Point], end: db.P times = [] for i, route in enumerate(routes): - times.append(__get_trip_time(__points_to_string(route), len(route), __points_to_string([starts[i]]), - __points_to_string([end]))) + times.append(__get_trip_time(__clues_to_string(route), len(route), __clues_to_string([starts[i]]), + __clues_to_string([end])[:-1])) # Find the average trip time average_time = np.mean(times) @@ -167,7 +186,7 @@ def __minimize_route_time_diff(routes: [db.Point], starts: [db.Point], end: db.P return routes -def __remove_longest_waypoints(route_coordinates: [db.Point], start: db.Point, end: db.Point, max_time): +def __remove_longest_waypoints(route_coordinates: [db.Clue], start: db.Bike, end: db.Point, max_time): """ Takes a list of coordinates, a start point, an end point, and a maximum time and returns a list of coordinates :param route_coordinates: the list of coordinates @@ -177,8 +196,8 @@ def __remove_longest_waypoints(route_coordinates: [db.Point], start: db.Point, e :return: a list of coordinates """ # Find the trip time for the route - route_time = __get_trip_time(__points_to_string(route_coordinates), len(route_coordinates), - __points_to_string([start]), __points_to_string([end])) + route_time = __get_trip_time(__clues_to_string(route_coordinates), len(route_coordinates), + __clues_to_string([start]), __clues_to_string([end])[:-1]) # If the trip time is greater than the max time, remove the waypoint with the longest distance from the mean if route_time > max_time: @@ -191,18 +210,18 @@ def __remove_longest_waypoints(route_coordinates: [db.Point], start: db.Point, e return route_coordinates -def __normalize_points(coordinates: [db.Point], centroids: [db.Point]): +def __normalize_points(clues: [db.Clue], bikes: [db.Bike]): """ Takes a list of coordinates and a list of centroids and returns a list of normalized coordinates and a list of normalized centroids - :param coordinates: the list of coordinates - :param centroids: the list of centroids + :param clues: the list of coordinates + :param bikes: the list of centroids :return: the list of normalized coordinates and the list of normalized centroids """ # Create a list of latitudes and longitudes - latitudes = [i.latitude for i in coordinates] - longitudes = [i.longitude for i in coordinates] + latitudes = [i.latitude for i in clues] + longitudes = [i.longitude for i in clues] # Find the minimum and maximum latitudes and longitudes min_lat = min(latitudes) @@ -214,12 +233,12 @@ def __normalize_points(coordinates: [db.Point], centroids: [db.Point]): normalized_coordinates = [] normalized_centroids = [] - for i in coordinates: + for i in clues: normalized_coordinates.append( - [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)]) - for i in centroids: + [__min_max_normalize(i.latitude, min_lat, max_lat), __min_max_normalize(i.longitude, min_lon, max_lon)]) + for i in bikes: normalized_centroids.append( - [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)]) + [__min_max_normalize(i.latitude, min_lat, max_lat), __min_max_normalize(i.longitude, min_lon, max_lon)]) return normalized_coordinates, normalized_centroids @@ -235,52 +254,54 @@ def __min_max_normalize(value, min_value, max_value): return (value - min_value) / (max_value - min_value) -def __find_closest_coordinate(coordinates: [db.Point], centroid: db.Point): +def __find_closest_coordinate(clues: [db.Clue], centroid: db.Point): """ - Takes a list of coordinates and a centroid and returns the coordinate in the list that is closest to the centroid - :param coordinates: the list of coordinates + Takes a list of coordinates and a centroid and returns the clue in the list that is closest to the centroid + :param clues: the list of coordinates :param centroid: the centroid - :return: the coordinate in the list that is closest to the centroid + :return: the clue in the list that is closest to the centroid """ - closest_coordinate = coordinates[0] + # Convert the clues to a list of points + closest_coordinate = clues[0] closest_coordinate_distance = __distance(closest_coordinate, centroid) - for coordinate in coordinates: - if __distance(coordinate, centroid) < closest_coordinate_distance: - closest_coordinate = coordinate - closest_coordinate_distance = __distance(coordinate, centroid) + for clue in clues: + if __distance(clue, centroid) < closest_coordinate_distance: + closest_coordinate = clue + closest_coordinate_distance = __distance(clue, centroid) return closest_coordinate -def __find_farthest_coordinate(coordinates: [db.Point], centroid: db.Point): +def __find_farthest_coordinate(clues: [db.Clue], centroid: db.Point): """ - Takes a list of coordinates and a centroid and returns the coordinate in the list that is farthest from the centroid - :param coordinates: the list of coordinates + Takes a list of coordinates and a centroid and returns the clue in the list that is farthest from the centroid + :param clues: the list of coordinates :param centroid: the centroid - :return: the coordinate in the list that is farthest from the centroid + :return: the clue in the list that is farthest from the centroid """ - farthest_coordinate = coordinates[0] + farthest_coordinate = clues[0] farthest_coordinate_distance = __distance(farthest_coordinate, centroid) - for coordinate in coordinates: - if __distance(coordinate, centroid) > farthest_coordinate_distance: - farthest_coordinate = coordinate - farthest_coordinate_distance = __distance(coordinate, centroid) + for clue in clues: + if __distance(clue, centroid) > farthest_coordinate_distance: + farthest_coordinate = clue + farthest_coordinate_distance = __distance(clue, centroid) return farthest_coordinate -def __mean_center(coordinates: [db.Point]): +def __mean_center(clues: [db.Clue]): """ Takes a list of coordinates and returns the mean center of the coordinates - :param coordinates: the list of coordinates + :param clues: the list of coordinates :return: the mean center of the coordinates """ - return db.Point(np.mean([i.latitude for i in coordinates]), np.mean([i.longitude for i in coordinates])) + return db.Point(np.mean([coordinate.latitude for coordinate in clues]), + np.mean([coordinate.longitude for coordinate in clues])) -def __distance(coordinate1: db.Point, coordinate2: db.Point): +def __distance(coordinate1: db.Clue, coordinate2: db.Point): """ Takes two coordinates and returns the distance between them :param coordinate1: the first coordinate |