From 0025654ae13215ed87830d542ae88924e084ba1c Mon Sep 17 00:00:00 2001 From: itsGarrin Date: Tue, 7 Nov 2023 13:17:44 -0500 Subject: Added a max time parameter --- ZestySalesman.ipynb | 186 ++++++++++++++++++++++--------------------- utils.py | 224 +++++++++++++++++++++++++--------------------------- 2 files changed, 201 insertions(+), 209 deletions(-) diff --git a/ZestySalesman.ipynb b/ZestySalesman.ipynb index 1d1fd59..57593d2 100644 --- a/ZestySalesman.ipynb +++ b/ZestySalesman.ipynb @@ -2,13 +2,13 @@ "cells": [ { "cell_type": "code", - "execution_count": 24, + "execution_count": 1, "id": "initial_id", "metadata": { "collapsed": true, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.608101Z", - "start_time": "2023-11-07T01:17:52.539921Z" + "end_time": "2023-11-07T18:15:48.594817Z", + "start_time": "2023-11-07T18:15:47.605833Z" } }, "outputs": [], @@ -20,7 +20,7 @@ }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 2, "outputs": [], "source": [ "# Load the data\n", @@ -32,15 +32,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.672617Z", - "start_time": "2023-11-07T01:17:52.544450Z" + "end_time": "2023-11-07T18:15:48.604219Z", + "start_time": "2023-11-07T18:15:48.596141Z" } }, "id": "73b780e762c9de37" }, { "cell_type": "code", - "execution_count": 26, + "execution_count": 3, "outputs": [], "source": [ "# Create three centroids, one in the North End, one in the Financial District, and one in the Back Bay\n", @@ -51,15 +51,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.673868Z", - "start_time": "2023-11-07T01:17:52.558087Z" + "end_time": "2023-11-07T18:15:48.608755Z", + "start_time": "2023-11-07T18:15:48.604788Z" } }, "id": "be4c8c1d77842ef7" }, { "cell_type": "code", - "execution_count": 27, + "execution_count": 4, "outputs": [], "source": [ "# Combine the two lists and add a column to indicate the list\n", @@ -73,15 +73,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.702176Z", - "start_time": "2023-11-07T01:17:52.568817Z" + "end_time": "2023-11-07T18:15:48.613233Z", + "start_time": "2023-11-07T18:15:48.607380Z" } }, "id": "ffe4025e97a6c6b9" }, { "cell_type": "code", - "execution_count": 28, + "execution_count": 5, "outputs": [], "source": [ "# Remove all columns but name and gps\n", @@ -90,15 +90,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.706405Z", - "start_time": "2023-11-07T01:17:52.577745Z" + "end_time": "2023-11-07T18:15:48.613309Z", + "start_time": "2023-11-07T18:15:48.611827Z" } }, "id": "72657779b4484aae" }, { "cell_type": "code", - "execution_count": 29, + "execution_count": 6, "outputs": [], "source": [ "# Convert the gps column to a list of lists for k-means\n", @@ -108,15 +108,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.706689Z", - "start_time": "2023-11-07T01:17:52.581919Z" + "end_time": "2023-11-07T18:15:48.617922Z", + "start_time": "2023-11-07T18:15:48.614428Z" } }, "id": "a157ffaec020a29a" }, { "cell_type": "code", - "execution_count": 30, + "execution_count": 7, "outputs": [ { "data": { @@ -135,8 +135,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:17:52.707232Z", - "start_time": "2023-11-07T01:17:52.597329Z" + "end_time": "2023-11-07T18:15:48.627782Z", + "start_time": "2023-11-07T18:15:48.618140Z" } }, "id": "a03ebde91b87fa3b" @@ -163,7 +163,7 @@ }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 8, "outputs": [ { "name": "stderr", @@ -185,8 +185,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:19.800168Z", - "start_time": "2023-11-07T01:17:52.606044Z" + "end_time": "2023-11-07T18:16:41.294672Z", + "start_time": "2023-11-07T18:15:48.624793Z" } }, "id": "ee9b3c1ecb360976" @@ -197,13 +197,17 @@ "## Create JSON" ], "metadata": { - "collapsed": false + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T17:33:02.697755Z", + "start_time": "2023-11-07T17:33:02.687460Z" + } }, "id": "c85b8ef869e35006" }, { "cell_type": "code", - "execution_count": 32, + "execution_count": 9, "outputs": [], "source": [ "# Create a JSON request for the API\n", @@ -214,15 +218,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:19.807296Z", - "start_time": "2023-11-07T01:18:19.799849Z" + "end_time": "2023-11-07T18:16:41.298495Z", + "start_time": "2023-11-07T18:16:41.293559Z" } }, "id": "aa618161182b5b07" }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 10, "outputs": [], "source": [ "# Create a dataframe from the JSON\n", @@ -232,15 +236,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:22.014184Z", - "start_time": "2023-11-07T01:18:19.803262Z" + "end_time": "2023-11-07T18:16:43.656626Z", + "start_time": "2023-11-07T18:16:41.303093Z" } }, "id": "32c485788eedd94" }, { "cell_type": "code", - "execution_count": 34, + "execution_count": 11, "outputs": [], "source": [ "# Add columns for the route number\n", @@ -253,20 +257,20 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:22.024878Z", - "start_time": "2023-11-07T01:18:22.017438Z" + "end_time": "2023-11-07T18:16:43.676130Z", + "start_time": "2023-11-07T18:16:43.661970Z" } }, "id": "49dba1f17ca8337e" }, { "cell_type": "code", - "execution_count": 35, + "execution_count": 12, "outputs": [ { "data": { - "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n168 64 0 \n169 65 0 \n170 66 0 \n171 67 0 \n172 68 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL... 6.024489 \n2 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n3 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n4 HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA... 39.201677 \n.. ... ... \n168 cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC... 22.776295 \n169 g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA... 12.789906 \n170 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n171 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n172 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.055569, 42.364032] -71.055569 42.364032 \n2 [-71.056164, 42.366918] -71.056164 42.366918 \n3 [-71.055561, 42.368861] -71.055561 42.368861 \n4 [-71.062507, 42.365968] -71.062507 42.365968 \n.. ... ... ... ... \n168 Alleghany Street [-71.099348, 42.33047] -71.099348 42.330470 \n169 Tremont Street [-71.098267, 42.332009] -71.098267 42.332009 \n170 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n171 [-71.093834, 42.339096] -71.093834 42.339096 \n172 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n168 2 \n169 2 \n170 2 \n171 2 \n172 2 \n\n[173 rows x 9 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL...6.024489[-71.055569, 42.364032]-71.05556942.3640321
220G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
330gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
440HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA...39.201677[-71.062507, 42.365968]-71.06250742.3659681
..............................
168640cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304702
169650g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA...12.789906Tremont Street[-71.098267, 42.332009]-71.09826742.3320092
170660e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324012
171670k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390962
172680DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

173 rows × 9 columns

\n
" + "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n151 62 0 \n152 63 0 \n153 64 0 \n154 65 0 \n155 66 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL... 6.024489 \n2 5IgsgAqJLID7AAAAHgAAAAwAAAAIAAAAz5ffQcMBVEDFYK... 5.871835 \n3 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n4 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n.. ... ... \n151 lhgDgIkYA4BkAAAAIgEAAFoBAAAaAAAAJyAzQWNrAEI8Ax... 7.134933 \n152 MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh... 11.504463 \n153 bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx... 8.340476 \n154 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n155 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.055569, 42.364032] -71.055569 42.364032 \n2 [-71.055582, 42.365251] -71.055582 42.365251 \n3 [-71.056164, 42.366918] -71.056164 42.366918 \n4 [-71.055561, 42.368861] -71.055561 42.368861 \n.. ... ... ... ... \n151 [-71.083465, 42.34194] -71.083465 42.341940 \n152 [-71.094327, 42.341231] -71.094327 42.341231 \n153 [-71.095003, 42.342001] -71.095003 42.342001 \n154 [-71.093834, 42.339096] -71.093834 42.339096 \n155 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n151 2 \n152 2 \n153 2 \n154 2 \n155 2 \n\n[156 rows x 9 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL...6.024489[-71.055569, 42.364032]-71.05556942.3640321
2205IgsgAqJLID7AAAAHgAAAAwAAAAIAAAAz5ffQcMBVEDFYK...5.871835[-71.055582, 42.365251]-71.05558242.3652511
330G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
440gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
..............................
151620lhgDgIkYA4BkAAAAIgEAAFoBAAAaAAAAJyAzQWNrAEI8Ax...7.134933[-71.083465, 42.34194]-71.08346542.3419402
152630MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh...11.504463[-71.094327, 42.341231]-71.09432742.3412312
153640bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx...8.340476[-71.095003, 42.342001]-71.09500342.3420012
154650k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390962
155660DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

156 rows × 9 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -278,8 +282,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:22.033944Z", - "start_time": "2023-11-07T01:18:22.026906Z" + "end_time": "2023-11-07T18:16:43.691423Z", + "start_time": "2023-11-07T18:16:43.681109Z" } }, "id": "f231d9a35358988c" @@ -296,14 +300,14 @@ }, { "cell_type": "code", - "execution_count": 36, + "execution_count": 13, "outputs": [ { "data": { - "text/plain": "", - "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" }, - "execution_count": 36, + "execution_count": 13, "metadata": {}, "output_type": "execute_result" } @@ -328,8 +332,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:22.118478Z", - "start_time": "2023-11-07T01:18:22.036338Z" + "end_time": "2023-11-07T18:16:43.877482Z", + "start_time": "2023-11-07T18:16:43.683653Z" } }, "id": "80fd847da2833913" @@ -346,14 +350,14 @@ }, { "cell_type": "code", - "execution_count": 37, + "execution_count": 14, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "Route 1 has 102 waypoints\n", - "Route 2 has 67 waypoints\n" + "Route 1 has 87 waypoints\n", + "Route 2 has 65 waypoints\n" ] } ], @@ -367,22 +371,22 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:22.120347Z", - "start_time": "2023-11-07T01:18:22.104950Z" + "end_time": "2023-11-07T18:16:43.895169Z", + "start_time": "2023-11-07T18:16:43.807251Z" } }, "id": "f53c97acec1c2fc4" }, { "cell_type": "code", - "execution_count": 38, + "execution_count": 15, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "The trip will take 12.788333333333334 hours\n", - "The trip will take 13.1675 hours\n" + "The trip will take 9.916944444444445 hours\n", + "The trip will take 9.295277777777779 hours\n" ] } ], @@ -397,8 +401,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:24.705352Z", - "start_time": "2023-11-07T01:18:22.107540Z" + "end_time": "2023-11-07T18:16:46.273794Z", + "start_time": "2023-11-07T18:16:43.813481Z" } }, "id": "a3ec09dfb5cbb5b3" @@ -415,7 +419,7 @@ }, { "cell_type": "code", - "execution_count": 47, + "execution_count": 16, "outputs": [ { "name": "stderr", @@ -438,8 +442,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:14.864605Z", - "start_time": "2023-11-07T01:21:59.518900Z" + "end_time": "2023-11-07T18:17:05.599874Z", + "start_time": "2023-11-07T18:16:46.275388Z" } }, "id": "bb6e00857e8175c0" @@ -456,7 +460,7 @@ }, { "cell_type": "code", - "execution_count": 48, + "execution_count": 17, "outputs": [], "source": [ "# Create a JSON request for the API\n", @@ -468,15 +472,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:16.725390Z", - "start_time": "2023-11-07T01:22:16.722334Z" + "end_time": "2023-11-07T18:17:05.600430Z", + "start_time": "2023-11-07T18:17:05.595893Z" } }, "id": "e886e061f86a2118" }, { "cell_type": "code", - "execution_count": 49, + "execution_count": 18, "outputs": [], "source": [ "# Create a dataframe from the JSON\n", @@ -487,15 +491,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:19.351381Z", - "start_time": "2023-11-07T01:22:17.034813Z" + "end_time": "2023-11-07T18:17:09.536438Z", + "start_time": "2023-11-07T18:17:05.601412Z" } }, "id": "23e4682fe9e30631" }, { "cell_type": "code", - "execution_count": 50, + "execution_count": 19, "outputs": [], "source": [ "# Add columns for the route number\n", @@ -509,20 +513,20 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:19.360710Z", - "start_time": "2023-11-07T01:22:19.355746Z" + "end_time": "2023-11-07T18:17:09.555728Z", + "start_time": "2023-11-07T18:17:09.541352Z" } }, "id": "c3a5c5d6f3ac46c0" }, { "cell_type": "code", - "execution_count": 51, + "execution_count": 20, "outputs": [ { "data": { - "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n170 29 0 \n171 30 0 \n172 31 0 \n173 32 0 \n174 33 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA... 4.756158 \n2 tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii... 4.525535 \n3 sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA... 7.844897 \n4 VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA... 22.681980 \n.. ... ... \n170 gLshgIS7IYAAAAAAPAAAAAAAAAAAAAAAAAAAAPGU1UAAAA... 10.782119 \n171 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n172 cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC... 22.776295 \n173 s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA... 4.111715 \n174 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.060933, 42.376178] -71.060933 42.376178 \n2 [-71.060753, 42.376391] -71.060753 42.376391 \n3 [-71.060948, 42.380436] -71.060948 42.380436 \n4 Factory Street [-71.061206, 42.398809] -71.061206 42.398809 \n.. ... ... ... ... \n170 [-71.10963, 42.336448] -71.109630 42.336448 \n171 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n172 Alleghany Street [-71.099348, 42.33047] -71.099348 42.330470 \n173 [-71.09454, 42.325354] -71.094540 42.325354 \n174 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n170 3 \n171 3 \n172 3 \n173 3 \n174 3 \n\n[175 rows x 9 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA...4.756158[-71.060933, 42.376178]-71.06093342.3761781
220tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii...4.525535[-71.060753, 42.376391]-71.06075342.3763911
330sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA...7.844897[-71.060948, 42.380436]-71.06094842.3804361
440VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA...22.681980Factory Street[-71.061206, 42.398809]-71.06120642.3988091
..............................
170290gLshgIS7IYAAAAAAPAAAAAAAAAAAAAAAAAAAAPGU1UAAAA...10.782119[-71.10963, 42.336448]-71.10963042.3364483
171300e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324013
172310cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304703
173320s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA...4.111715[-71.09454, 42.325354]-71.09454042.3253543
174330DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397623
\n

175 rows × 9 columns

\n
" + "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n170 31 0 \n171 32 0 \n172 33 0 \n173 34 0 \n174 35 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA... 4.756158 \n2 tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii... 4.525535 \n3 sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA... 7.844897 \n4 VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA... 22.681980 \n.. ... ... \n170 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n171 g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA... 12.789906 \n172 cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC... 22.776295 \n173 s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA... 4.111715 \n174 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.060933, 42.376178] -71.060933 42.376178 \n2 [-71.060753, 42.376391] -71.060753 42.376391 \n3 [-71.060948, 42.380436] -71.060948 42.380436 \n4 Factory Street [-71.061206, 42.398809] -71.061206 42.398809 \n.. ... ... ... ... \n170 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n171 Tremont Street [-71.098267, 42.332009] -71.098267 42.332009 \n172 Alleghany Street [-71.099348, 42.33047] -71.099348 42.330470 \n173 [-71.09454, 42.325354] -71.094540 42.325354 \n174 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n170 3 \n171 3 \n172 3 \n173 3 \n174 3 \n\n[175 rows x 9 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA...4.756158[-71.060933, 42.376178]-71.06093342.3761781
220tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii...4.525535[-71.060753, 42.376391]-71.06075342.3763911
330sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA...7.844897[-71.060948, 42.380436]-71.06094842.3804361
440VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA...22.681980Factory Street[-71.061206, 42.398809]-71.06120642.3988091
..............................
170310e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324013
171320g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA...12.789906Tremont Street[-71.098267, 42.332009]-71.09826742.3320093
172330cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304703
173340s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA...4.111715[-71.09454, 42.325354]-71.09454042.3253543
174350DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397623
\n

175 rows × 9 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -534,8 +538,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:19.375055Z", - "start_time": "2023-11-07T01:22:19.364517Z" + "end_time": "2023-11-07T18:17:09.566860Z", + "start_time": "2023-11-07T18:17:09.558481Z" } }, "id": "17a8cc8fed5450a6" @@ -552,14 +556,14 @@ }, { "cell_type": "code", - "execution_count": 52, + "execution_count": 21, "outputs": [ { "data": { - "text/plain": "", - "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" }, - "execution_count": 52, + "execution_count": 21, "metadata": {}, "output_type": "execute_result" } @@ -584,8 +588,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:20.246243Z", - "start_time": "2023-11-07T01:22:20.167900Z" + "end_time": "2023-11-07T18:17:09.664747Z", + "start_time": "2023-11-07T18:17:09.566588Z" } }, "id": "702adaec008a6ec8" @@ -602,15 +606,15 @@ }, { "cell_type": "code", - "execution_count": 53, + "execution_count": 22, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Route 1 has 57 waypoints\n", - "Route 2 has 80 waypoints\n", - "Route 3 has 32 waypoints\n" + "Route 2 has 78 waypoints\n", + "Route 3 has 34 waypoints\n" ] } ], @@ -626,23 +630,23 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:21.994911Z", - "start_time": "2023-11-07T01:22:21.992304Z" + "end_time": "2023-11-07T18:17:09.666099Z", + "start_time": "2023-11-07T18:17:09.634214Z" } }, "id": "4106acf2adad01d7" }, { "cell_type": "code", - "execution_count": 54, + "execution_count": 23, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The trip will take 9.175 hours\n", - "The trip will take 9.341111111111111 hours\n", - "The trip will take 9.398333333333333 hours\n" + "The trip will take 8.926111111111112 hours\n", + "The trip will take 9.533333333333333 hours\n" ] } ], @@ -661,22 +665,22 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:22:25.544575Z", - "start_time": "2023-11-07T01:22:23.206069Z" + "end_time": "2023-11-07T18:17:15.097884Z", + "start_time": "2023-11-07T18:17:09.637760Z" } }, "id": "c58106faf0fc7f4e" }, { "cell_type": "code", - "execution_count": 46, + "execution_count": 23, "outputs": [], "source": [], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T01:18:42.067793Z", - "start_time": "2023-11-07T01:18:42.056069Z" + "end_time": "2023-11-07T18:17:15.098169Z", + "start_time": "2023-11-07T18:17:15.094392Z" } }, "id": "a2f10e3152b95a69" diff --git a/utils.py b/utils.py index 2898b3d..a4b789d 100644 --- a/utils.py +++ b/utils.py @@ -5,47 +5,26 @@ import requests from sklearn.cluster import KMeans -# Given a dataframe of coordinates and centroids, cluster the coordinates, minimize the time difference, and return the routes -def cluster_and_minimize_2(df, centroids, norm_centroids, end, time_diff, minimize=True, n=2): +def cluster_and_minimize_2(df, centroids, norm_centroids, end, time_diff, max_time=24, n=2): # Cluster the coordinates kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) - - # Fit the coordinates to the clusters kmeans.fit(df['normalized_gps'].values.tolist()) - # Add the cluster labels to the dataframe df['cluster'] = kmeans.labels_ - - # Create centroid strings centroid_1 = list_to_string([centroids[0]]) centroid_2 = list_to_string([centroids[1]]) # Return the list of locations in each cluster route_1 = df[df['cluster'] == 0] - route_1_stops = len(route_1['gps'].values.tolist()) - route_1_str = list_to_string(route_1['gps'].values.tolist()) - route_2 = df[df['cluster'] == 1] - route_2_stops = len(route_2['gps'].values.tolist()) - route_2_str = list_to_string(route_2['gps'].values.tolist()) - - # Get the trip time for each route - trip_hrs_1 = get_trip_time(route_1_str, route_1_stops, centroid_1, end) - trip_hrs_2 = get_trip_time(route_2_str, route_2_stops, centroid_2, end) - - if minimize: - # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference - if abs(trip_hrs_1 - trip_hrs_2) > time_diff: - route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(), - route_2['gps'].values.tolist(), - centroid_1, centroid_2, end, time_diff, - n=n) - else: - route_1_coordinates = route_1['gps'].values.tolist() - route_2_coordinates = route_2['gps'].values.tolist() - else: - route_1_coordinates = route_1['gps'].values.tolist() - route_2_coordinates = route_2['gps'].values.tolist() + + route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(), + route_2['gps'].values.tolist(), + centroid_1, centroid_2, end, time_diff, n) + + # Remove waypoints from the longest route until the trip time is less than the max time + route_1_coordinates = __remove_longest_waypoints__(route_1_coordinates, centroid_1, end, max_time) + route_2_coordinates = __remove_longest_waypoints__(route_2_coordinates, centroid_2, end, max_time) # Edit the dataframe to reflect the new coordinate clusters df.loc[df['gps'].astype(str).isin(map(str, route_1_coordinates)), 'cluster'] = 0 @@ -57,52 +36,40 @@ def cluster_and_minimize_2(df, centroids, norm_centroids, end, time_diff, minimi def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start, end, time_diff, n): """ - Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a time difference that is less than the time difference + Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a + time difference that is less than the time difference """ - # Find the difference in time between the two routes - route_1_time = get_trip_time(list_to_string(route_1_coordinates), - len(route_1_coordinates), route_1_start, end) - route_2_time = get_trip_time(list_to_string(route_2_coordinates), - len(route_2_coordinates), route_2_start, end) - route_time_diff = abs(route_1_time - route_2_time) - - # If the difference in time is greater than the time difference, move the closest coordinate from the longer route to the shorter route - if route_time_diff > time_diff: - # Find which route is longer - if route_1_time > route_2_time: - longer_route = route_1_coordinates - shorter_route = route_2_coordinates - - for i in range(n): - # Move the closest coordinate from the longer route to the shorter route - closest_coordinate = move_coordinate(longer_route, shorter_route) - longer_route.remove(closest_coordinate) - shorter_route.append(closest_coordinate) - - # Recursively call the function - return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, end, - time_diff, n) - - else: - longer_route = route_2_coordinates - shorter_route = route_1_coordinates - - for i in range(n): - # Move the closest coordinate from the longer route to the shorter route - closest_coordinate = move_coordinate(longer_route, shorter_route) - longer_route.remove(closest_coordinate) - shorter_route.append(closest_coordinate) - - # Recursively call the function - return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, end, - time_diff, n) - - # If the difference in time is less than the time difference, return the routes - return route_1_coordinates, route_2_coordinates + # Find the trip time for each route + route_1_time = get_trip_time(list_to_string(route_1_coordinates), len(route_1_coordinates), route_1_start, end) + route_2_time = get_trip_time(list_to_string(route_2_coordinates), len(route_2_coordinates), route_2_start, end) + + # Find the average trip time + average_time = (route_1_time + route_2_time) / 2 + + # Define a list of all times and route coordinates + times = [route_1_time, route_2_time] + routes = [route_1_coordinates, route_2_coordinates] + + # Sort the routes by time + sorted_indices = np.argsort(times) + + # If the difference of the longest trip time from average is greater than the time difference + if times[sorted_indices[1]] - average_time > time_diff: + # Move the closest coordinate(s) from the longest route to the shortest route + for i in range(n): + closest_coordinate = __move_coordinate__(routes[sorted_indices[1]], routes[sorted_indices[0]]) + routes[sorted_indices[1]].remove(closest_coordinate) + routes[sorted_indices[0]].append(closest_coordinate) + + # Recursively call the function + return minimize_route_time_diff(routes[0], routes[1], route_1_start, route_2_start, end, time_diff, n) + + # If the difference of the longest trip time from average is less than the time difference, return the routes + return routes[0], routes[1] # Create a function to minimize the time difference between three routes -def cluster_and_minimize_3(df, centroids, norm_centroids, end, time_diff, minimize=True, n=2): +def cluster_and_minimize_3(df, centroids, norm_centroids, end, time_diff, max_time=24, n=2): # Cluster the coordinates kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) @@ -119,46 +86,18 @@ def cluster_and_minimize_3(df, centroids, norm_centroids, end, time_diff, minimi # Return the list of locations in each cluster route_1 = df[df['cluster'] == 0] - route_1_stops = len(route_1['gps'].values.tolist()) - route_1_str = list_to_string(route_1['gps'].values.tolist()) - route_2 = df[df['cluster'] == 1] - route_2_stops = len(route_2['gps'].values.tolist()) - route_2_str = list_to_string(route_2['gps'].values.tolist()) - route_3 = df[df['cluster'] == 2] - route_3_stops = len(route_3['gps'].values.tolist()) - route_3_str = list_to_string(route_3['gps'].values.tolist()) - - # Get the trip time for each route - trip_hrs_1 = get_trip_time(route_1_str, route_1_stops, centroid_1, end) - trip_hrs_2 = get_trip_time(route_2_str, route_2_stops, centroid_2, end) - trip_hrs_3 = get_trip_time(route_3_str, route_3_stops, centroid_3, end) - average_time = (trip_hrs_1 + trip_hrs_2 + trip_hrs_3) / 3 + # Minimize the time difference between the routes + route_1_coordinates, route_2_coordinates, route_3_coordinates = minimize_route_time_diff_3( + route_1['gps'].values.tolist(), route_2['gps'].values.tolist(), route_3['gps'].values.tolist(), + centroid_1, centroid_2, centroid_3, end, time_diff, n) - times = [trip_hrs_1, trip_hrs_2, trip_hrs_3] - routes = [route_1_str, route_2_str, route_3_str] - - sorted_indices = np.argsort(times) - - if minimize: - # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference - if times[sorted_indices[2]] - average_time > time_diff: - route_1_coordinates, route_2_coordinates, route_3_coordinates = minimize_route_time_diff_3( - route_1['gps'].values.tolist(), - route_2['gps'].values.tolist(), - route_3['gps'].values.tolist(), - centroid_1, centroid_2, centroid_3, end, time_diff, - n=n) - else: - route_1_coordinates = route_1['gps'].values.tolist() - route_2_coordinates = route_2['gps'].values.tolist() - route_3_coordinates = route_3['gps'].values.tolist() - else: - route_1_coordinates = route_1['gps'].values.tolist() - route_2_coordinates = route_2['gps'].values.tolist() - route_3_coordinates = route_3['gps'].values.tolist() + # Remove waypoints from the longest route until the trip time is less than the max time + route_1_coordinates = __remove_longest_waypoints__(route_1_coordinates, centroid_1, end, max_time) + route_2_coordinates = __remove_longest_waypoints__(route_2_coordinates, centroid_2, end, max_time) + route_3_coordinates = __remove_longest_waypoints__(route_3_coordinates, centroid_3, end, max_time) # Edit the dataframe to reflect the new coordinate clusters df.loc[df['gps'].astype(str).isin(map(str, route_1_coordinates)), 'cluster'] = 0 @@ -192,7 +131,7 @@ def minimize_route_time_diff_3(route_1_coordinates, route_2_coordinates, route_3 if times[sorted_indices[2]] - average_time > time_diff: # Move the closest coordinate(s) from the longest route to the shortest route for i in range(n): - closest_coordinate = move_coordinate(routes[sorted_indices[2]], routes[sorted_indices[0]]) + closest_coordinate = __move_coordinate__(routes[sorted_indices[2]], routes[sorted_indices[0]]) routes[sorted_indices[2]].remove(closest_coordinate) routes[sorted_indices[0]].append(closest_coordinate) @@ -204,6 +143,25 @@ def minimize_route_time_diff_3(route_1_coordinates, route_2_coordinates, route_3 return routes[0], routes[1], routes[2] +def __remove_longest_waypoints__(route_coordinates, start, end, max_time): + """ + Takes a list of lists of coordinates and returns a list of lists of coordinates that is the same length as the + original list but has a trip time less than the max time + """ + # Find the trip time for the route + route_time = get_trip_time(list_to_string(route_coordinates), len(route_coordinates), start, end) + + # 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: + route_mean = __mean_center__(route_coordinates) + furthest_coordinate = __find_farthest_coordinate__(route_coordinates, route_mean) + route_coordinates.remove(furthest_coordinate) + + return __remove_longest_waypoints__(route_coordinates, start, end, max_time) + + return route_coordinates + + def list_to_string(list_of_lists): """ Takes a list of lists of coordinates and returns a string of the coordinates @@ -288,23 +246,53 @@ def __min_max_normalize__(value, min_value, max_value): # Given two clusters and their respective lists of coordinates, move one coordinate from the larger centroid to the smaller centroid -def move_coordinate(larger_centroid_coordinates, smaller_centroid_coordinates): +def __move_coordinate__(larger_centroid_coordinates, smaller_centroid_coordinates): # Calculate the centroid of the smaller cluster - smaller_centroid = [sum([i[0] for i in smaller_centroid_coordinates]) / len(smaller_centroid_coordinates), - sum([i[1] for i in smaller_centroid_coordinates]) / len(smaller_centroid_coordinates)] + smaller_centroid = __mean_center__(smaller_centroid_coordinates) + + # Find the coordinate in the larger cluster that is closest to the centroid of the smaller cluster + closest_coordinate = __find_closest_coordinate__(larger_centroid_coordinates, smaller_centroid) + + return closest_coordinate + - # Find the coordinate in larger_centroid_coordinates that is closest to smaller_centroid - closest_coordinate = larger_centroid_coordinates[0] - closest_coordinate_distance = __distance__(closest_coordinate, smaller_centroid) +def __find_closest_coordinate__(coordinates, centroid): + """ + Takes a list of coordinates and a centroid and returns the coordinate in the list that is closest to the centroid + """ + closest_coordinate = coordinates[0] + closest_coordinate_distance = __distance__(closest_coordinate, centroid) - for coordinate in larger_centroid_coordinates: - if __distance__(coordinate, smaller_centroid) < closest_coordinate_distance: + for coordinate in coordinates: + if __distance__(coordinate, centroid) < closest_coordinate_distance: closest_coordinate = coordinate - closest_coordinate_distance = __distance__(coordinate, smaller_centroid) + closest_coordinate_distance = __distance__(coordinate, centroid) return closest_coordinate +def __find_farthest_coordinate__(coordinates, centroid): + """ + Takes a list of coordinates and a centroid and returns the coordinate in the list that is furthest from the centroid + """ + farthest_coordinate = coordinates[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) + + return farthest_coordinate + + +def __mean_center__(coordinates): + """ + Takes a list of coordinates and returns the mean center of the coordinates + """ + return [sum([i[0] for i in coordinates]) / len(coordinates), sum([i[1] for i in coordinates]) / len(coordinates)] + + def __distance__(coordinate1, coordinate2): """ Takes two coordinates and returns the distance between them -- cgit v1.2.3