Resolving Topology Errors During Branch Merges

Isolate conflicting spatial features, apply deterministic geometry repair rules, and validate against a shared topology schema before committing — that is the core sequence for clean spatial branch merges. Part of the broader work covered in automated conflict detection in merge requests, topology resolution is the step that standard Git merge algorithms skip entirely.

Concept & Context

Geospatial versioning introduces topology errors when parallel branches modify shared boundaries, snap vertices differently, or apply conflicting coordinate transformations. Unlike line-based text merges, spatial data has no granular diffing at the vertex level, so overlapping edits to adjacent parcels, road networks, or hydrological catchments frequently produce invalid geometries. The broader branching and merge strategies for spatial datasets framework reduces collision frequency through disciplined branching conventions, but automated topology validation remains mandatory as a final gate.

When two contributors edit the same spatial extent, floating-point precision differences compound during merge operations. A vertex recorded as (151.20541, -33.87142) in one branch and (151.20540, -33.87143) in another creates a sliver polygon at the shared boundary — invisible in most GIS editors but fatal to spatial joins, area calculations, and routing algorithms. Spatial merges also fail when branches use different digitization scales or when coordinate rounding truncates shared boundary vertices. Teams relying on spatial diff algorithms for polygon data to detect changes must resolve these micro-drifts before any diff result can be trusted.

Core Algorithmic Pipeline

The topology resolution pipeline follows five deterministic steps. Order matters: repairing individual geometries before snapping prevents snap from operating on already-broken inputs, and validating after snapping catches cases where snapping itself introduces new violations.

Topology resolution pipeline Five sequential steps: CRS normalise, make_valid repair, sjoin conflict detect, tolerance snap, is_valid gate 1. CRS Normalise 2. make_valid Repair 3. sjoin Conflict Detection 4. Tolerance Snap 5. is_valid Gate

Step 1 — CRS normalisation. Reproject the incoming branch GeoDataFrame to match the target CRS before any spatial operation. Merging across mismatched coordinate reference systems introduces silent coordinate drift that no downstream repair step can recover.

Step 2 — Individual geometry repair. Apply Shapely’s make_valid to every geometry in the branch layer. This resolves self-intersections, duplicate vertices, and ring orientation issues per the OGC Simple Features specification. It operates on single geometries in isolation and does not fix topological relationships between features — that is the job of the snapping step.

Step 3 — Spatial conflict detection. Use a geopandas.sjoin with predicate="intersects" backed by an STRtree spatial index to identify which branch features overlap target boundary features. Limiting the repair to only conflicting features prevents unnecessary geometry modification to non-conflicting parts of the layer.

Step 4 — Tolerance-based vertex snapping. Call shapely.ops.snap(branch_geom, target_union, tolerance) on each conflicting feature. The tolerance must be calibrated to your CRS units: 0.001 decimal degrees is roughly 111 m at the equator — almost certainly too coarse for cadastral work. For a projected CRS in metres, 0.01 suits survey-grade data; 1.0 is a reasonable upper bound for regional environmental datasets.

Step 5 — Fail-fast validation gate. Run is_valid on every feature in the repaired branch layer. If any geometry fails, call explain_validity to record the exact violation type (e.g., "Self-intersection[151.205, -33.871]") and block the merge. A non-zero residual error count must not be allowed into the main branch.

Working Implementation

import geopandas as gpd
from shapely.validation import make_valid, explain_validity
from shapely.ops import snap
from shapely import STRtree
import logging

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")


def resolve_topology_errors(
    branch_gdf: gpd.GeoDataFrame,
    target_gdf: gpd.GeoDataFrame,
    tolerance: float = 0.001,
) -> tuple[gpd.GeoDataFrame, bool]:
    """
    Detect and repair topology errors in branch_gdf relative to target_gdf.

    Returns the repaired GeoDataFrame and True if all geometries are valid,
    or the partially-repaired GeoDataFrame and False if residual errors remain.
    Residual errors must block the merge in the calling workflow.
    """
    # Step 1: Normalise CRS — must happen before any spatial operation
    if branch_gdf.crs != target_gdf.crs:
        logging.info("CRS mismatch detected. Reprojecting branch to target CRS.")
        branch_gdf = branch_gdf.to_crs(target_gdf.crs)

    # Step 2: Repair individual geometries with make_valid
    branch_gdf = branch_gdf.copy()
    branch_gdf["geometry"] = branch_gdf["geometry"].apply(
        lambda g: make_valid(g) if g is not None and not g.is_valid else g
    )

    # Step 3: Detect spatial conflicts using an STRtree spatial index
    # Build index on target; query returns candidate indices for each branch bbox
    target_geoms = list(target_gdf.geometry)
    tree = STRtree(target_geoms)

    conflict_branch_indices = set()
    local_targets: dict[int, list] = {}

    for i, branch_geom in enumerate(branch_gdf.geometry):
        if branch_geom is None:
            continue
        candidate_indices = tree.query(branch_geom, predicate="intersects")
        if len(candidate_indices) > 0:
            conflict_branch_indices.add(i)
            # Store the local target subset for localised snapping
            local_targets[i] = [target_geoms[j] for j in candidate_indices]

    if conflict_branch_indices:
        logging.warning(
            f"Detected {len(conflict_branch_indices)} branch features "
            f"intersecting target boundaries. Applying tolerance snap."
        )

    # Step 4: Tolerance-based snapping — only on conflicting features
    for i in conflict_branch_indices:
        branch_geom = branch_gdf.geometry.iloc[i]
        if branch_geom is None:
            continue
        # Snap to a local unary_union of only the nearby target features
        local_union = local_targets[i][0]
        for t in local_targets[i][1:]:
            local_union = local_union.union(t)
        snapped = snap(branch_geom, local_union, tolerance)
        branch_gdf.iloc[i, branch_gdf.columns.get_loc("geometry")] = snapped

    # Step 5: Fail-fast validation gate
    invalid_mask = ~branch_gdf["geometry"].is_valid
    if invalid_mask.any():
        invalid_count = int(invalid_mask.sum())
        logging.error(
            f"Merge blocked: {invalid_count} geometries remain invalid after repair."
        )
        for idx in branch_gdf.index[invalid_mask]:
            geom = branch_gdf.loc[idx, "geometry"]
            logging.debug(f"  Feature {idx}: {explain_validity(geom)}")
        return branch_gdf, False

    logging.info(
        f"Topology validation passed ({len(branch_gdf)} features). "
        "Branch is safe to merge."
    )
    return branch_gdf, True

