Skip to content

GTFS Stop Search

Three complementary search functions over the in-memory GTFS stop index for the Cochabamba public transit network. Used in the passenger app for stop autocomplete, map clustering, and route discovery.

Where It Is Used

apps/api-server/src/passenger/gtfs.service.ts

All three functions operate on the GTFS index built at server startup — see GTFS Index Building.

1. Fuzzy / Accent-Tolerant Text Search

Endpoint: GET /passenger/gtfs/stops/search?q=<query>

Used for the passenger autocomplete field when typing a stop name.

Algorithm

  1. Normalize the query string: typescript const normalize = (s: string) => s.toLowerCase().normalize('NFD').replace(/[̀-ͯ]/g, ''); This converts "Oquendo" and "oquendo" to the same string, and strips Spanish diacritics (á → a, é → e, ñ → n, etc.).

  2. Filter the stop index to entries where normalize(stop.name).includes(normalize(query)).

  3. Sort by route count descending — busier intersections (served by more routes) appear first, since passengers are more likely searching for major stops.

  4. Return the first 8 results.

Example

Query "avenida" matches "Avenida Oquendo", "Avenida Blanco Galindo", "Avenida América", etc., regardless of accent marks.

2. Nearest-N Stops (No Radius Cutoff)

Endpoint: GET /passenger/gtfs/stops/nearby?lat=&lng=&n=25

Returns the N closest stops with no distance cutoff. Guarantees results even when the user is far from any stop (e.g., in a low-coverage area).

Algorithm

function nearestN(lat: number, lng: number, n: number): GtfsStop[] {
  return stops
    .map(s => ({ ...s, dist: haversine(lat, lng, s.lat, s.lng) }))
    .sort((a, b) => a.dist - b.dist)
    .slice(0, n);
}

Default N = 25. Complexity: $O(n \log n)$ dominated by the sort.

3. Stops Within Radius

Endpoint: GET /passenger/gtfs/stops/within?lat=&lng=&radius=700

Returns all stops within a given radius, sorted by distance and capped at 30 results.

Algorithm

function withinRadius(lat: number, lng: number, radius: number): GtfsStop[] {
  return stops
    .filter(s => haversine(lat, lng, s.lat, s.lng) <= radius)
    .sort((a, b) => a.dist - b.dist)
    .slice(0, 30);
}

Default radius = 700 m (~10-minute walk at 80 m/min pedestrian pace).

Normalization Function Detail

const normalize = (s: string) =>
  s
    .toLowerCase()
    .normalize('NFD')                        // decompose accented characters
    .replace(/[̀-ͯ]/g, '');        // strip combining diacritical marks

Unicode range U+0300–U+036F covers all combining diacritical marks used in Spanish and other Latin scripts.