Segment-Crossing Detection Between GPS Samples

The predicate change described in dead reckoning and trajectory interpolation — from “is this point inside” to “does this segment cross the boundary” — is a one-line change in principle and a performance problem in practice. A segment query has a larger candidate envelope than a point query, and every surviving candidate requires an intersection computation that allocates. This page, sitting within Core Architecture & Latency Constraints, covers the predicate itself, its degenerate cases, and the analytic pre-filter that makes it affordable on the hot path.

Concept and specification #

The question a segment test answers is richer than a containment test, and the richness is the reason a naive implementation gets it wrong. For a segment $S$ from $p_0$ to $p_1$ and a fence polygon $F$, four outcomes are possible, and each implies different transitions:

$$\begin{array}{rlrlrlrlrlrlr}& amp;p_0\notin F,;p_1\notin F,;S\cap \partial F=\varnothing & amp;& amp;\Rightarrow \text{no transition}& amp;p_0\notin F,;p_1\in F& amp;& amp;\Rightarrow \text{ENTER at the crossing}& amp;p_0\in F,;p_1\notin F& amp;& amp;\Rightarrow \text{EXIT at the crossing}& amp;p_0\notin F,;p_1\notin F,;S\cap \partial F\ne \varnothing & amp;& amp;\Rightarrow \text{ENTER then EXIT}\end{array}$$

The fourth case is the pass-through, and it is the one that motivated the whole change: both endpoints are outside, so no point test can see it, and it emits two transitions from one input event. A pipeline whose emission stage assumes at most one transition per event drops the EXIT, leaving the pair permanently INSIDE — a worse outcome than the missed crossing the change was meant to fix.

The join-gap bound is the safety parameter. A segment is a claim that the device travelled in a straight line between two observations, and that claim gets weaker with time and distance. Beyond the bound the honest representation is a discontinuity in the track rather than a straight line, and the pipeline should emit nothing rather than a fabrication.

Step-by-step implementation #

1. Reject cheaply before constructing anything. The dominant cost of the naive implementation is object construction, so the pre-filter must be pure arithmetic on primitives — no Point, no LineString, no allocation. A slab test against the fence’s bounding box rejects the vast majority of candidates:

from __future__ import annotations

def segment_bbox_hits(
    x0: float, y0: float, x1: float, y1: float,
    minx: float, miny: float, maxx: float, maxy: float,
) -> bool:
    """Liang-Barsky slab clip: True when the segment could touch the box.
    Pure float arithmetic — no geometry objects, no allocation."""
    if max(x0, x1) < minx or min(x0, x1) > maxx:
        return False
    if max(y0, y1) < miny or min(y0, y1) > maxy:
        return False
    dx, dy = x1 - x0, y1 - y0
    t0, t1 = 0.0, 1.0
    for p, q in ((-dx, x0 - minx), (dx, maxx - x0),
                 (-dy, y0 - miny), (dy, maxy - y0)):
        if p == 0.0:
            if q < 0.0:
                return False          # parallel and outside this slab
            continue
        r = q / p
        if p < 0.0:
            if r > t1:
                return False
            t0 = max(t0, r)
        else:
            if r < t0:
                return False
            t1 = min(t1, r)
    return t0 <= t1

2. Build geometry only for survivors. On the fleet measured here the slab test rejected 94% of index candidates at 60 ns each, so only 6% ever reach Shapely. That single reordering is worth more than any micro-optimisation inside the intersection itself.

3. Derive transitions from endpoint containment plus the intersection. Compute the two endpoint containments once and reuse them; do not infer them from the intersection result, which is ambiguous for a segment that merely touches a vertex.

4. Interpolate the event time by arc-length fraction. The crossing’s event time is $t_0+f(t_1-t_0)$ where $f$ is the fraction of the segment’s length at the intersection. Compute $f$ with project() on the segment rather than by comparing coordinates, which is wrong for a segment that doubles back.

5. Quantise the interpolated instant to the idempotency bucket. An interpolated instant is an estimate, and a later, better fix can shift it by tens of milliseconds — producing a different idempotency key and therefore a duplicate. Round the instant to the same bucket width the key uses before publishing.

6. Order multiple transitions by fraction. A segment crossing a concave fence can produce four or more intersection points. Sort them by $f$ and emit alternating ENTER/EXIT starting from the state implied by $p_0$; emitting them in the order the geometry library returns them is not guaranteed to be spatial order.

Benchmark and verification #

Measured over 12 million segment evaluations against a 1.2M-polygon index, mean 3.9 candidates per evaluation:

The third row is the headline: the pre-filter halves the cost and returns the gen-2 collection interval from 4 s to 26 s while changing the answer not at all — the slab test is conservative, so it never rejects a segment that genuinely intersects. The fourth row adds shapely.prepared.prep on the fence geometry, which pays for itself once a fence is tested more than about three times, and on a fleet with geographic concentration most fences are tested thousands of times per second.

Verification is a differential replay. Run a captured stream through the point evaluator and the segment evaluator and assert the segment output is a strict superset. Any transition the point path emits and the segment path does not is a bug — in practice, nearly always a fence whose ring is invalid, where contains() and intersects() disagree. Feed those fences to the validity repair described in handling polygon edge cases in high-frequency telemetry rather than working around them in the evaluator.

Failure modes and edge cases #

The last row is the mistake that makes the whole change silently ineffective. If the index is still queried with the point, the candidate set contains only fences containing that point, and no pass-through fence is ever a candidate — so the expensive segment predicate runs against a candidate set that could never contain the crossing it was added to find. The symptom is a change that costs 2× the CPU and improves the miss rate by nothing, and it is worth asserting in a test: a fence entirely between two endpoints must appear in the candidate set.

Touching cases deserve one more note. A segment that grazes a fence vertex without entering produces an intersection of dimension zero and containment False at both endpoints, which the fourth case above would report as ENTER-then-EXIT at the same instant. Filter out pass-throughs whose two crossing fractions differ by less than the snap tolerance; they are tangencies, not traversals, and emitting them produces zero-duration dwells that downstream consumers treat as data errors.

Related #

• Dead Reckoning & Trajectory Interpolation — the parent topic and the cost model for the wider candidate envelope.
• Speed Gating to Suppress Impossible Jumps — rejecting the fixes that would otherwise become fabricated segments.
• Bounding-Box Prefilters Before Exact Containment — the same reordering applied to the point path.