Snapping Bike-Share Stations to OSM Nodes

A GBFS station_information.json feed hands you a bike-share station as a bare lat/lon pair — accurate to the dock, useless to a router until it is wired into a node in the road graph. Snapping is the step that closes that gap: for every station, find the closest node a pedestrian can actually walk to, insert a connector edge, and reject any station whose nearest candidate sits implausibly far away. This page is the concrete implementation referenced from GTFS multi-modal trip-planning automation, which stitches the resulting connector edges into a time-expanded transit graph, and it supports the broader automation goals of Routing API Automation & Fleet Integration — turning fragmented data feeds into a graph a routing engine can actually query.

The naive approach — looping over stations and computing distance to every graph node — does not scale past a few hundred stations against a graph with tens of thousands of nodes. A scipy.spatial.cKDTree built once over projected node coordinates turns that O(stations × nodes) scan into O(stations × log nodes), but only if the tree and the query points share the same planar coordinate reference system. Querying a KD-tree with raw lat/lon degrees silently distorts distance at any latitude away from the equator, which produces optimistic snap distances that pass a threshold check they should have failed.

When to Use This Approach

KD-tree nearest-node snapping is the right tool when station coordinates come from a reasonably trustworthy feed, the routable node density is high enough that straight-line distance closely tracks network-reachable distance, and you need to process thousands of stations against a large graph without paying for a network-distance search on every point.

Use KD-tree Euclidean snapping when:

• Station coordinates come from an operator’s GBFS feed rather than crowd-sourced or manually digitized points
• The graph node density around each station is high enough that straight-line distance closely approximates true walking distance — dense urban cores, not isolated rural docks
• You need to snap thousands of stations against a graph with 100 000+ nodes and cannot afford a network-distance (Dijkstra ball) search per station
• A connector edge of a few tens of meters is an acceptable approximation of real accessibility

Reach for something else when:

• A physical barrier — a river, a fenced rail corridor, a highway median — sits between the station and its geometrically nearest node; a straight-line KD-tree match cannot see the barrier, so a rejected or suspiciously short snap should trigger a network-distance check instead of blind acceptance
• Station density is very low (a handful of docks in a pilot deployment) — a GeoPandas sjoin_nearest call is simpler to reason about and fast enough without building a tree explicitly
• The surrounding OSM extract is sparse or has known fragmentation — validate that candidate nodes belong to the graph’s largest connected component before trusting a snap

Implementation

The function below assumes you already have GTFS-adjacent station records and an OSM node table as GeoDataFrames — station ingestion is covered in integrating GTFS schedules into trip planning and is not repeated here.

# requires: numpy, pandas, geopandas, scipy, pyproj (pip install numpy pandas geopandas scipy pyproj)
# Python 3.9+

from __future__ import annotations

import numpy as np
import geopandas as gpd
from scipy.spatial import cKDTree
from pyproj import CRS, Transformer

MAX_SNAP_DISTANCE_M = 35.0
WALK_SPEED_MPS = 1.35  # conservative pedestrian speed while walking a bike to a dock

# Node classes a bike-share dock can realistically connect through on foot.
WALKABLE_HIGHWAY = {
    "residential", "service", "footway", "path", "pedestrian",
    "living_street", "cycleway", "unclassified", "tertiary",
}


def snap_stations_to_graph(
    stations: gpd.GeoDataFrame,
    graph_nodes: gpd.GeoDataFrame,
) -> gpd.GeoDataFrame:
    """Snap GBFS stations to the nearest routable OSM node.

    `stations` needs a `station_id` column and point geometry in EPSG:4326.
    `graph_nodes` needs `node_id`, `highway_class`, and point geometry in EPSG:4326.
    Returns one row per station with the matched node, snap distance in meters,
    and an `accepted` flag.
    """
    routable = graph_nodes[graph_nodes["highway_class"].isin(WALKABLE_HIGHWAY)].copy()
    if routable.empty:
        raise ValueError("no routable nodes remain after the highway_class filter")

    # Project once into a local UTM zone so Euclidean distance in the KD-tree
    # tracks true ground distance to within centimeters per kilometer.
    utm_crs = CRS(routable.estimate_utm_crs())
    to_utm = Transformer.from_crs("EPSG:4326", utm_crs, always_xy=True).transform

    node_xy = np.column_stack(to_utm(routable.geometry.x.to_numpy(), routable.geometry.y.to_numpy()))
    station_xy = np.column_stack(to_utm(stations.geometry.x.to_numpy(), stations.geometry.y.to_numpy()))

    tree = cKDTree(node_xy)
    distances_m, idx = tree.query(station_xy, k=1, workers=-1)

    matched = routable.iloc[idx].reset_index(drop=True)
    out = stations[["station_id"]].reset_index(drop=True).copy()
    out["node_id"] = matched["node_id"].to_numpy()
    out["snap_distance_m"] = distances_m
    out["accepted"] = out["snap_distance_m"] <= MAX_SNAP_DISTANCE_M
    out["connector_weight_s"] = out["snap_distance_m"] / WALK_SPEED_MPS
    return out


