Trace Resampling and Densification for Fleet GPS

Every fleet dataset is a mixture of reporting rates. The tractor units run a 1 Hz tracker, the vans report every thirty seconds, the subcontractor’s phones send whatever the operating system’s power manager allowed, and a tail of older devices only report on ignition events. Nothing downstream is built for that. Stop detection assumes a roughly uniform sampling interval when it computes windowed variance, speed profiling divides by an interval it expects to be constant, and any comparison between two vehicles silently compares two different measurement processes.

Resampling is the stage that makes the rest of the pipeline honest. It puts every trace on a stated time grid, records where the grid was filled from real observations and where it was not, and refuses to fill gaps that no reasonable interpolation can justify. Done well it is invisible. Done badly it is the most dangerous stage in the pipeline, because it manufactures data that looks exactly like measurement.

This page covers the whole of that stage: measuring the rate you actually have, choosing a target grid, filling short gaps, refusing long ones, densifying sparse geometry where a downstream consumer genuinely needs it, and simplifying dense geometry for storage and display without letting the simplified version leak back into analytics.

Prerequisites

• Python 3.11+, with pandas 2.2 or polars 1.0 and above. The examples use Polars for the batch paths and pandas where the API is clearer; both are shown where the idioms differ materially.
• Timestamps already normalised to UTC and monotonic per vehicle. If that is not true yet, do timestamp synchronisation first — resampling a trace whose clock drifts will bake the drift into the grid.
• Outliers already removed. Resampling after outlier removal is the only sane ordering; the reverse smears every spike across its neighbours.
• A projected CRS available for any distance-based work. Interpolating in degrees is acceptable for short gaps at low latitudes and wrong everywhere else — see coordinate reference system mapping.

The Sub-Problem: Why Naive Resampling Fails

The naive implementation is one line — df.resample("1s").interpolate() — and it is wrong in three distinct ways that all produce plausible-looking output.

It invents movement through gaps. A tracker that lost coverage in a tunnel for ninety seconds produces two fixes ninety seconds apart. Linear interpolation fills the gap with a perfectly straight line at a perfectly constant speed, through whatever terrain lies between. Nothing downstream can tell those points from observations, and a distance-based billing report will happily invoice the straight-line shortcut.

It creates stops that never happened, and destroys ones that did. Interpolating across a gap that spans a genuine two-minute stop produces a smooth constant-speed traversal, and the stop disappears. Conversely, upsampling a 60-second feed to 1 Hz creates fifty-nine near-identical points per interval during a slow crawl, which a variance-based stop detector will read as a stationary period.

It changes the statistics of the trace. Any speed, acceleration or heading derived from a resampled trace inherits the interpolation’s smoothness. Acceleration computed from linearly interpolated positions is exactly zero inside every filled interval, which makes a harsh-braking detector look wonderfully clean and entirely blind.

The fix in every case is the same and is not clever: resampling must record what it did. A grid slot filled from an observation and a grid slot filled by interpolation are different kinds of data point, and the only reliable way to stop them being confused is to keep them in different columns or to carry a flag that downstream code is obliged to read.

Step-by-Step Workflow

Step 1 — Measure the rate you actually have

The configured reporting interval is a statement of intent. The observed interval is a fact, and the two diverge constantly: devices back off under low battery, cellular retries batch several fixes into one flush, and firmware upgrades silently change defaults across part of the fleet.

import polars as pl

def observed_rate(fixes: pl.DataFrame) -> pl.DataFrame:
    """Median and 90th-percentile inter-fix interval per device-session."""
    return (
        fixes.sort(["device_id", "ts_utc"])
        .with_columns(
            (pl.col("ts_utc").diff().dt.total_seconds())
            .over("device_id")
            .alias("dt_s")
        )
        .filter(pl.col("dt_s").is_not_null() & (pl.col("dt_s") > 0))
        .group_by("device_id")
        .agg(
            pl.col("dt_s").median().alias("dt_median"),
            pl.col("dt_s").quantile(0.90).alias("dt_p90"),
            pl.len().alias("n_fixes"),
        )
    )

