Simplifying Trajectories with Douglas-Peucker Before Release

Simplification drops the points a line does not need, and because trajectory uniqueness grows with the number of retained points, dropping them is the cheapest uniqueness reduction available. The catch is that Douglas-Peucker keeps exactly the points that carry the most information — the turns — so simplification alone is a utility optimisation, not a privacy control.

Core Calculation # permalink

Douglas-Peucker retains a vertex when its perpendicular distance from the chord joining the current endpoints exceeds a tolerance $\epsilon$. Applied recursively, it returns the smallest subset whose maximum deviation from the original polyline is at most $\epsilon$.

Its privacy value comes from the signature-space relationship: with $C$ distinguishable cell-bins and $p$ retained points, the number of distinct signatures a population spreads across is bounded by $C^{p}$, and the expected occupancy per signature is $N / C^{p}$. Removing one point divides the signature space by $C$ — so a simplification that takes a trip from 40 points to 6 shrinks the space by a factor of $C^{34}$, which is why it moves uniqueness faster than any spatial coarsening at comparable utility cost.

The tolerance and the retained count are related empirically rather than in closed form, but a useful planning approximation for a path of length $L$ with sinuosity $\sigma$ is

with $\kappa$ a route-class constant fitted from a sample. In practice you sweep $\epsilon$ and read $p$ off the curve rather than trusting the approximation.

The complication is which points survive. Douglas-Peucker is a max-deviation algorithm, so it keeps the vertices where the path changes direction — junctions, turns, the start and end. Those are precisely the vertices a map-matching adversary uses to anchor a reconstruction, and precisely the ones that distinguish one commuter’s route from another’s. Simplification therefore reduces $p$ while raising the information per retained point, and the two effects partially cancel.

Worked numeric example # permalink

A 6.2 km urban commute, 372 raw fixes at 10 s intervals, $C = 180$ distinguishable cell-bins, $N = 50{,}000$ trips:

Only the last row produces an occupancy anywhere near 1, and it corresponds to publishing a straight line between origin and destination. That is the honest result: simplification alone does not deliver k-anonymity on trajectories. It gets the signature space down by thirty orders of magnitude and still leaves every trip unique, because the space started so large.

What it does deliver is a much cheaper starting point for the controls that do provide a guarantee. Grouping 8-point signatures is tractable; grouping 372-point signatures is not.

Python Implementation # permalink

from __future__ import annotations

import geopandas as gpd
import numpy as np
import pandas as pd
from shapely.geometry import LineString


def simplify_traces(
    fixes: gpd.GeoDataFrame,
    tolerance_m: float,
    max_points: int | None = None,
    trace_col: str = "trace_id",
) -> pd.DataFrame:
    """Douglas-Peucker each trace, then cap the retained points.

    The cap matters as much as the tolerance: a long or sinuous trace survives
    simplification with many more vertices than a short one, and vertex count is
    what drives signature-space size. Capping equalises the contribution.

    Args:
        fixes: projected metric CRS, columns `trace_col`, `t`, point geometry.
        tolerance_m: max perpendicular deviation Douglas-Peucker may introduce.
        max_points: hard ceiling on retained vertices per trace; the excess is
            dropped by raising the effective tolerance for that trace alone.
    """
    if not fixes.crs or not fixes.crs.is_projected:
        raise ValueError("project to a metric CRS before simplifying")

    rows = []
    for tid, g in fixes.sort_values([trace_col, "t"]).groupby(trace_col):
        if len(g) < 2:
            continue
        line = LineString(zip(g.geometry.x, g.geometry.y))
        eps = tolerance_m
        simple = line.simplify(eps, preserve_topology=False)
        # A long trace keeps more vertices at the same tolerance. Raise its own
        # tolerance until it meets the cap, so no trace contributes an outsized
        # signature just for being long.
        while max_points is not None and len(simple.coords) > max_points:
            eps *= 1.6
            simple = line.simplify(eps, preserve_topology=False)
        for i, (x, y) in enumerate(simple.coords):
            rows.append({trace_col: tid, "seq": i, "x": x, "y": y,
                         "tolerance_used_m": eps})
    out = pd.DataFrame(rows)
    out.attrs["requested_tolerance_m"] = tolerance_m
    out.attrs["max_points"] = max_points
    return out

