Snapping Noisy Positions to the Indoor Routing Graph

This page is the implementation companion to Snapping Positioning Fixes onto the Routing Graph: a single self-contained snapper that takes a noisy (x, y, level) fix and returns the edge it belongs on, where along that edge, and how far off it was.

What Snapping and Map-Matching Mean #

Snapping is the act of resolving a continuous position estimate to a discrete location on a network. The router does not understand “you are at (12.4, 8.1)”; it understands “you are on edge (n17, n18), 3.2 metres from its start, on level 2.” Snapping computes that translation for a single fix: find the nearest routable edge, project the fix perpendicularly onto it, and report the foot of that perpendicular as the on-graph location.

Map-matching is snapping with memory. A lone fix snapped in isolation will jump between edges as the estimate jitters, so map-matching adds a cross-frame rule that biases the answer toward continuity — the user was on this edge last frame, so prefer to keep them here unless the evidence for switching is strong. The lightweight version used here is hysteresis: a distance margin the new edge must beat before the snap will leave the current one. That single rule removes almost all of the oscillation a memoryless snapper suffers between parallel corridors, without the full sequence-scoring machinery of a hidden-Markov matcher.

Minimal Working Example #

The function below snaps one fix. It builds an R-tree over edge geometries once, queries candidates near the fix, projects onto each candidate on the correct level with shapely, and returns the best snap or None when the fix is off-graph.

import logging
from dataclasses import dataclass
from typing import Optional

from rtree import index
from shapely.geometry import LineString, Point

logger = logging.getLogger(__name__)


@dataclass
class Snap:
    edge_id: int
    point: tuple[float, float]
    offset: float        # metres along the edge from its start
    distance: float      # perpendicular distance from the fix, metres


def build_index(edges: list[tuple[LineString, int]]) -> index.Index:
    """Index edge bounding boxes; edges is a list of (geometry, level)."""
    idx = index.Index()
    for i, (geom, _level) in enumerate(edges):
        idx.insert(i, geom.bounds)
    logger.info("indexed %d edges", len(edges))
    return idx


def snap(fix: tuple[float, float], level: int, edges: list[tuple[LineString, int]],
         idx: index.Index, max_snap: float = 4.0, radius: float = 6.0) -> Optional[Snap]:
    """Snap one fix to the nearest same-level edge, or None if it is off-graph."""
    x, y = fix
    p = Point(fix)
    hits = list(idx.intersection((x - radius, y - radius, x + radius, y + radius)))
    best: Optional[Snap] = None
    for i in hits:
        geom, edge_level = edges[i]
        if edge_level != level:                     # never snap across floors
            continue
        offset = geom.project(p)
        proj = geom.interpolate(offset)
        d = p.distance(proj)
        if best is None or d < best.distance:
            best = Snap(i, (proj.x, proj.y), offset, d)
    if best is None or best.distance > max_snap:
        logger.info("fix (%.2f, %.2f) off-graph; holding last location", x, y)
        return None
    return best

To add hysteresis across a stream, keep the previous Snap and only accept a different edge when it beats the held edge by a margin:

def apply_hysteresis(new: Optional[Snap], prev: Optional[Snap], margin: float = 0.75) -> Optional[Snap]:
    """Prefer the previous edge unless the new one is closer by more than `margin`."""
    if new is None or prev is None or new.edge_id == prev.edge_id:
        return new
    return new if (prev.distance - new.distance) > margin else prev

Snapping Parameter Reference #

Size radius and max_snap from your positioning error, not from arbitrary round numbers: if the filtered fixes have a ~1.5 m standard deviation, a 4 m ceiling captures the vast majority of legitimate fixes while still rejecting genuine outliers.

Common Errors & Fixes #

The blue dot jumps up a floor near the stairwell. The level guard is missing or the fix carries the wrong level. A shapely projection is purely 2D, so an edge one storey up is often Euclideanly closer than the correct edge below it. Verify the fix’s level and filter candidates before the distance comparison:

if edge_level != level:
    continue          # this line is the whole fix — never compare distance across levels

The snapped point oscillates between two hallways every second. Two parallel corridors sit within the fix noise, and a memoryless snap picks whichever is marginally nearer each frame. Add apply_hysteresis around the raw snap call so leaving the current edge costs a real distance improvement:

prev = apply_hysteresis(snap(fix, lvl, edges, idx), prev, margin=0.75)

Every fix returns None and the marker never moves. No candidate edge falls within max_snap, usually because the fix stream and the graph are in different frames or scales — one in metres, one in millimetres, or a shifted origin. Assert a known point before trusting the stream: snap a fix you know sits on a corridor and confirm a small distance. If it comes back tens or thousands of units off, the coordinate frames disagree and no snapping parameter will rescue it.

Integration Point #

This snapper is the last transform before routing. Its input is the smoothed pose emitted by the particle filter implementation — one clean (x, y, level) per frame rather than raw radio jitter — and the design reasoning behind each stage lives in the parent guide, Snapping Positioning Fixes onto the Routing Graph. Its output, the Snap, becomes the router’s start location: edge_id and offset together name a point on the network the wayfinding engine can begin a path from. Keep smoothing and snapping as separate stages — the filter removes noise, the snapper constrains to the graph — so each can be tuned and validated on its own against a surveyed walk.

Frequently Asked Questions #

Related #

• Snapping Positioning Fixes onto the Routing Graph — the parent guide with the full three-stage design, edge-case table, and diagram.
• Implementing a Particle Filter for Indoor Positioning — the source of the smoothed pose this snapper consumes.

This page is part of the Positioning-to-Graph Integration guide within the Indoor Positioning & Fingerprinting reference.