Dead Reckoning & Trajectory Interpolation Between GPS Fixes

A geofence evaluator that tests only the positions it receives is answering a question nobody asked. The question is “did this vehicle cross the boundary”, and the evidence is a sequence of samples of a continuous path — so a fence that fits entirely between two consecutive samples is crossed in reality and invisible in the data. At a 1 Hz update rate and 90 km/h, consecutive fixes are 25 m apart; at the 15-second cadence a battery-conscious mobile SDK often uses, they are 375 m apart. Every fence narrower than that gap is a coin flip. This page expands the sampling-and-continuity problem introduced in Core Architecture & Latency Constraints, and the failure it addresses is missed crossings between samples — together with its mirror image, the fabricated crossing produced when a pipeline interpolates through a dropout for longer than the physics supports.

The reader here has a geofence service whose accuracy complaints do not correlate with accuracy at all. The fixes are good; the fences are correct; the triggers are missing. The two techniques that close the gap are different in kind and must not be confused. Interpolation fills the space between two known fixes and is a statement about the past, made with both endpoints in hand. Dead reckoning extends forward from the last known fix using velocity and heading, and is a statement about the present, made with no endpoint at all. The first is nearly free and nearly always correct; the second decays and must be bounded.

What the Sampling Gap Actually Costs #

The probability that a point-sampled path misses a fence is governed by the ratio of the sampling stride to the fence’s smallest chord. For a convex fence of characteristic width $w$ crossed by a straight path at sampling stride $s=v\cdot \Delta t$, the probability that at least one sample lands inside is roughly $\min (1,w/s)$ — so the miss rate is approximately $1-w/s$ once $s>w$, and zero below it. The measured numbers from a mixed urban fleet, 6,000 fences with a median width of 140 m, bear this out:

The last two rows are the ones that matter commercially, because a 15–30 s cadence is what a mobile SDK negotiates down to when the operating system starts enforcing background-location budgets. A pipeline that behaves well against a 1 Hz test fleet can lose half its triggers in production for reasons that have nothing to do with the evaluator.

Interpolation converts the question from “is this point inside” to “does this segment intersect”, which is a different geometric predicate with a different cost and a much better answer:

Plain segment intersection recovers 98.6% of the missed crossings for roughly 2.3× the cost of a point test, and resampling the segment into more points buys essentially nothing — which is the single most useful result on this page, because midpoint resampling is the fix teams reach for first and it is the one that does not work. It does not work because a segment test is already exact for a straight path; the residual 0.7% is the curvature the straight line does not capture, and only a road-snapped polyline addresses that.

Segment Testing on the Critical Path #

The change to the evaluator is smaller than it sounds. Instead of testing a point against the candidate polygons, test a two-point LineString, and derive the transition from the relationship between the endpoints and the intersection:

from __future__ import annotations
from shapely.geometry import LineString, Point, Polygon

def segment_transitions(
    prev: tuple[float, float],
    curr: tuple[float, float],
    t_prev_ns: int,
    t_curr_ns: int,
    fence: Polygon,
) -> list[tuple[str, int]]:
    """Transitions implied by the straight path from prev to curr, with
    interpolated event times. Returns [] when the segment misses entirely."""
    seg = LineString([prev, curr])
    if not seg.intersects(fence):
        return []
    inside_prev = fence.contains(Point(prev))
    inside_curr = fence.contains(Point(curr))
    if inside_prev == inside_curr and not inside_prev:
        # Passed clean through: one ENTER and one EXIT inside the interval.
        clipped = seg.intersection(fence)
        if clipped.is_empty:
            return []
        a, b = clipped.coords[0], clipped.coords[-1]
        return [("ENTER", _lerp_ns(seg, a, t_prev_ns, t_curr_ns)),
                ("EXIT", _lerp_ns(seg, b, t_prev_ns, t_curr_ns))]
    if inside_curr and not inside_prev:
        pt = seg.intersection(fence.exterior)
        return [("ENTER", _lerp_ns(seg, _first(pt), t_prev_ns, t_curr_ns))]
    if inside_prev and not inside_curr:
        pt = seg.intersection(fence.exterior)
        return [("EXIT", _lerp_ns(seg, _first(pt), t_prev_ns, t_curr_ns))]
    return []                      # inside for the whole interval