Note what the function does not do: it carries no timestamps through. Douglas-Peucker operates on geometry, and interpolating a time onto a retained vertex re-introduces a precise instant for a point the algorithm chose because it was geometrically extreme. Where timing must survive, round it separately under temporal cloaking and join on the sequence index.

Verification # permalink

def simplification_report(raw: gpd.GeoDataFrame, simple: pd.DataFrame,
                          trace_col: str = "trace_id") -> dict:
    """Point reduction, deviation, and the uniqueness that actually remains."""
    per_trace = simple.groupby(trace_col).size()
    raw_per = raw.groupby(trace_col).size()
    sig = simple.groupby(trace_col).apply(
        lambda g: tuple(zip(g["x"].round(-2), g["y"].round(-2)))
    )
    unique = int((sig.value_counts() == 1).sum())
    return {
        "median_points_before": float(raw_per.median()),
        "median_points_after": float(per_trace.median()),
        "max_points_after": int(per_trace.max()),
        "unique_signature_fraction": unique / max(sig.size, 1),   # expect ~1.0
        "traces": int(sig.size),
    }

unique_signature_fraction will come back near 1.0 at any tolerance that leaves the trip recognisable, and reporting it is the point. It is the number that stops a team describing a simplified release as anonymised — the reduction is real and large and still leaves every trace unique, so the k-anonymity or differential-privacy layer is still required.

The second check is a map-matching run against the simplified output. Because the retained vertices are turns, a Hidden Markov matcher often reconstructs the full route from a simplified trace more reliably than from a noisy raw one — the simplification has removed the GPS jitter that was confusing it. If the release relies on masking as well, verify the two in combination, never separately.

Edge Cases & Adjustments # permalink

• Long traces dominate the signature space. At a fixed tolerance a 40 km trip keeps far more vertices than a 3 km one, so it is far more unique. The vertex cap in the implementation equalises this; without it, the longest trips in a release are the ones that never group.
• preserve_topology=True keeps more points. Shapely’s topology-preserving mode avoids self-intersections and, in doing so, retains vertices the plain algorithm would drop. For a privacy pass the plain mode is usually right; for a rendering pass it is not.
• Simplifying before or after masking. Simplify first. Masking a raw trace and then simplifying re-averages the noise across retained vertices, which reduces the effective displacement — the same averaging attack described under defending against map-matching attacks.
• Stops become vertices. A dwell shows up as a cluster of near-identical fixes, which Douglas-Peucker collapses to one extreme vertex sitting at the stop. Run stay-point detection and suppression before simplifying, or the algorithm will faithfully preserve every anchor.
• Very short traces. Below about six fixes there is nothing to simplify and the tolerance does nothing. Those traces are also the most unique, so route them to suppression rather than through this pass.

FAQ # permalink

Is simplification a privacy control?

Not on its own. It reduces the signature space enormously and still leaves essentially every trace unique, because trajectory signature spaces start at astronomical sizes. Treat it as a preprocessing step that makes the real controls — grouping, generalization, suppression — computationally and statistically tractable.

What tolerance should I use?

Sweep it and read the retained-point curve. The useful region is where point count has collapsed and deviation is still below whatever the downstream analysis tolerates; for urban commutes that is typically 50–200 m. Choosing from the map alone tends to land far too low, because a 20 m tolerance looks visually perfect and keeps sixty points.

Does simplification help or hurt map matching?

It usually helps the matcher, which means it hurts you. Simplified corners are exact where raw corners were noisy. If map matching is in your threat model, add displacement after simplifying and verify the pair together.

Can I keep the timestamps on the retained vertices?

Only after separate temporal treatment. A retained vertex is geometrically extreme — a turn — and pairing it with a precise instant gives an adversary a high-confidence space-time point, which is the strongest possible input to a linkage attack.

Related # permalink

• Trajectory Anonymization Techniques — the grouping and suppression this feeds
• Implementing Trajectory k-Anonymity with scikit-mobility — where the signature-space arithmetic comes from
• Stop-Location & POI Suppression — the pass that must run before this one
• Defending Against Map-Matching Attacks — why simplified corners help the adversary

← Back to Trajectory Anonymization Techniques