A segment is a named stretch of road or trail. Every time you ride or run through it, you want to know your time and effort on that segment. The technical problem: no two GPS traces through the same location are identical. Your line varies, the device sampling rate varies, the GPS noise floor varies. Matching a new activity against a segment reference line requires an algorithm that tolerates this variation without requiring exact point correspondence.

Why bounding box isn't enough

The naive approach: if an activity's bounding box overlaps a segment's bounding box, check for a match. This is too coarse. A long ride through a city will have a bounding box that overlaps dozens of segments that the rider never actually traversed. You need to check whether the activity actually follows the segment's path, not just passes through its vicinity.

A slightly better naive approach: snap each activity trackpoint to the nearest segment point and flag a match if enough points are within a threshold distance. This fails on segments with repeated lat/lng patterns (e.g., a figure-eight loop) and produces false matches when two roads run parallel within the threshold.

Dynamic Time Warping basics

Dynamic Time Warping (DTW) is an algorithm for measuring the similarity between two time series that may vary in speed or timing. Originally developed for speech recognition, it works by finding the minimum-cost alignment between the two sequences, allowing one sequence to be "stretched" or "compressed" in time relative to the other.

For GPS segment matching, the "time series" are sequences of lat/lng coordinates. The "cost" of aligning two points is their Haversine distance. DTW finds the alignment that minimizes total cost.

The key property: DTW handles the case where an activity has more sample points than the segment reference (because the athlete rode slowly and the device sampled more densely) or fewer sample points (because the device had a low sampling rate). A Euclidean distance measure would fail in both cases. DTW doesn't care — it stretches the shorter sequence to match the longer one optimally.

The implementation

The DTW matrix is computed using dynamic programming. Given two sequences A (length n) and B (length m): 

function dtw(a: [number, number][], b: [number, number][]): number {
  const n = a.length;
  const m = b.length;
  const cost = Array.from({ length: n }, () => new Float64Array(m).fill(Infinity));

  cost[0][0] = haversine(a[0], b[0]);

  for (let i = 1; i < n; i++) {
    cost[i][0] = cost[i - 1][0] + haversine(a[i], b[0]);
  }
  for (let j = 1; j < m; j++) {
    cost[0][j] = cost[0][j - 1] + haversine(a[0], b[j]);
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      const d = haversine(a[i], b[j]);
      cost[i][j] = d + Math.min(cost[i - 1][j], cost[i][j - 1], cost[i - 1][j - 1]);
    }
  }

  return cost[n - 1][m - 1];
}

The returned value is the total alignment cost. Normalize by the length of the warping path to get a per-point average distance. Activities where this average exceeds a threshold (default: 25 meters) are not considered matches.

Bounding box prefilter

Running DTW against every segment in the database for every activity is prohibitively expensive. The prefilter step uses a spatial index: expand each segment's bounding box by 100 meters in each direction, and only run DTW against segments whose expanded bounding box contains at least one activity trackpoint.

In D1, the prefilter is a simple range query on stored bbox_min_lat, bbox_max_lat, bbox_min_lng, bbox_max_lng columns. This reduces the candidate set from thousands of segments to tens per activity — then DTW runs only on the candidates.

Effort extraction

Once DTW confirms a match, the algorithm backtracks through the cost matrix to find the warping path — the sequence of (i, j) index pairs that defines the optimal alignment. The activity trackpoints corresponding to the first and last points of the warping path give the start and end indices in the activity's sample array.

From those indices, extract the sub-array of samples that covers the segment. Compute:

  • Elapsed time: samples[end].t - samples[start].t in seconds
  • Average power / HR / pace over the extracted sub-array
  • Normalized Power if watts are available at 1Hz
  • Best effort flag: compare against all previous efforts on this segment for this athlete

The segment effort is written to the segment_efforts table with the activity ID, segment ID, elapsed seconds, and the extracted metrics. The UI shows the effort on both the activity detail page and the segment leaderboard.

Windowed DTW for long activities

Standard DTW on a 3-hour ride (roughly 10,800 GPS points at 1Hz) against a 5-minute segment (300 reference points) would build a 10,800 × 300 matrix. That's 3.24M cells — fine for a single comparison, but repeated across all candidate segments it adds up.

The optimization: instead of running DTW on the full activity against the segment, use the bounding box overlap to find the approximate location in the activity where the segment occurs, then extract a window of ±2 minutes around that region. DTW runs on the window (roughly 240 points) against the segment reference. The window approach reduces the matrix to ~72k cells — 45× smaller — at negligible accuracy cost.