def _lerp_ns(seg: LineString, at, t0: int, t1: int) -> int:
    frac = seg.project(Point(at)) / seg.length if seg.length else 0.0
    return int(t0 + frac * (t1 - t0))

The inside_prev == inside_curr and not inside_prev branch is the whole point: it is the pass-through case, invisible to point testing, and it emits two transitions from a single interval. Any pipeline that assumes at most one transition per input event will silently drop the EXIT here, which turns a missed crossing into a permanently stuck “inside” state — a worse bug than the one the interpolation was added to fix. The interpolated event times are also what make the transitions usable downstream: without them, both the ENTER and the EXIT carry the arrival timestamp of the second fix, and any dwell calculation built on them reports zero.

The candidate set has to widen to match. A point query against the spatial index returns fences containing the point; a segment query must return fences whose bounding box intersects the segment’s bounding box, which for a 375 m stride is a substantially larger envelope and therefore a larger candidate count. On the fleet measured above, moving from point to segment queries raised mean candidates per evaluation from 1.4 to 3.9 — the real cost of interpolation, and the reason the per-evaluation figure rose to 0.41 ms rather than staying near the point-test cost.

Dead Reckoning and Its Horizon #

Dead reckoning answers a different question: where is the device now, given that the last fix was 40 seconds ago? The projection itself is trivial — advance along the last known heading at the last known speed — and the engineering is entirely in knowing when to stop trusting it.

Error accumulates from three sources with different growth rates. Position error at the last fix is constant. Speed error integrates linearly with elapsed time. Heading error produces a cross-track error that grows as roughly $v\cdot t\cdot \sin (\delta \theta )$, which for small angles is also linear in $t$ but with a coefficient that is itself uncertain — and once the vehicle turns, the model is simply wrong rather than merely imprecise. Combining them, the projected uncertainty radius after $t$ seconds is approximately

$$r(t)\approx {\sigma }_0+{\sigma }_v\cdot t+v\cdot t\cdot {\sigma }_{\theta }$$

For a typical urban vehicle — ${\sigma }_0=8$ m, ${\sigma }_v=0.5$ m/s, $v=14$ m/s, ${\sigma }_{\theta }=0.09$ rad — the radius reaches 40 m at about 20 s and 100 m at about 50 s. Against a 140 m fence, projections beyond roughly 20 seconds cannot answer a containment question with any confidence, which is where the horizon in the table below comes from:

The policy that follows is a ladder rather than a threshold: project and emit while the cone is small relative to the fence, project but suppress while it is comparable, and stop projecting entirely once it exceeds the fence. Crucially, the comparison is per fence — the same 40 m cone is decisive for a 2 km congestion zone and useless for a 60 m loading bay — so the horizon is not a global constant but a function of the fence the projection is being tested against. Implementations that hard-code a single dead-reckoning timeout get one of the two cases wrong by construction.

The state machine that consumes the ladder is the fallback router described in fallback routing for GPS dropouts; this page supplies the geometry that decides when it should change state, and graceful degradation strategies for location APIs supplies the contract the degraded triggers travel under.

Memory, Churn and the Per-Device Track #

Both techniques need the previous fix, which means per-device state and therefore the same footprint discipline as any other per-device map. One previous fix is 48 bytes in a slotted dataclass — timestamp, latitude, longitude, speed, heading, accuracy — and 200,000 devices is 9.6 MB, which is negligible. The temptation to keep a track rather than a fix is where the footprint goes wrong: a 60-sample ring buffer per device for smoothing turns 9.6 MB into 580 MB, and the smoothing it enables is usually better achieved with a two-state filter that keeps no history at all, as covered in Kalman filter smoothing for noisy location streams.

Allocation churn is the sharper problem. The naive implementation above constructs a LineString, a Point, and an intersection geometry per fence per evaluation — at 25k evaluations/sec with 3.9 candidates each, that is roughly 300k Shapely objects per second, every one of which is a Python object wrapping a GEOS handle. Measured with tracemalloc, that costs 340 MB/s of allocation and pushes gen-2 collections from one every 90 s to one every 4 s. The fix is the standard one from memory-constrained spatial processing: pre-filter with a cheap analytic segment-versus-bounding-box test in pure arithmetic, and only build geometry for the candidates that survive. On the same fleet that reduced constructed geometries by 71% and returned the gen-2 interval to 26 s.

Async Placement and Ordering #