Two numbers matter. The median is the rate to design the grid around. The 90th percentile tells you how gappy the feed is: a device with a median of 30 seconds and a p90 of 240 seconds is not a 30-second device, it is a 30-second device with a coverage problem, and resampling it to a 30-second grid will produce a trace that is a quarter interpolation by volume.

Step 2 — Choose the target grid

The grid should be no finer than the slowest device you intend to serve from it. Upsampling adds no information; it only adds rows, and every added row is a chance for a downstream consumer to treat a reconstruction as an observation.

For mixed fleets the honest answer is usually two artefacts: a native-rate trace per vehicle for anything that needs full fidelity, and a coarse common grid for cross-fleet aggregates. Trying to serve both from one table is where the arguments start.

Step 3 — Align to the grid without inventing anything

Alignment and interpolation are different operations and should be separate steps. Alignment moves an existing fix to the nearest grid slot within a tolerance; interpolation creates a value where no fix exists. Doing alignment first means the interpolation step only ever sees genuinely empty slots.

def align_to_grid(fixes: pl.DataFrame, every: str = "30s", tol: str = "10s") -> pl.DataFrame:
    """Snap each fix to the nearest grid slot within `tol`. No values are created."""
    grid = (
        fixes.select(
            pl.datetime_range(
                pl.col("ts_utc").min().dt.truncate(every),
                pl.col("ts_utc").max().dt.truncate(every),
                every,
                time_zone="UTC",
            ).alias("slot")
        )
    )
    return grid.join_asof(
        fixes.sort("ts_utc"),
        left_on="slot",
        right_on="ts_utc",
        strategy="nearest",
        tolerance=tol,
    ).with_columns(
        pl.col("lat").is_not_null().alias("observed")
    )

The observed column is the whole point. Every row that leaves this function is either a real fix moved by up to the tolerance, or an empty slot — and the flag says which.

Step 4 — Fill short gaps, refuse long ones

The interpolation limit is a policy, and like every policy in this pipeline it should be derived from something rather than chosen because it looked reasonable. The defensible derivation is: fill a gap only if the distance a vehicle could plausibly cover within it is smaller than the resolution the downstream consumer cares about.

At 30-second reporting and 50 km/h, one interval is 420 metres. Two intervals is 830 metres — most of a city block grid, and enough to contain several turns. That is why “twice the native interval” keeps appearing as a limit: it is roughly the point at which the straight line stops being a defensible approximation of the path.

NATIVE_S = 30
LIMIT_SLOTS = 2                       # fill gaps up to 2 × native interval

def fill_short_gaps(aligned: pl.DataFrame) -> pl.DataFrame:
    return aligned.with_columns(
        pl.col("lat").interpolate().alias("lat_filled"),
        pl.col("lon").interpolate().alias("lon_filled"),
        # run length of the current null streak, forwards and backwards
        pl.col("observed").cum_sum().alias("_grp"),
    ).with_columns(
        pl.len().over("_grp").alias("_gap_len")
    ).with_columns(
        pl.when(pl.col("observed"))
          .then(pl.lit("observed"))
          .when(pl.col("_gap_len") <= LIMIT_SLOTS + 1)
          .then(pl.lit("interpolated"))
          .otherwise(pl.lit("missing"))
          .alias("provenance")
    ).with_columns(
        pl.when(pl.col("provenance") == "missing").then(None).otherwise(pl.col("lat_filled")).alias("lat"),
        pl.when(pl.col("provenance") == "missing").then(None).otherwise(pl.col("lon_filled")).alias("lon"),
    ).drop(["_grp", "_gap_len", "lat_filled", "lon_filled"])

Three provenance values, not two. missing is a first-class outcome and must survive into storage — a null row that says “we do not know where this vehicle was at 14:32:00” is far more useful than a row that quietly guesses.

Step 5 — Densify only where a consumer needs it

Densification is the opposite operation: adding vertices along a known path so that a downstream geometric test has enough resolution. It is legitimate in exactly one situation — when the path between two points is known, not assumed.

After map matching, the path between two matched fixes is known: it is the routed geometry the matcher already returned. Densifying along that geometry is not interpolation in the dangerous sense, because the shape comes from the road network rather than from a straight line. That makes densification a post-matching operation, and running it before matching is a common and expensive mistake.

