Matching road trips that share a road, in PostGIS

Musafir is a travel app about the road rather than the destination. One idea underneath it: routes overlap. A search from Nagpur to Delhi shares road with the popular Delhi to Chandigarh corridor, so what one traveller discovers on that stretch should reach the next person who drives it.

That needs an answer to a question that sounds simple: are these two routes on the same road here? Routes from a routing engine never share exact coordinates. They are sampled differently, offset by a few metres, and split at different points.

A working definition of "the same road"

The implementation compares short pieces instead of whole routes:

The core of the function

It is a PL/pgSQL function, search_route, that stores the route and then walks it piece by piece. This is the loop from the current version:

for i in 0..n_chunks - 1 loop
  chunk_geom := st_linesubstring(route_geom, i::numeric / n_chunks, (i + 1)::numeric / n_chunks);
  chunk_geog := chunk_geom::geography;
  p_start := st_startpoint(chunk_geom);
  p_end := st_endpoint(chunk_geom);
  calc_bearing := round(degrees(st_azimuth(p_start, p_end)))::int % 360;
  seg_id := null;

  select rs.id into seg_id
  from public.route_segments rs
  where st_dwithin(chunk_geog, rs.polyline, radius_m * 4) -- cheap prefilter
    and (
      rs.bearing_deg is null or
      abs(rs.bearing_deg - calc_bearing) <= 45 or
      abs(abs(rs.bearing_deg - calc_bearing) - 180) <= 45 or
      abs(rs.bearing_deg - calc_bearing) >= 315
    )
    and (
      select count(*) filter (
        where st_dwithin(st_lineinterpolatepoint(chunk_geom, p / 4.0)::geography, rs.polyline, radius_m)
      )
      from generate_series(0, 4) as p
    )::numeric / 5 >= overlap_threshold
  order by st_distance(chunk_geog, rs.polyline)
  limit 1;

  if seg_id is not null then
    matched_count := matched_count + 1;
    insert into public.poi_route (poi_id, route_id, segment_id, is_on_route)
    select pr.poi_id, new_route_id, pr.segment_id, true
    from public.poi_route pr
    where pr.segment_id = seg_id
    on conflict do nothing;
  else
    insert into public.route_segments (route_id, segment_index, polyline, start_coord, end_coord, distance_km, bearing_deg)
    values (
      new_route_id, i, chunk_geog,
      p_start::geography,
      p_end::geography,
      st_length(chunk_geog) / 1000,
      calc_bearing
    );
  end if;
end loop;

The defaults are chunk_m = 500, radius_m = 50 and overlap_threshold = 0.8, and the number of pieces is greatest(1, ceil(total_len / chunk_m)), so even a very short route gets one piece.

The PostGIS calls, one at a time

Why geometry and geography both appear

PostGIS has two types for shapes. geography measures on the spheroid, so distances come out in metres, which is what "within 50 m" needs. st_linesubstring and st_lineinterpolatepoint work on geometry. So the function keeps both: geometry to cut and sample, geography to measure.

One consequence worth knowing: substring fractions are taken on the geometry's length in degrees, so pieces are only roughly 500 m, not exactly.

Why the heading check exists

Distance alone gets crossings wrong. Where two roads cross, pieces of each are within 50 m of each other for a moment, but they are not the same road. Comparing headings keeps a crossing from counting. The check accepts the opposite direction too, so both directions of a road match, and older pieces saved before headings were stored (bearing_deg is null) stay matchable.

Edge cases, honestly

• Each piece is compared with one saved piece at a time. A new piece straddling the boundary of two old pieces may reach 4 of 5 on neither.
• The samples include both endpoints, so piece boundaries that are offset from old boundaries can cost a hit.
• A matched piece is not stored as part of the new route. Only unmatched pieces are saved, so a route's saved pieces have gaps where it overlapped.
• on conflict do nothing on the inherited links does not actually de-duplicate anything yet: that table has no unique constraint beyond its id.

What it costs

The function carries its own note: it loops once per 500 m piece, O(route length), fine at early traffic, with a set-based rewrite as the fix once long routes feel slow. Each iteration is one index-assisted candidate lookup on the GiST index, up to five point checks per candidate, and an insert. A 1,000 km route is about 2,000 iterations. That is arithmetic from the defaults, not a measurement.