def build_connector_edges(snapped: gpd.GeoDataFrame) -> list[dict]:
    """Bidirectional connector edges for accepted snaps, ready for graph insertion."""
    accepted = snapped[snapped["accepted"]]
    edges: list[dict] = []
    for row in accepted.itertuples(index=False):
        station_node = f"station:{row.station_id}"
        edges.append({"u": station_node, "v": row.node_id, "weight": row.connector_weight_s, "kind": "bikeshare_access"})
        edges.append({"u": row.node_id, "v": station_node, "weight": row.connector_weight_s, "kind": "bikeshare_access"})
    return edges

tree.query(..., workers=-1) parallelizes the nearest-neighbor search across all available cores in a single vectorized call — there is no reason to loop over stations in Python. The station-to-node distance array and the connector-weight array fall out of the same NumPy operation without a second pass over the data.

Key Parameters and Tuning

Projection matters more than tree implementation. Swapping cKDTree for sklearn.neighbors.BallTree with a haversine metric produces comparable correctness, but the UTM-projection step above is what actually determines whether MAX_SNAP_DISTANCE_M means what you think it means. Skipping it is the single most common source of silently wrong accepted/rejected flags.

Integration Points

Accepted connector edges are appended to whichever base graph the rest of the pipeline already builds from OSM — a NetworkX graph for prototyping, or the compiled node/edge arrays feeding OSRM or Valhalla for production queries. Because station nodes are synthetic (station:<id>), they never collide with real OSM node IDs, and downstream code can identify them with a simple string prefix check when rendering multi-modal itineraries.

Feeding trip planning. The connector edges produced here are the walking legs that let a transit-planning graph treat a bike-share dock as a reachable access point rather than an isolated coordinate. Integrating GTFS schedules into trip planning consumes these edges when building the time-expanded graph, attaching each station node alongside transit stop nodes so an earliest-arrival search can route a rider on foot to a dock, by bike to another dock, and on foot again to a transit stop.

Layering onto the base road graph. If your OSM extract already carries a separate multi-modal layer for transit, ferries, or rail, the connector edges belong on the same layer boundary described in implementing multi-modal transit layers — treat a bike-share station like any other mode-transfer point rather than bolting it onto the road layer directly.

Re-running on a schedule. GBFS station_information.json feeds add and retire docks continuously, and OSM extracts change as mappers add footpaths. Key the snap job by station_id and re-run it on every extract refresh rather than caching results indefinitely — a station that was correctly flagged as unreachable six months ago may now have a routable node nearby. If your engine of choice needs the connector edges expressed as a routing profile rather than raw graph edges, the JSON-based tuning pattern in Valhalla configuration for multi-modal analysis shows how access-point costing is typically expressed.

The walkable-class filter is what stops a station from attaching to a road nobody can cross on foot. Without it the nearest node to a kerbside dock is often a carriageway node on a dual carriageway, and the resulting connector implies a pedestrian crossing that does not exist.

Validation Checklist

1. Distance distribution sanity check. Plot a histogram of snap_distance_m for accepted stations. A dense grouping near 0 m with a thin scatter of larger values approaching the threshold is expected; a spike right at MAX_SNAP_DISTANCE_M suggests the threshold is truncating legitimate matches and should be loosened.

2. Projection round-trip. Reproject a sample of matched node coordinates back to EPSG:4326 and confirm they equal the originals within floating-point tolerance — this catches a wrong or stale estimate_utm_crs() result before it corrupts every distance in the batch.

3. Rejected-station audit. For every accepted == False row, manually inspect the station against a basemap. Confirm it is a genuine data problem (courtyard placement, missing footpath in OSM) rather than an overly strict WALKABLE_HIGHWAY filter excluding a valid nearby way.

4. No cross-barrier snaps. Spot-check accepted stations near rivers, rail corridors, or elevated highways. A short Euclidean distance across a barrier the KD-tree cannot see is the most common silent failure mode of this approach.

5. Connectivity of matched nodes. Confirm every matched node_id belongs to the graph’s largest connected component. A node in an isolated fragment will accept the snap but produce an unroutable connector edge at query time.

6. Duplicate node handling. Verify that stations sharing a matched node_id are intentional (a dense hub or plaza) rather than an artifact of an overly coarse graph — check the ratio of unique stations to unique matched nodes and investigate any outlier clusters.

Related

• GTFS multi-modal trip-planning automation — the parent workflow that fuses these connector edges with GTFS transit schedules and OSM walk layers
• Integrating GTFS schedules into trip planning — building the time-expanded graph that consumes station access edges alongside transit connections
• Implementing multi-modal transit layers — where mode-transfer points like bike-share stations sit relative to the base road graph
• Valhalla configuration for multi-modal analysis — expressing access-point costing for connector edges when routing through a compiled engine