Choosing a Coordinate Quantisation Grid for Delta Encoding

One number decides whether your deltas record edits or record floating-point noise, and it is usually chosen by copying whatever the last project used. This page is a focused companion to delta tracking algorithms for vector data.

Concept & Context

A coordinate stored as a double carries about fifteen significant digits. A survey captured with survey-grade GNSS is accurate to two or three centimetres. Everything between those two is arithmetic: the residue of a reprojection, a repeated transformation, or a library that rounds differently from the one that wrote the file.

Delta encoding compares coordinates, so it sees that residue as change. Without quantisation, a repository can record a full delta for a layer that nobody edited, purely because it passed through a reprojection. With quantisation set correctly, the same operation produces no delta at all.

The grid has a floor and a ceiling. It must be coarser than the capture noise — otherwise noise survives quantisation — and finer than the smallest edit that matters, or real work disappears. Between those two bounds the choice is mostly free, and the useful convention is to sit an order of magnitude below the survey accuracy: 1 mm for a 2–3 cm survey, 1 cm for a decimetre-accurate municipal layer, 10 cm for a display-only basemap.

The window a usable grid has to sit in Horizontal bars on a common scale showing floating-point noise, a survey's capture accuracy, the smallest edit worth recording, and two candidate grids — one inside the usable window and one above it, which would hide real edits. MAGNITUDE, IN METRES Arithmetic noise 1e-06 m reprojection residue — must be quantised away Grid: 1 mm 0.001 m inside the window Capture accuracy 0.03 m Smallest real edit 0.05 m Grid: 100 mm 0.1 m above the smallest edit — hides real work The grid must sit above the noise and below the smallest edit; everything between those two is a free choice.

Core Algorithmic Pipeline

  1. Establish the survey accuracy from the capture metadata, not from the coordinate precision in the file.
  2. Set a candidate grid an order of magnitude finer than that accuracy.
  3. Measure the phantom rate: round-trip a copy of the data through the pipeline without editing it, and count features reported as changed.
  4. Measure the miss rate: apply known edits at the smallest size that matters and confirm every one is detected.
  5. Record the grid in the delta header and in the layer metadata, so the number travels with the data.
Two errors, and only one of them is visible Two panels. A grid that is too fine produces deltas full of phantom changes, which is loud and annoying. A grid that is too coarse silently discards real edits, which produces no signal at all until somebody notices the working data disagrees with history. TOO FINE A full delta after a reprojection nobody made Repository grows while the data stands still Reviewers learn that deltas mean nothing Loud, and therefore self-correcting TOO COARSE A real edit produces an empty delta Working data and history quietly disagree Nothing in the pipeline reports anything Silent, and found only by a test that looks for it Measure both directions: the phantom rate on unchanged data, and the miss rate on known edits. Teams tune the left column because it complains. The right column is the one that costs data.

Working Implementation

"""Choose and verify a quantisation grid by measuring both failure directions."""
from __future__ import annotations

import geopandas as gpd
import numpy as np
from shapely import set_precision
from shapely.ops import transform


def quantise(gdf: gpd.GeoDataFrame, grid: float) -> gpd.GeoDataFrame:
    """Snap every coordinate onto the grid, in CRS units."""
    if gdf.crs is None or gdf.crs.is_geographic:
        raise ValueError(
            "quantisation must be applied in a projected CRS — a grid expressed "
            "in degrees is a different distance at every latitude"
        )
    out = gdf.copy()
    out["geometry"] = out.geometry.apply(lambda g: set_precision(g, grid))
    return out


def phantom_rate(gdf: gpd.GeoDataFrame, grid: float, epsg_via: int = 4326) -> float:
    """Fraction of features that a round trip makes look changed at this grid.

    The round trip is a stand-in for the ordinary operations a layer survives in
    a real pipeline — a reprojection out and back, which changes nothing that
    was measured and perturbs every digit that was not.
    """
    original = quantise(gdf, grid)
    round_tripped = quantise(
        gdf.to_crs(epsg=epsg_via).to_crs(gdf.crs), grid
    )
    same = [
        a.equals(b) for a, b in zip(original.geometry, round_tripped.geometry)
    ]
    return 1.0 - (sum(same) / len(same))


