#Detecting Changed Features with Geometry Hashing

A feature fingerprint is only useful if two exports of an unchanged feature produce the same digest — and by default they do not. Ring orientation flips, starting vertices rotate, projection round-trips perturb the sixteenth decimal, and attribute column order varies between runs. Any of those changes the bytes without changing the feature, and a naive hash reports a 100% change rate. This page is the normalisation procedure, extending incremental conversion and change data capture.

#Quick Reference

#What Has to Be Normalised

Two geometries are equal if they describe the same set of points. Two geometries are identical in bytes only if they also agree on a long list of representational choices that carry no meaning. The gap between those two notions is the entire problem.

Coordinate precision is the biggest source. Any pipeline that reprojects, buffers, or passes geometry through a library that works in a different internal representation will produce coordinates differing in the last few bits. Snapping to the grid the dataset actually stores — the precision reduction step that already exists in a well-built pipeline — removes it entirely, and does so consistently because both runs snap to the same absolute grid.

Ring orientation is next. The same polygon can be stored with its exterior ring clockwise or counter-clockwise, and different tools have different conventions. A canonical orientation makes the choice deterministic.

Starting vertex is the subtle one. A closed ring A→B→C→D→A is the same ring as C→D→A→B→C, and some sources rotate it when re-tessellating. Rotating every ring to start at its lexicographically smallest vertex removes the ambiguity.

Attribute serialisation is the easy one that people still get wrong: sort the field names, render nulls as an explicit sentinel rather than as an omitted key, format numbers with a fixed representation, and encode as UTF-8.

#Implementation

# Requires: shapely>=2.0, geopandas>=1.0, numpy>=1.26  (Python 3.10+)
from __future__ import annotations

import hashlib
import json
import math
from dataclasses import dataclass

import geopandas as gpd
import numpy as np
from shapely import get_coordinates, normalize, set_precision, to_wkb
from shapely.geometry.base import BaseGeometry


@dataclass(frozen=True)
class Fingerprint:
    geometry: str
    attributes: str

    @property
    def combined(self) -> str:
        return hashlib.blake2b(
            f"{self.geometry}:{self.attributes}".encode("ascii"), digest_size=16
        ).hexdigest()


def canonical_geometry(geom: BaseGeometry | None, grid: float) -> bytes:
    """Reduce a geometry to one representation per shape.

    normalize() fixes ring orientation and ring order; set_precision() removes
    projection round-trip noise; the rotation below removes the remaining
    freedom in where a closed ring starts.
    """
    if geom is None or geom.is_empty:
        return b""
    snapped = set_precision(geom, grid_size=grid)
    if snapped is None or snapped.is_empty:
        return b""
    oriented = normalize(snapped)

    coords = get_coordinates(oriented)
    if coords.size:
        # Rotating to the lexicographically smallest vertex makes the starting
        # point deterministic; sources that re-tessellate otherwise rotate it.
        start = int(np.lexsort((coords[:, 1], coords[:, 0]))[0])
        if start:
            rotated = np.roll(coords[:-1], -start, axis=0)
            coords = np.vstack([rotated, rotated[:1]])
    return to_wkb(oriented) + coords.tobytes()


def canonical_attributes(values: dict[str, object]) -> str:
    """Deterministic text for an attribute tuple, nulls made explicit."""
    rendered: dict[str, object] = {}
    for name in sorted(values):
        value = values[name]
        if value is None or (isinstance(value, float) and math.isnan(value)):
            rendered[name] = None                     # one spelling of "absent"
        elif isinstance(value, float):
            rendered[name] = f"{value:.12g}"          # stable float formatting
        else:
            rendered[name] = str(value)
    return json.dumps(rendered, sort_keys=True, ensure_ascii=False, separators=(",", ":"))


