Skip to content

Geodesic Line-Segment Projection Snapping

This document provides a detailed overview of the geodesic line-segment projection snapping algorithm implemented in syncc. It explains why the previous vertex-only proximity checks failed on long straight avenues, the mathematical details of the projection vector calculations, and how this achieves gap-free transit-to-walk map alignments.

1. The Proximity Snapping Problem

Bolivian public transit (trufis/micros) allows passengers to hail and get off the bus anywhere along a route, not just at designated stops. Therefore, when routing a passenger: 1. They walk from their origin to some optimal boarding point on the bus route. 2. They ride the bus along the route segment. 3. They get off the bus at an optimal alighting point and walk to their destination.

To calculate these routes, the backend maps the origin/destination straight-line (Euclidean) projections onto the bus route shape to find the boarding/alighting coordinates. However, when the frontend requests the actual pedestrian walking legs from the OSRM/Valhalla routing engine, it snaps the start and end coordinates to the nearest walkable street networks (sidewalks/intersections).

This mismatch produces visual gaps and overlaps on the map:

graph TD
    subgraph A [Before: Discrete Proximity Snapping]
        R1[Alight Point on Avenue] -.->|Gap / Walk Backwards| W1[Walkway Corner on Intersection]
    end
    subgraph B [After: Segment Projection Snapping]
        R2[Alight Point Snapped to Corner] ===|Connected| W2[Walkway Starts at Corner]
    end

Why Vertex-Only Checking Fails

To close these gaps, the markers must snap to the walkable paths. However, simply checking the distance between walking path points and the discrete vertices (vertices are coordinates/stops along the bus route) fails on straight roads:

  • Sparse Vertices: In geographic datasets, straight road segments only have points at corners/bends. A straight segment can stretch 200–500 meters without intermediate points.
  • False Deviations: If a passenger walks along the bus route avenue between two checkpoints, the distance from their walking path to the nearest discrete shape vertex might be 50 meters, even though they are exactly on the bus route.
  • Premature Cutoff: A threshold check (e.g., <30m) will falsely assume the pedestrian has left the bus route, snapping the marker at the wrong location (e.g., 80 meters too early).

2. The Solution: Line-Segment Projection

Instead of measuring the distance to the discrete vertices of the bus route, we measure the shortest distance to the continuous line segments connecting those vertices.

For each point $P$ along the walking path, we project it perpendicularly onto each line segment $AB$ of the bus route:

          P (Walking point)
          |
          |  d (Shortest Distance)
          v
  A-------P'-------B  (Bus route segment)

Mathematical Steps

For a walking point $P(x, y)$ and a bus segment defined by endpoints $A(x_1, y_1)$ and $B(x_2, y_2)$:

1. Define Vectors

Represent the segment vector $\vec{AB}$ and the point-to-start vector $\vec{AP}$: $$\vec{AB} = (x_2 - x_1, y_2 - y_1)$$ $$\vec{AP} = (x - x_1, y - y_1)$$

2. Calculate Projection Factor ($t$)

We project $\vec{AP}$ onto $\vec{AB}$ using the dot product, normalized by the squared length of the segment $|\vec{AB}|^2$: $$t = \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} = \frac{(x - x_1)(x_2 - x_1) + (y - y_1)(y_2 - y_1)}{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

The scalar $t$ indicates where the projection lies relative to the segment: * $t < 0$: The projection lies before $A$. * $t > 1$: The projection lies after $B$. * $0 \le t \le 1$: The projection lies directly on the segment $AB$.

3. Clamp the Projection

To ensure we only find points on the actual segment (not the infinite line), we clamp $t$ to the range $[0, 1]$: $$t_{\text{clamped}} = \max(0, \min(1, t))$$

4. Find Projected Point Coordinates ($P'$)

The closest point $P'(x', y')$ on the segment $AB$ is: $$x' = x_1 + t_{\text{clamped}}(x_2 - x_1)$$ $$y' = y_1 + t_{\text{clamped}}(y_2 - y_1)$$

5. Calculate Geodesic Distance

We compute the Haversine distance between $P(x, y)$ and $P'(x', y')$ to get the shortest distance in meters.

3. Intersection Snapping Algorithm

Using the segment-distance calculation, we find the exact points where the walking paths intersect or deviate from the bus route:

1. Boarding Snap (Origin → Bus Route)

We walk along the path walkToBusPts starting from the origin: * We check the distance from each point to the bus segment. * The first point that is within 30 meters of any segment on the bus route is the intersection where the passenger first reaches the route. * We snap the boarding marker (boardPt) to this point and trim the walking leg to terminate there.

2. Alighting Snap (Bus Route → Destination)

We walk along the path walkFromBusPts ending at the destination: * We check the distance from each point to the bus segment. * The last point that is within 30 meters of any segment on the bus route is the intersection where the passenger turns off the avenue. * We snap the alighting marker (alightPt) to this intersection and trim the walking leg to start there.

4. Code Implementation

This is the TypeScript implementation added to gtfs-route-detail.page.ts, route-detail.page.ts, and home.page.ts:

// Geodesic Line-Segment Projection Math
const distanceToLineSegment = (p: L.LatLngTuple, a: L.LatLngTuple, b: L.LatLngTuple): number => {
  const x = p[0], y = p[1];
  const x1 = a[0], y1 = a[1];
  const x2 = b[0], y2 = b[1];

  const A = x - x1;
  const B = y - y1;
  const C = x2 - x1;
  const D = y2 - y1;

  const dot = A * C + B * D;
  const lenSq = C * C + D * D;
  let param = -1;
  if (lenSq !== 0) {
    param = dot / lenSq;
  }

  let xx, yy;
  if (param < 0) {
    xx = x1;
    yy = y1;
  } else if (param > 1) {
    xx = x2;
    yy = y2;
  } else {
    xx = x1 + param * C;
    yy = y1 + param * D;
  }

  return haversineMeters(x, y, xx, yy);
};

// Find the minimum distance from a coordinate to any segment on the route
const distanceToRoute = (p: L.LatLngTuple, route: L.LatLngTuple[]): number => {
  let minDist = Infinity;
  for (let i = 0; i < route.length; i++) {
    // Check vertex distance
    const dVertex = haversineMeters(p[0], p[1], route[i][0], route[i][1]);
    if (dVertex < minDist) minDist = dVertex;

    // Check segment projection distance
    if (i < route.length - 1) {
      const dSeg = distanceToLineSegment(p, route[i], route[i+1]);
      if (dSeg < minDist) minDist = dSeg;
    }
  }
  return minDist;
};