Key design choices in this implementation:

  • Local unary_union over a global one. The original single-call target_gdf.geometry.unary_union dissolves the entire target layer into one geometry object before snapping. On layers with hundreds of thousands of features that operation is both memory-expensive and CPU-bound. Limiting the union to candidates returned by the STRtree query keeps each snap call fast and proportional to local complexity.
  • branch_gdf.copy() before mutation. Never modify the caller’s dataframe in place. Returning a new object allows the caller to compare before/after states for audit logging.
  • iloc assignment for geometry. Setting geometry with .iloc via the column position index sidesteps the SettingWithCopyWarning that loc triggers on geometry columns in some GeoPandas versions.

Validation & Output Verification

After the pipeline runs successfully (returns True), confirm correctness before committing to the main branch:

import json

def audit_merge_result(
    original_gdf: gpd.GeoDataFrame,
    repaired_gdf: gpd.GeoDataFrame,
    output_path: str,
) -> None:
    """Write repaired layer and emit a JSON audit record."""
    assert repaired_gdf["geometry"].is_valid.all(), "Residual topology errors"
    assert len(repaired_gdf) == len(original_gdf), "Row count changed during repair"

    # Verify no features shifted beyond 10x the snap tolerance (sanity check)
    max_drift = repaired_gdf.geometry.distance(original_gdf.geometry).max()
    print(f"Max geometry drift after repair: {max_drift:.6f} CRS units")

    repaired_gdf.to_file(output_path, driver="GPKG")

    audit = {
        "feature_count": len(repaired_gdf),
        "all_valid": bool(repaired_gdf["geometry"].is_valid.all()),
        "max_drift_crs_units": float(max_drift),
        "output": output_path,
    }
    print(json.dumps(audit, indent=2))

Run these checks in your CI pipeline immediately after resolve_topology_errors returns True:

  1. is_valid assertion — confirms zero residual errors; the pipeline already blocks on this, but an explicit assert in the audit step catches any regression in the pipeline logic.
  2. Row-count assertion — topology repair must never silently drop or duplicate features; a count mismatch indicates a make_valid edge case (e.g., a degenerate polygon collapsing to a line) that needs manual review.
  3. Max drift check — compare repaired geometry positions to originals. A drift significantly above your snap tolerance indicates that snapping moved features beyond the expected correction window, which may require lowering the tolerance or investigating the source of the large offset.

Failure Modes

Symptom: make_valid produces a GeometryCollection instead of a Polygon. Root cause: the input geometry was so severely self-intersecting that the only valid result is a mix of lower-dimensional primitives (lines, points). Fix: detect GeometryCollection outputs with isinstance(g, GeometryCollection) and flag those features for manual review rather than passing them downstream.

Symptom: snap returns a geometry that is still invalid. Root cause: the snap tolerance is larger than the minimum spacing between valid vertices in the target, causing the branch geometry to fold over itself. Fix: halve the tolerance and re-run; if the error persists, the source geometry requires manual digitization correction.

Symptom: Pipeline times out on layers with more than 500 k features. Root cause: unary_union on the full target layer before the STRtree refactor, or sjoin without a spatial index. Fix: ensure the STRtree-based localised snap path is in use; also consider splitting the branch layer into spatial tiles of ~50 k features and processing them in parallel with concurrent.futures.ProcessPoolExecutor.

Symptom: CRS mismatch is reported even though both layers are EPSG:4326. Root cause: one layer has a GEOGRAPHIC_CRS authority string while the other has a WGS 84 authority string — they are geometrically identical but gdf.crs != other_gdf.crs evaluates to True because the CRS objects differ in metadata. Fix: normalise both CRS objects with pyproj.CRS.from_epsg(4326) before comparison, or use branch_gdf.crs.equals(target_gdf.crs) instead of !=.

Back to Branching & Merge Strategies for Spatial Datasets