def fingerprint_frame(
    frame: gpd.GeoDataFrame,
    key_column: str,
    *,
    grid: float,
    attributes: tuple[str, ...],
) -> dict[str, Fingerprint]:
    """Two digests per feature: geometry and attributes, kept separate."""
    if key_column not in frame.columns:
        raise KeyError(f"key column {key_column!r} missing")
    if frame[key_column].duplicated().any():
        raise ValueError("duplicate feature keys — the key is not stable")

    out: dict[str, Fingerprint] = {}
    for row in frame.itertuples(index=False):
        record = row._asdict()
        geom_bytes = canonical_geometry(record[frame.geometry.name], grid)
        attr_text = canonical_attributes({k: record.get(k) for k in attributes})
        out[str(record[key_column])] = Fingerprint(
            geometry=hashlib.blake2b(geom_bytes, digest_size=16).hexdigest(),
            attributes=hashlib.blake2b(attr_text.encode("utf-8"), digest_size=16).hexdigest(),
        )
    return out

#Validation

The single most valuable check is an alarm on the change rate. A detector that has silently degraded reports an implausible number, and that number is easy to test against.

# Requires: the module above — refuse to proceed on an implausible change rate
PLAUSIBLE_MAX = 0.20        # 20% of features changing in one run is suspicious

current = fingerprint_frame(today, "uprn", grid=0.01, attributes=ATTRS)
previous = load_manifest("s3://bucket/parcels/_manifests/v000041.json")

changed = {k for k, fp in current.items()
           if k in previous and previous[k]["combined"] != fp.combined}
rate = len(changed) / max(len(current), 1)

if rate > PLAUSIBLE_MAX:
    raise RuntimeError(
        f"{rate:.1%} of features changed — normalisation has probably regressed. "
        f"Compare a sample of canonical forms across the two runs before rerunning."
    )
print(f"{len(changed):,} changed ({rate:.2%}) — within the plausible band")

Expected ranges: a mature address or parcel estate changes 0.1–1% of features per day; a live utility network 1–3%; a survey layer under active field capture up to 5%. Anything above 20% is either a genuine bulk update, which someone will know about, or a normalisation regression.

#Edge Cases and Caveats

Hashing before snapping. Applying the digest to raw source coordinates and snapping afterwards defeats the whole exercise, because the noise the snap would have removed is already baked into the hash. Order matters: snap, canonicalise, then hash.

Narrow hash outputs. A 32-bit checksum over ten million features has a better-than-even chance of at least one collision, and a collision means a genuinely changed feature is reported unchanged and never rewritten. Use at least 128 bits; the storage cost in the manifest is negligible next to a silently stale feature.

Attributes that legitimately change every run. A last_exported_at timestamp or a row sequence number will differ on every export and mark every feature changed. Exclude such fields from the fingerprint explicitly and list the exclusions in the manifest, so the choice is visible when someone later wonders why a real change was missed.

#Frequently Asked Questions

Why does my change detector report that every feature changed?

Almost always because the fingerprint is not normalised. A source that exports rings clockwise this week and counter-clockwise next week, or starts each ring at a different vertex, or round-trips coordinates through a projection library producing sixteenth-decimal differences, produces different bytes for identical features. Normalise geometry to a canonical form and attributes to a fixed field order before hashing, and the rate drops to the real change rate.

Should the fingerprint cover attributes as well as geometry?

Yes, but consider keeping them as two digests rather than one. A combined digest tells you a feature changed; separate geometry and attribute digests tell you which, and that distinction drives real decisions — an attribute-only change may not require re-tiling or re-indexing, while a geometry change does. The extra sixteen bytes per feature in the manifest is a small price for that.

Which hash function should I use?

Any fast non-cryptographic or modern cryptographic digest with a wide output — BLAKE2 at 128 bits is a good default. The property you need is collision resistance across tens of millions of features, which 128 bits provides with an enormous margin. Avoid 32-bit checksums such as CRC32: at ten million features the birthday bound makes accidental collisions likely, and a collision means a changed feature is silently reported as unchanged.

#Related

• Incremental Conversion and Change Data Capture — parent guide: where the fingerprint fits in the run
• Partition Overwrite vs Append for Spatial Tables — what the pipeline does with the change set
• Coordinate Precision Reduction for Smaller GeoParquet — the snapping step the digest depends on
• Handling Null Values in Spatial Schema Mapping — why nulls need one explicit spelling

← Back to Incremental Conversion and Change Data Capture