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.

Bike-share station snapping via KD-tree nearest-node search Left panel: a station point falls inside its snap-distance threshold circle, so the nearest routable OSM node is selected and a connector edge is drawn. Right panel: a station's nearest routable node lies outside the threshold circle, so the snap is rejected and flagged for review instead of inserting a connector edge. Accepted — within threshold Rejected — exceeds threshold max_snap_distance_m motorway node nearest node station Connector edge inserted; weight = distance / walk speed max_snap_distance_m nearest node station No connector inserted; station flagged for review

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

Parameter Default Effect
k (neighbors queried) 1 Query k=3–5 when you want fallback candidates ready if the nearest node is later disqualified by a manual review or a connectivity check
MAX_SNAP_DISTANCE_M 35 m Tighten to 15–20 m in dense grid cities where every block has multiple walkable ways; loosen to 60–80 m for suburban or campus deployments with sparser path networks
WALKABLE_HIGHWAY filter set of highway classes Excludes motorway, trunk, and primary nodes without pedestrian access; add steps if the deployment includes stations near stairways you want represented as connectors
workers (cKDTree.query) -1 (all cores) Matters once you are snapping tens of thousands of stations against continent-scale extracts; negligible below a few thousand stations
UTM CRS selection estimate_utm_crs() Recompute per extract — a national GBFS aggregator can span multiple UTM zones, and reusing one zone across the whole dataset introduces distortion at the edges
distance_upper_bound unset Pass MAX_SNAP_DISTANCE_M * 3 to tree.query to let scipy prune the search early on very large graphs, at the cost of inf distances for genuinely out-of-range stations

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.

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.

Why does snapping with raw lat/lon degrees produce wrong distances?

A cKDTree built directly on decimal-degree coordinates measures Euclidean distance in degree-space, not meters. Because a degree of longitude shrinks with cos(latitude), the same coordinate delta represents a shorter ground distance at high latitude than near the equator. This distorts every MAX_SNAP_DISTANCE_M comparison unless coordinates are first projected into a local planar CRS such as UTM.

What happens to a bike-share station with no routable node inside the threshold?

The snap is marked accepted=False and no connector edge is inserted. Route these to a manual review queue instead of dropping them silently — common causes are a coordinate error in the operator’s feed, a station inside a courtyard or plaza with no adjacent walkable way, or an OSM extract that has not been refreshed since a nearby path was mapped.

Can multiple stations snap to the same OSM node?

Yes, and it’s expected rather than a bug. Docks clustered around one intersection or transit hub often share the nearest routable node. This is safe for routing correctness because each station keeps its own synthetic station:<id> node and connector edge; it only becomes a problem if station metadata is later deduplicated by node_id, which would silently merge distinct stations.