def miss_rate(gdf: gpd.GeoDataFrame, grid: float, edit_m: float,
              sample: int = 500, seed: int = 12345) -> float:
    """Fraction of deliberate edits of size `edit_m` that this grid hides."""
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(gdf), size=min(sample, len(gdf)), replace=False)

    before = quantise(gdf.iloc[idx], grid)
    shifted = gdf.iloc[idx].copy()
    shifted["geometry"] = shifted.geometry.apply(
        lambda g: transform(lambda x, y, z=None: (x + edit_m, y), g)
    )
    after = quantise(shifted, grid)

    hidden = [a.equals(b) for a, b in zip(before.geometry, after.geometry)]
    return sum(hidden) / len(hidden)


def evaluate(path: str, candidates=(0.0001, 0.001, 0.01, 0.1),
             smallest_real_edit_m: float = 0.05) -> None:
    gdf = gpd.read_file(path)
    print(f"{'grid (m)':>10} {'phantom %':>10} {'missed %':>9}   verdict")
    for grid in candidates:
        p = phantom_rate(gdf, grid) * 100
        m = miss_rate(gdf, grid, smallest_real_edit_m) * 100
        if m > 0:
            verdict = "too coarse — hides real edits"
        elif p > 1:
            verdict = "too fine — records noise"
        else:
            verdict = "usable"
        print(f"{grid:>10.4f} {p:>10.2f} {m:>9.2f}   {verdict}")


if __name__ == "__main__":
    evaluate("data/parcels.gpkg", smallest_real_edit_m=0.05)

A representative run on a parcel layer captured to 3 cm:

  grid (m)  phantom %  missed %   verdict
    0.0001      37.40      0.00   too fine — records noise
    0.0010       0.12      0.00   usable
    0.0100       0.00      0.00   usable
    0.1000       0.00     91.80   too coarse — hides real edits

Both usable rows are defensible; 1 mm leaves more headroom if the layer is later resurveyed with better equipment, and costs almost nothing in delta size relative to 1 cm.

Validation & Output Verification

# The chosen grid must produce a clean no-op on unchanged data
import geopandas as gpd
from quantise import quantise, phantom_rate

GRID = 0.001
gdf = gpd.read_file("data/parcels.gpkg")
assert phantom_rate(gdf, GRID) < 0.01, "the pipeline records change where none exists"

# And it must be recorded where the delta consumer will find it
import json
delta = json.load(open("deltas/parcels_2026-08-06.json"))
assert delta["quantisation_grid_m"] == GRID
assert delta["crs"] == gdf.crs.to_string()
print("grid recorded with the delta")
# A grid change is a migration, so make it visible in review
git log -p --follow -- params.yaml | grep -n "quantisation_grid" | head

If the grid appears in a commit alongside data changes, the review cannot separate the two — the diff will show nearly every feature as modified and nobody can tell which of those were real.

Failure Modes

  • A delta for a layer nobody edited — symptom: a full-size delta after a reprojection. Root cause: grid finer than the arithmetic noise. Fix: measure the phantom rate and move one order of magnitude coarser.

  • An edit that never reaches history — symptom: the working file differs from the last committed state and the delta is empty. Root cause: grid coarser than the edit. Fix: measure the miss rate against the smallest edit that matters; this failure is silent, so the test is the only signal.

  • Grid applied in a geographic CRS — symptom: precision varies by latitude across a national layer. Root cause: a grid expressed in degrees. Fix: quantise in a projected CRS, as the implementation enforces.

  • Two deltas cannot be compared — symptom: replaying a delta produces different geometry than expected. Root cause: the deltas were produced under different grids and neither recorded it. Fix: write the grid into the delta header and refuse to apply a delta whose grid differs from the target layer’s.

Why changing the grid is a migration A sequence showing what happens on the first run after a grid change: every coordinate lands on a different lattice, so the delta engine reports nearly every feature as modified, and a reviewer cannot separate that from real edits unless the change was committed on its own. Params Delta engine Reviewer grid 1 mm → 10 mm re-quantise both sides 182 400 features modified none of them edited by anyone Commit a grid change on its own, with a release note, or the next diff is unreviewable.

Back to Delta Tracking Algorithms for Vector Data