Skip to content

GTFS Shape Matching & Polyline Clipping

Selects the correct travel direction from a GTFS route's multiple direction variants, then clips the full route shape to only the segment the passenger will actually ride — from their boarding stop to their alighting stop.

Where It Is Used

apps/passengers-app/src/app/pages/gtfs-route-detail/gtfs-route-detail.page.ts

Applied when a passenger selects a GTFS route (Cochabamba public transit) to view their specific trip segment on the map.

The Problem

A single GTFS route typically has 2+ direction variants (outbound / inbound / circular), each with a full polyline covering the entire route. The passenger only travels a portion of one direction. Displaying the wrong direction or the full polyline creates a confusing and cluttered map.

Algorithm

Phase 1: Direction Selection

For each direction variant of the GTFS route:

  1. Find the polyline point closest to the boarding stop: $$i_{\text{board}} = \arg\min_{i} \text{Haversine}(pts[i], \text{boardStop})$$

  2. Find the polyline point closest to the alighting stop, constrained to come after $i_{\text{board}}$ (enforces forward travel): $$i_{\text{alight}} = \arg\min_{i > i_{\text{board}}} \text{Haversine}(pts[i], \text{alightStop})$$

  3. Score the direction: $\text{score} = d_{\text{board}} + d_{\text{alight}}$ (sum of the two closest distances).

Select the direction with the lowest score.

let bestDir = null, bestScore = Infinity;
for (const dir of directions) {
  const pts = dir.polyline;
  let boardMin = Infinity, boardIdx = 0;
  for (let i = 0; i < pts.length; i++) {
    const d = haversine(pts[i], boardStop);
    if (d < boardMin) { boardMin = d; boardIdx = i; }
  }
  let alightMin = Infinity, alightIdx = boardIdx;
  for (let i = boardIdx; i < pts.length; i++) {
    const d = haversine(pts[i], alightStop);
    if (d < alightMin) { alightMin = d; alightIdx = i; }
  }
  const score = boardMin + alightMin;
  if (score < bestScore) { bestScore = score; bestDir = { dir, boardIdx, alightIdx }; }
}

Phase 2: Polyline Clipping

Extract the slice of the selected direction's polyline between the two matched indices:

const { dir, boardIdx, alightIdx } = bestDir;
const clipped = dir.polyline.slice(
  Math.min(boardIdx, alightIdx),
  Math.max(boardIdx, alightIdx) + 1
);

Math.min/max handles edge cases where the route is circular and the indices may appear reversed.

syncc Route Equivalent

For syncc-registered routes (non-GTFS), the same polyline clipping is performed in route-detail.page.ts:

  1. Decode Line.polyline → allPts[]
  2. Find nearest index to boarding stop: brute-force Haversine scan
  3. Find nearest index to alighting stop: separate brute-force scan
  4. Clip: allPts.slice(pStart, pEnd + 1)