polyline checkpoint enhancement for GPS timing during Low-Key Hillclimbs

As I initially described here, I have been developing an event model for GPS data for the Low-Key Hillclimbs. This allow us to do things which weren't possible before:

1. dirt climbs: 2012 and 2013, where it's better to let riders do it on their own
2. short-hills routes, where there's too many time points for practical hand-timing
3. bonus climbs, supplementing the standard "event", in which riders get a chance to experience more challenges

A limitation of the model has been checkpoints are defined as fixed line segments. This provides a much better solution to event applications than does the Strava timing algorithm, which is optimized for users who within a few seconds define an arbitrary, abstract "segment" and the code is left to match rider data to the segment without much additional information. My model is set up for a course designer who is willing to carefully optimize the placement of a series of checkpoints, to improve timing accuracy and to reduce sensitivity to GPS errors and rider navigational choices consistent with the course goals. Strava's present algorithm will never serve the need of event organizers who want to verify course completions, potentially with time limits, and optionally timing riders over various portions: in events, there's simply too little margin for error. However, the simple model of a checkpoint as a single line segment can be limiting.

Checkpoints can serve two purposes:

1. to provide optional split times
2. to verify completion of a course, for example that the rider didn't take a short-cut

For split times, it makes sense to optimize the line strictly for the purposes of timing. If GPS data is flaky, and position errors are large, or GPS drops out during the ride, you don't want to assign split times to that rider associated with that checkpoint. But if the split times are just supplementary to the overall time, that's fine.

Additionally, for timing, you probably want the line to cross the road at a perpendicular angle. This way if the rider is to the left or right, the rider gains no advantage or disadvantage on splits associated with that line. This is basic stuff in start-finish line placement.

But if the point is just to verify the rider passed, there's no reason to worry about such things. The line can have generous width, angled to best avoid the roads presenting potential short-cuts. But with course verification, GPS data drops may still be an issue. And a single straight line may not be the best shape to catch the rider moving along the desired path.

To address this I extended the model to include polylines.

In the old code, a checkpoint was characterized by a line, which included a left and right boundary. The line needed to be crossed with the left boundary on the left, the right boundary on the right. It was encoded as a center point and a right point, with the left point a reflection of the right through the center. There was also an optional distance parameter, to allow tuning of the distance between the center point and the left and right boundaries, retaining the distance. This was implemented to facilitate extending the line if in practice GPS errors turned out to be larger than expected.

With polylines, checkpoints are instead represented by a list of such lines. In every preceding case, the list was length one. But the list could be arbitrary length. The code then goes through the list and checks in order if any of the lines is crossed, again with its right boundary on the right and left boundary on the left. If any is crossed by the path between two points in the user trajectory, the checkpoint is considered triggered

Polylines represent a surprisingly broad range of applications. The one which inspired their implementation is a series of sequential checkpoints along an unambiguous section of the route the rider must traverse. It's not important which of the checkpoints is crossed as long as at least one of the checkpoints is crossed. If GPS signal integrity is unreliable, and the signal might drop or large position errors might occur, this application can be used to verify course completion. Obviously this wouldn't be best for timing, since the time could be taken to any of a series of checkpoints which lie at different distances. If the user went through more than one of these sequential checkpoints, going through following lines would simply retrigger the same checkpoint. This would have relevance only if there was a time budget to either the next or the prior checkpoint.

But there's other possibilities. Another would be a checkpoint which consists of what is effectively a curved line. Segments could be connected, the left boundary of one matching the right boundary of the next. While the data representation I'm using doesn't easily facilitate this, it would be a simple enhancement to support it so in the course definition phase only the series of vertex points would need to be specified.

An application of this would be a course where the goal was to hit a landmark, from any direction, then move to an additional landmark. I could construct a polygon around the landmark consisting of three more more sides. The user would need to enter, or optionally leave this region to trigger the checkpoint. If the points were arranged clockwise looking down, each segment ordered left then right, the checkpoint would be triggered upon leaving, while if they were arranged counterclockwise, the checkpoint would be triggered upon entering.

Another would be a checkpoint where I wanted to avoid potential alternate paths, and space was tight. Consider roads A, B, and C. I want to make sure the rider is on road B which is between A and C. However, from a desired checkpoint the direction of minimum distance to A is in a different direction than the direction of minimum distance to C. I might put a two-part polyline, from between A and B, to the point on B, to between B and C. Or I could make it a 3-part line with a short segment perpendicular to road B. The idea is to shape the net to catch the rider to maximize the chance of catching the rider without catching riders on alternate paths.

Another application is a bidirectional checkpoint. Imagine a course with an out-and-back, where the rider must circle a loop at the turnaround. Perhaps I don't care if the loop is made with a left turn or right turn. I could put a 2-segment checkpoint at he apex of the loop, one for clockwise riders, the other, identical except the left and right boundaries are swapped, for counterclockwise riders.

Another application might be routes with time limits (time budgets) for road segments where the rider might spend time at a rest stop. Suppose I have a route from A to B to C, and there is a 1 hour limit from A to B, and another 1-hour limit from B to C. A rider spends 10 minutes at checkpoint B. If the rider were to take 45 minutes to go from A to B, then spend 10 minutes at B, then 55 minutes from B to C, then the rider would rather have the resting time at B assigned to the A-B portion. That would provide for 55 minutes against a 1-hour budget for both A-B and B-C. On the other hand, if the resting time were credited to the B-C portion, that would result in 45 and 65 minutes, the 65 minutes going over the 60 minute time budget, and there would be a 5-minute penalty against overall time. To do this, I would put in a polyline segment, one before the rest stop, the other after. Then riders would trigger it twice, and the code would pick the one which resulted in a minimum net time for the rider, as I described in my blog post on recursive course time determination.

So this extension of the model, from checkpoints consisting of a single line segment with left and right boundaries, to multiple line segments each with its own left and right boundary where the rider triggers the checkpoint by crossing any of them, has considerable power, especially when used in conjunction with the flexible, recursive course timing algorithm I described previously.

It's still somewhat limited, however. I require checkpoints themselves to be crossed in order. I still have no way to say "checkpoints A and B must each be crossed but in either order". For example, it's popular in alleycat races to have riders need to visit a series of landmarks but optimizing the order is part of the competition. While the code could trivially be modified to support this, combining this functionality with the existing one in an elegant fashion would be additional work. A slight generalization of this idea would be "N checkpoints, of which M must be crossed, where 0 < M ≤ N". For example, I might want to define a series of checkpoints along a route with unreliable GPS, but make sure the rider hit at least half of them. This comes closer to the Strava path matching algorithm.

Okay, I'd better stop now, otherwise I'm going to want to overhaul my code again, and it's already working in advance of tomorrow's bonus route of Lomas Cantadas and Marin Ave in the Berkeley Hills. I'm excited to see how it goes.