Segment testing consumes two consecutive fixes, so it inherits the ordering requirement of anything stateful: fixes must arrive per-device in event-time order, downstream of the reorder buffer described in event-time ordering and clock skew. Out-of-order arrival does not merely reorder the output here — it constructs a segment between two fixes that were never adjacent, which can sweep across half a city and intersect fences the vehicle never approached. That failure is dramatic and easy to spot in testing, and it is the reason segment interpolation must never be applied to a raw arrival-ordered stream.

The interpolated transitions also carry event times that are not the arrival time of any input event, which propagates into the emission layer. An ENTER interpolated to 0.6 s before the fix that revealed it must be published with that earlier event time so that dwell calculations and the idempotency key bucket land correctly — and because the key includes an event-time bucket, an interpolated instant that shifts when a later, better fix arrives will produce a different key and therefore a duplicate. The defence is to quantise the interpolated instant to the same bucket width the key uses before it is ever published, so a re-derived instant lands in the same bucket unless it genuinely moved.

Finally, the pass-through case emits two transitions from one input, which means the emission stage must be able to publish a burst without treating it as a queue anomaly. A bounded queue sized on the assumption of one output per input will report spurious backpressure the moment a motorway fleet drives through a corridor of small fences, an interaction covered in sizing bounded asyncio queues for geofence pipelines.

Operational Runbook #

1. Measure the sampling stride, not the cadence. Export stride_metres = speed × Δt as a histogram. Cadence alone is misleading: the same 5 s cadence is harmless in a depot and destructive on a motorway.
2. Compare the stride histogram against the fence-width histogram. The fraction of fences narrower than the P95 stride is the upper bound on how many crossings the pipeline can be missing. If that fraction is under 1%, interpolation is not worth its cost.
3. Quantify the miss rate directly. Replay a captured stream through both a point evaluator and a segment evaluator and diff the transition logs. The segment path should be a strict superset; any transition the point path emits that the segment path does not is a bug in the intersection code, most often a fence with an invalid ring.
4. Watch candidate fan-out after enabling segments. candidates_per_evaluation should rise by roughly the ratio of segment envelope area to point-query area. A rise of more than about 5× means the stride histogram has a long tail — usually a device reporting a stale fix after a long silence, which should be discarded rather than joined to the next fix.
5. Instrument dead-reckoned emissions separately. Tag every trigger with source=observed|interpolated|projected and alert on the projected fraction. A rising projected fraction is a connectivity regression, not a geofencing one, and will otherwise be diagnosed for weeks as a trigger-accuracy problem.
6. Cap the join gap. Never construct a segment across a gap longer than the dead-reckoning horizon for the fences in the envelope. Beyond it, the straight line is a fabrication, and the correct output is a gap in the track rather than an invented crossing.

Architectural Guidance #

Use segment interpolation whenever the P95 sampling stride is a meaningful fraction of the median fence width — in practice, whenever cadence is above about 2 s or speeds are above about 50 km/h. It is the highest-value change on this page: one predicate swap, a modest candidate fan-out, and an order-of-magnitude reduction in missed crossings.

Add road snapping only when curvature genuinely dominates, which in practice means dense street networks with small fences — kerbside pickup zones, bus-lane enforcement, city-centre delivery bays. It costs a map-matching service in the hot path and roughly 9× the evaluation time, and on the fleet measured here it bought 0.5 percentage points over plain segment testing.

Use dead reckoning only where the consumer can act on a probabilistic answer, and always with the confidence ladder attached. It is the right tool for keeping a live map plausible during a tunnel transit; it is the wrong tool for deciding a compliance boundary, where the honest output during a dropout is “unknown” rather than a projection.

Use none of the above when fixes are dense relative to fences — a 1 Hz fleet inside 2 km zones misses effectively nothing — and spend the effort on boundary hysteresis instead, which is where that fleet’s real trigger-quality problem will be.

FAQ #

Related #

• Core Architecture & Latency Constraints — the parent section, where the extra candidate fan-out has to be absorbed by the latency budget.
• Segment-Crossing Detection Between GPS Samples — the intersection predicate, its degenerate cases, and the analytic pre-filter.
• Kalman Filter Smoothing for Noisy Location Streams — a constant-memory alternative to keeping a track history.
• Speed Gating to Suppress Impossible Jumps — rejecting the fixes that would otherwise become fabricated segments.
• Fallback Routing for GPS Dropouts — the state machine that consumes the dead-reckoning confidence ladder.