Douglas-Peucker Simplification for Fleet Trace Storage

A year of fleet traces is mostly redundant vertices. A vehicle travelling in a straight line at 1 Hz emits a fix every fourteen metres, and a hundred of them describe a stretch of motorway that two points would describe just as well for any purpose involving a screen. Douglas-Peucker removes those points, and for tile serving and archival it removes a great many of them.

The danger is not the algorithm; it is what happens after. A simplified line is shorter than the one it replaced, its speed profile is smoother, and any dwell computed against a polygon it passes near will differ. This page covers how to choose the tolerance, how to keep the result valid, and — most importantly — how to keep the simplified geometry from leaking into anything that measures. It extends the storage half of trace resampling and densification.

Compatibility and Configuration Requirements

The projected-CRS requirement is not pedantry. A tolerance of 0.00001 degrees is 1.11 metres of latitude everywhere and between 1.11 and 0.4 metres of longitude depending on where the vehicle is, so a fleet operating across a continent will simplify its northern traces roughly three times harder than its southern ones — see coordinate reference system mapping.

A Self-Contained Simplifier

from __future__ import annotations

import geopandas as gpd
import numpy as np
import shapely


# Web Mercator ground resolution at the equator, metres per pixel, 256 px tiles.
_M_PER_PX_Z0 = 156_543.03392


def tolerance_for_zoom(zoom: int, latitude_deg: float = 52.0, px: float = 0.5) -> float:
    """Ground tolerance in metres that is `px` pixels at the given zoom level."""
    m_per_px = _M_PER_PX_Z0 * np.cos(np.radians(latitude_deg)) / (2**zoom)
    return float(m_per_px * px)


def simplify_for_display(
    traces: gpd.GeoDataFrame,
    zoom: int = 16,
    geometry_col: str = "geometry",
    out_col: str = "geometry_display",
) -> gpd.GeoDataFrame:
    """Add a simplified geometry column sized for a target zoom level.

    The original geometry is untouched. Anything that measures distance,
    duration or containment must keep using it.
    """
    if traces.crs is None or traces.crs.is_geographic:
        raise ValueError("simplify in a projected CRS — degrees make the tolerance vary by latitude")

    tol = tolerance_for_zoom(zoom, latitude_deg=float(traces.geometry.centroid.y.mean()))
    out = traces.copy()
    out[out_col] = shapely.simplify(
        traces[geometry_col].values, tolerance=tol, preserve_topology=True
    )
    out.attrs["display_tolerance_m"] = tol
    out.attrs["display_zoom"] = zoom
    return out

Two things are worth noticing. The tolerance is derived from the zoom level, not chosen; and the result goes in a new column, so no caller can accidentally receive the simplified line when it asked for the trace.

Execution and Tuning Guidelines

Zoom, then tolerance. Decide the deepest zoom the layer will be drawn at, then compute the tolerance. A fleet overview map that never goes past zoom 12 can tolerate a 20-metre tolerance and save an order of magnitude of storage; a driver-facing replay at zoom 18 cannot.

Simplify per trip, not per day. Simplifying a whole day as one line lets the algorithm remove a vertex at the boundary between two trips, which moves the endpoint of one trip and the start of the next. Segment first — see splitting trips on ignition cycles — and simplify each trip independently.

Keep preserve_topology=True unless you have measured that you can afford otherwise. It is slightly slower and it prevents the algorithm from producing a self-intersecting line from a valid input, which is the failure that turns into an invalid geometry error three stages downstream.

Store the tolerance with the geometry. A simplified line whose tolerance is unknown cannot be reasoned about later. A small integer column costs nothing and answers the question “how far off can this be?” without an archaeology exercise.

Common Pitfalls Specific to This Technique

Simplifying before map matching. The matcher uses the shape of the trace to discriminate between candidate paths, and simplification removes exactly the small deviations that distinguish a service road from the carriageway beside it. Simplify the matched output if you must simplify at all, never the input.

Letting the simplified column become the default. The most common route to a wrong distance report is a view or a materialised table that selects geometry_display because it was the smaller column and the join was faster. Name the columns so the mistake is visible in the query, and put the tolerance in the name if you have more than one.

Assuming simplification is idempotent across tolerances. Simplifying at 2 m and then again at 5 m does not give the same line as simplifying once at 5 m; Douglas-Peucker is sensitive to which vertices survive the first pass. Always simplify from the original when producing a new tolerance.

Serving Two Geometries Without Confusing Them

The operational risk in simplification is not the algorithm — it is the second column. Once a table holds two representations of the same journey, somebody will eventually read the wrong one, and the resulting error is invisible: distances come out a few percent low and nothing raises.

Three conventions prevent it, and all three are cheap.

Name the column after what it is for, not after what it is. geometry_display_z16 is harder to select by accident than geometry_simple, and the name carries the tolerance so a reader knows what they are holding. If a second zoom level is added later, the naming scheme already accommodates it.

Give the two columns different types where the store allows it. In PostGIS, keeping the analytical geometry in a projected SRID and the display geometry in EPSG:3857 makes an accidental mix raise a mixed-SRID error instead of returning a plausible number. The type system is doing the review that nobody has time to do.

Compute derived metrics once, at write time, from the analytical geometry. If distance_m, duration_s and mean_speed_kmh are materialised columns rather than expressions evaluated at query time, the display geometry is never in a position to influence them. A view that recomputes distance from whatever geometry column is in scope is the mechanism by which the error actually happens.

-- Analytical geometry in a projected SRID; display geometry in Web Mercator.
ALTER TABLE trips
    ADD COLUMN geometry            geometry(LineString, 32631) NOT NULL,
    ADD COLUMN geometry_display_z16 geometry(LineString, 3857),
    ADD COLUMN distance_m          double precision NOT NULL,
    ADD COLUMN display_tolerance_m real;

-- This raises rather than lying, because the SRIDs differ.
-- SELECT ST_Length(geometry_display_z16) FROM trips;

Regenerating after a tolerance change

Because Douglas-Peucker is not idempotent across tolerances, a change of zoom level means regenerating from the original geometry rather than re-simplifying the existing display column. Treat the display geometry as a cache: it can always be rebuilt, it is never the source, and dropping it entirely should cost nothing but CPU. A pipeline that cannot cheaply rebuild it has quietly promoted it to a source of truth.

Related

• Trace resampling and densification — parent topic, where simplification sits relative to resampling
• Compressing fleet trajectory archives without losing fidelity — the lossless alternative when storage is the real constraint
• Writing matched trajectories to GeoParquet with Polars — holding both geometries in one file
• Coordinate reference system mapping for fleet data — why the tolerance must be metres
• GPS Data Preprocessing & Cleaning Fundamentals — parent section