Route Progress Algorithm

Updated: As of 12/2/2022

This is incomplete, but it’s the basic framework for determining a bus’s progress along a route. The calculation is performed with the assumption that the bus is near a valid route at all times:

1. Find the route closest to the bus

1. Iterate over all routes from route_1, route_2, ... route_n. (As of 12/6/2022 there are only two routes: West Route, North Route).
2. Use Turf.js, LineString, to find the closest coordinate along route_m. Note that this closest coordinate may not be a rtept along the route, but instead a coordinate along the LineString from each rtept to the next rtept along route_m.
   • For example in Public > routes-data > fall22.gpx we have:

          <name>West Route</name>
          <cmt>Blue</cmt>
          <rtept lat="42.730777" lon="-73.677212"></rtept>
          <rtept lat="42.727822" lon="-73.678042"></rtept>
          ...

Here is how to interpret the data shown above:

• There exists a route called "West Route"
• one rtept along the route, "West Route", is a rtept with latitude="42.730777" and longitude="-73.677212" which we may refer to as "vertex" in the code.
• a closest coordinate along the LineString may be ("latitude": 42.73136133333333), "longitude": -73.66852533333333). Note that this is NOT a rtept shown in the data above and is furthermore not a rtept that exists at all in the data above if we were to expand the data to show all the rtepts along "West Route".
• the closest coordinate exists in the set of coordinates from one rtept, to another rtept lying along the LineString which is made up of the , <rtept lat="42.727822" lon="-73.678042>, etc...

For illustration purposes only, here is a diagram which outlines some of these key points:

3. Check if the distance between the current bus location to the closest coordinate is within Constants.isOnRouteThreshold
   • true -> return true (implying that the current bus location is on route_m)
   • false -> return false (implying that the current bus location is not on route_m)
4. If (3)
   • true -> has the route segment closest to the bus been set yet? - true -> the bus is on an overlapping route -> return the first route segment - false -> set current route segment to the current route
   • false -> continue to check the next route
   • Note that there might be the same distance to the bus location in the case of overlapping routes. In such an edge case we will return the first route segment.

2. Find the distance along the current route that the bus has traveled from the first rtept to the current bus location

1. Determine the nearest "vertex" to the current bus location. For convenience let us call it 'b'
2. Continuously sum the polyline distances from one rtpet to the next until we reach 'b'
3. At rtept_v consider 3 possibles cases in order to get the accurate distance travled
   • 3 Cases:

// If the current rtept is the nearest rtept, determine if the reported bus location is to the left or right of the nearest rtept
// (i.e. Assume we have the following polyline)
//
// |-----|-----| --> |--x1--|--x2--| --> This algorithm determines whether the current bus location, 'x' is either 'x1' or 'x2' relative to the nearest rtept, 'b'
// a     b     c     a      b      c
//
// For brevity assume the following in all polyline cases:
//    Let 'x' be either 'x1' or 'x2' which is determined by the case analysis
//    Let 'a' be the rtept before the nearest rtept in the entire route
//    Let 'b' be the nearest rtept in the entire route
//    Let 'c' be the rtept after the nearest rtept in the entire route
//
// This step is needed in order to determine whether the distance the bus has traveled includes 'a' to 'x1' or instead 'b' to 'x2'
//
// There are 3 cases: 1) distance(a,b) == distance(b,c)
//                    2) distance(a,b) < distance(b,c)
//                    3) distance(a,b) > distance(b,c) 

Case 1)

// Assume the following polyline (for case 1):
// Goal: Determine if x=x1 or if x=x2
//
// |--x1--|--x2--| 
// a      b      c
//
// if distance(a,x) < distance(x,c) then x = x1 which implies the bus has just passed rtept 'a' and that we must sum the remaining distance from 'a' to x==x1
// Otherwise x == x2 which implies the bus has just passed rtept 'b' and that we must sum the remaining distance from 'b' to x==x2

Case 2)

// Assume the following polyline (for case 2):
// Goal: Determine if x=x1 or if x=x2
//
// |--x1--|--x2-------| 
// a      b           c
//
// Suppose we have delta1 < delta2. By direct proof the following is true (for brevity assume distance(...) == d(...)):
// delta1 = d(b,c) - d(a,x)
// delta2 = d(b,c) - d(a,b)
// delta1 < delta2 --> d(b,c) - d(a,x) < d(b,c) - d(a,b) --> -d(a,x) < -d(a,b) --> d(a,x) > d(a,b)
// if delta1 < delta2 then d(a,x) > d(a,b) then x = x2 which implies the bus has just passed rtept 'b' and that we must sum the remaining distance from 'b' to x==x2
// Otherwise x == x1 which implies the bus has just passed rtept 'a' and that we must sum the remaining distance from 'a' to x==x1

Case 3)

// Assume the following polyline (for case 3):
// Goal: Determine if x=x1 or if x=x2
//
// |-------x1--|--x2--| 
// a           b      c
//
// Suppose we have delta1 < delta2. By direct proof the following is true (for brevity assume distance(...) == d(...)):
// delta1 = d(a,b) - d(c,x)
// delta2 = d(a,b) - d(b,c)
// delta1 < delta2 --> d(a,b) - d(c,x) < d(a,b) - d(b,c) --> -d(c,x) < -d(b,c) --> d(c,x) > d(b,c)
// if delta1 < delta2 then d(c,x) > d(b,c) then x = x1 which implies the bus has just passed rtept 'a' and that we must sum the remaining distance from 'a' to x==x1
// Otherwise x == x2 which implies the bus has just passed rtept 'b' and that we must sum the remaining distance from 'b' to x==x2