The usual consumers are geofence tests and corridor analyses. A vehicle that passes through a 200-metre geofence at 80 km/h spends nine seconds inside it; at 30-second reporting there may be no fix inside the polygon at all, and a naive point-in-polygon test will miss the visit entirely. Densifying the matched geometry to a 20-metre spacing before the test fixes it — and the densified points must still be flagged, because they are not observations either.

Step 6 — Simplify for storage and display

Simplification runs in the other direction and answers a different question: how few vertices can represent this line without a viewer noticing? The Douglas-Peucker algorithm is the standard answer, and for urban delivery traces a tolerance of three to five metres typically removes seventy to eighty percent of vertices with no visible change at city zoom levels.

The discipline is to keep the simplified geometry as a separate artefact. It belongs in the tile pipeline and the map view; it does not belong in the analytical store, because every metric derived from it — distance, duration in a zone, speed profile — is computed over a line that has had its detail deliberately removed.

from shapely.geometry import LineString

def display_geometry(matched: LineString, tolerance_m: float = 4.0) -> LineString:
    """Simplify for tiles. Never feed the result back into analytics."""
    return matched.simplify(tolerance_m, preserve_topology=True)

Choosing an Interpolation Limit From the Data

Rather than picking a limit and defending it, derive it. Take a corpus of high-rate traces, downsample them to the rate you actually have, interpolate the gaps at a range of limits, and measure the error against the original. The curve that comes out is specific to your operating area and settles the argument.

The shape is consistent across fleets: error grows slowly while the gap is shorter than the distance between decision points in the network, then rises sharply once a gap can contain a turn. In a dense European city that inflection is around forty to sixty seconds. On motorway corridors it is several minutes, because there is nowhere to turn.

Operational Troubleshooting

Interpolated share climbs after a firmware rollout. The devices changed their reporting behaviour and the grid did not. Re-measure the observed rate per device family before adjusting anything else; the correct response is usually a coarser grid for that family, not a longer interpolation limit.

Resampled traces are larger than the raw feed. Upsampling is happening somewhere. Check that the grid is not finer than the slowest contributing device, and that a per-vehicle native path has not been accidentally routed through the fleet-wide grid.

Stop counts fall after resampling is introduced. Stops are being interpolated away, exactly as in the first figure. Move stop detection ahead of resampling, or run it on the native trace and join the results onto the grid.

Distance totals rise slightly and consistently. Alignment tolerance is too generous, so fixes are being moved by several seconds and the small displacements accumulate. Tighten the tolerance to a third of the grid interval.

Distance totals rise sharply on some vehicles. Long gaps are being filled. Check the provenance distribution for the affected vehicles; a straight-line fill across a coverage hole under-reports distance more often than it over-reports it, so a rise usually means the gap fill is being applied across a genuine stop and adding movement.

A downstream job crashes on nulls. That is the system working. The alternative — filling the gap — would have produced a wrong answer silently. Give the consumer an explicit policy for missing slots rather than removing the nulls.

Deployment Checklist

• Observed inter-fix interval measured per device family, not assumed from configuration
• Grid interval no finer than the slowest device served from it
• Alignment tolerance set to at most one third of the grid interval
• Interpolation limit derived from a downsampling experiment on real traces
• Provenance column present on every row and propagated into storage
• Missing slots stored as nulls rather than dropped
• Stop detection runs on the native trace, ahead of resampling
• Densification restricted to post-matching geometry, and flagged
• Simplified display geometry stored separately from analytical geometry
• Interpolated-share metric published per vehicle-day and alerted on

Related

• Interpolating GPS gaps during tunnel signal loss — the gap-filling policy ladder in detail
• Timestamp synchronisation for multi-device GPS logs — the alignment work that must happen before any grid exists
• Outlier removal in raw telematics streams — why cleaning precedes resampling
• Sliding-window variance stop detection — the consumer most damaged by careless resampling
• GPS Data Preprocessing & Cleaning Fundamentals — parent section covering the whole preprocessing stage