Trajectory Simplification & Smoothing

Within the Local Spatial Processing Patterns guide, this page covers what a gateway does with a sequence of positions rather than a single one. A GNSS receiver reporting at one hertz produces 86 400 fixes a day per asset, most of which describe a straight line the previous fix already described, plus a metre or two of noise the receiver invented. Simplification removes the redundancy; smoothing removes the noise. They are different operations with different failure modes, and running them in the wrong order or at the wrong stage is one of the most common quiet data-quality faults in field telemetry.

The stakes are concrete. Unsimplified tracks dominate the byte budget analysed in bandwidth and async sync optimization; unsmoothed tracks produce phantom geofence crossings, inflated distance-travelled totals and jittering map displays. Both are solvable on a Cortex-A gateway with bounded memory, and both go wrong in ways that are invisible until someone compares a computed total against a known ground truth.

Constraint mapping #

The last row explains why this section pays for itself. Simplifying a 1 Hz vehicle track at a 5 m tolerance typically retains 4–8% of the points with a maximum path deviation under the receiver’s own error — an order-of-magnitude reduction that costs nothing in fidelity anyone can measure.

Core technique 1: causal smoothing with an α-β filter #

A full Kalman filter is the right answer when the motion model matters and the tuning effort is available; the walkthrough for that is in Kalman filtering noisy GPS fixes on a gateway. For a large share of asset-tracking work the α-β filter — a fixed-gain simplification of the same idea — delivers most of the benefit in a dozen lines with no matrix arithmetic at all.

# alpha_beta.py — fixed-gain causal smoother for a position/velocity state.
# Constant memory, no allocation, no history. Safe in a hot loop and on an MCU.
class AlphaBeta:
    __slots__ = ("alpha", "beta", "x", "v", "t", "primed")

    def __init__(self, alpha: float = 0.35, beta: float = 0.05):
        # alpha weights the position correction, beta the velocity correction.
        # Larger alpha tracks manoeuvres faster and admits more noise.
        self.alpha, self.beta = alpha, beta
        self.x = self.v = 0.0
        self.t = 0.0
        self.primed = False

    def update(self, measurement: float, t: float) -> float:
        if not self.primed:
            self.x, self.t, self.primed = measurement, t, True
            return measurement
        dt = t - self.t
        if dt <= 0.0 or dt > 30.0:
            # Clock step or a long gap: re-prime rather than extrapolate wildly.
            self.x, self.v, self.t = measurement, 0.0, t
            return measurement
        self.t = t
        predicted = self.x + self.v * dt          # constant-velocity prediction
        residual = measurement - predicted
        self.x = predicted + self.alpha * residual
        self.v = self.v + (self.beta * residual) / dt
        return self.x

Run one instance per axis on projected coordinates, never on raw latitude and longitude — a degree of longitude is a different distance at every latitude, and a filter tuned in degrees is tuned for exactly one place. The projected frame comes from the transform described in coordinate reference systems at the edge.

The dt guard is what makes this deployable. A duty-cycled node produces gaps of minutes, and a constant-velocity prediction across a fifteen-minute gap places the asset kilometres from reality. Re-priming on a long gap is the honest behaviour: the filter has no information about that interval and should not pretend otherwise.

Core technique 2: bounded simplification #

Douglas–Peucker is the standard simplification algorithm and its textbook form is recursive, which on a track with a pathological shape can recurse as deeply as the point count. On an embedded target that is a stack overflow waiting for the right input. The iterative form with an explicit fixed-size stack has identical output and a bounded footprint; it is written out in full in Douglas–Peucker on a fixed-size stack.

For streaming use there is a cheaper option that needs no window at all. The dead-band rule retains a fix only when it deviates from the line between the last retained fix and the current one by more than a tolerance — a single-pass, constant-memory approximation that keeps around twice as many points as Douglas–Peucker for the same maximum error, and needs no buffer whatsoever.

Core technique 3: filling the gaps #

Removing points is only half the problem; a track also has holes, from an urban canyon, a tunnel, or a duty-cycled node that was asleep. The device has three options: leave the gap explicit, interpolate across it, or extrapolate through it with dead reckoning.

Leaving it explicit is almost always right for storage. A consumer that receives a track with a marked gap can decide what to do; one that receives an interpolated straight line through a tunnel cannot tell it from a measured one. Interpolation belongs at the presentation layer, not the acquisition layer.

Extrapolation with an inertial sensor is different, because it produces new information rather than an assumption. The accuracy and the honest time limits are set out in dead reckoning gap fill during GNSS outages — and the essential discipline is that extrapolated positions carry a flag and a growing uncertainty, so nothing downstream mistakes them for fixes.

Choosing tolerances from the job, not from the algorithm #

Every parameter in this section — the filter gain, the simplification tolerance, the gap policy — is usually inherited from whatever example the implementer read first, and every one of them should come from a statement about the job instead. Three questions produce all of them.

What is the smallest movement anyone will act on? For a delivery fleet, arriving at a stop is a movement of a few metres and the answer is around 5 m. For a rail wagon in a yard, being on one siding rather than another is tens of metres. For a container tracked across an ocean, nothing under a kilometre changes a decision. The simplification tolerance should sit just below that figure — close enough to preserve every actionable movement, large enough to discard everything else.

How accurate is the position actually? The receiver’s own error sets the floor. A tolerance below it preserves noise at full price, and a filter tuned to track motion smaller than it will chase that noise faithfully. Read the accuracy the receiver reports rather than the number on the datasheet: an antenna under a metal roof reports honestly, and the honest number is often five times the specification.

How long can a decision wait? This sets the smoothing gain. A geofence that triggers a physical interlock cannot wait three fixes for the filter to settle, so it needs a responsive filter and a wider hysteresis band to compensate. A daily utilisation report can afford a heavily smoothed track, because nothing is decided in the moment.

Those three answers interact in a way that is worth stating explicitly, because it is the source of most bad configurations: the tolerance must exceed the position error, and the hysteresis band must exceed both. A geofence band narrower than the simplification tolerance will see crossings appear and disappear depending on which points survived simplification — a failure that presents as intermittent, unreproducible event duplication and takes weeks to attribute correctly.

What each stage is allowed to change #

It is worth being pedantic about which stage may alter what, because the pipeline’s correctness depends on it and the constraints are easy to violate accidentally during a refactor.

The quality gate may reject a fix entirely. It must not modify one — a fix with poor geometry is either good enough to use or it is not, and a “corrected” fix with an optimistic accuracy figure attached poisons everything downstream that reads that figure.

The smoother may move a position and must not remove one. Its output is the same sequence at the same timestamps, with each position adjusted toward what the motion model considers plausible. It may also add information — an uncertainty estimate, a velocity — and downstream stages should use both.

The decision stage may not modify the sequence at all. It reads positions and emits events. Any stage that both decides and edits is one that will eventually decide based on its own edits.

The simplifier may remove positions and must not move the ones it keeps. A simplifier that also snaps points to a road network is doing two things, and the map-matched output is no longer a record of where the asset was measured to be — which matters the first time somebody disputes a report.

Holding to those four rules costs nothing and makes the pipeline auditable: given a raw track and the parameters, every downstream artefact is reproducible, and a discrepancy points at exactly one stage.

Operational considerations #

Track the retention ratio — points out over points in — as a first-class metric. It is a compact summary of both the receiver’s behaviour and the tolerance’s suitability. A ratio that jumps from 6% to 40% means the receiver has become noisy (blocked antenna, poor sky view) or the asset started behaving differently (stop-start traffic instead of a motorway). Either way it is visible days before the resulting bandwidth increase becomes a bill.

Watch the smoother’s residual too: the mean absolute difference between the raw measurement and the smoothed estimate. A residual that grows steadily indicates the filter’s motion model no longer matches reality — the classic case being a filter tuned for a vehicle being fitted to a slow-moving asset, where it lags every manoeuvre.

Reporting distance travelled, and why it is contentious #

Almost every fleet eventually computes distance travelled from a track, and almost every fleet eventually finds that two systems disagree about it by ten to thirty percent. The disagreement is not a bug in either system; it is the direct consequence of which stage of this pipeline each one measured.

Summing the straight-line distances between raw fixes over-reports, sometimes badly. Receiver noise adds a random walk on top of the real motion, and summing the magnitudes of those small random displacements adds them all in. A vehicle parked for eight hours with a live receiver can accumulate several kilometres of purely fictional travel this way.

Summing over smoothed positions removes most of that, because the filter has already rejected the motion the model considers implausible. It is the figure most operational reports should use, and it should say so.

Summing over the simplified track under-reports, because the retained points are chords across the removed detail. At a 5 m tolerance the shortfall is typically one to three percent on a road route and considerably more on a track with tight curves.

None of the three is wrong; they answer different questions. The failure is leaving the choice implicit, so that a report built from the spooled track disagrees with a dashboard built from the live stream, and nobody can say which is right because nobody wrote down which stage each one measured.

Three rules keep it manageable. Compute the total on the device, at the smoothed stage, and transmit it as a counter alongside the positions — that way the authoritative figure travels with the data and does not depend on which subset survived. Include the stage in the field name, so the number’s meaning is self-documenting. And when a stationary period is detected, add nothing at all: a filter clamped to zero velocity should contribute zero distance, which is the single change that removes most of the phantom mileage fleets discover in their first month.

The same reasoning applies to any derived quantity — time in motion, average speed, idle duration. Each of them depends on which stage produced its input, and each of them will eventually be compared against a figure from a different system. Deciding the stage explicitly, once, is cheaper than reconciling them later.

Failure modes and recovery #

Where this leaves the pipeline #

Assembled, the stages produce a device that emits three distinct products from one fix stream, each correct for its consumer. A live position — smoothed, uncertainty-tagged, updated per fix — drives the display and the decision logic. A stream of events — crossings, dwells, alarms — is emitted by the decision stage from that live position and never regenerated afterwards. And a stored track — simplified, quantised, spooled — carries the history at whatever resolution the byte budget allows.

Keeping those three separate is what makes the whole thing debuggable. When a report disagrees with what an operator remembers seeing, the question is which of the three products the report was built from, and each one has a defined provenance. When an event is missing, the decision stage’s inputs are recoverable from the stored track only if the track kept the relevant points — which is why simplification comes last, and why the event stream is emitted independently rather than derived later.

The recurring theme across every technique here is that lossy operations are fine as long as the loss is chosen, bounded and recorded. A track simplified at a stated tolerance is honest data. The same track simplified by whatever the buffer happened to drop is not, and the two are indistinguishable to anyone downstream unless the device says which it produced.

Related #

• Douglas–Peucker on a fixed-size stack — the bounded simplification implementation.
• Kalman filtering noisy GPS fixes on a gateway — the full filter, its tuning and its cost.
• Dead reckoning gap fill during GNSS outages — extrapolating honestly through an outage.
• Threshold-Based Event Mapping — the decision stage that must run before simplification.
• Delta Sync for Spatial Datasets — what happens to the retained points on the wire.