Merging Overlapping Zone Edits with Shapely

Recover the version both editors branched from, compute each edit’s additions and removals against it, and refuse the merge where one edit’s addition meets the other’s removal — a union cannot express removal, so it silently restores the area an editor deliberately trimmed and produces a zone neither of them made.

This guide sits under Conflict Resolution Strategies, within Idempotency & Spatial Deduplication. It is the resolution step invoked when Implementing a Version Vector for Spatial Features classifies two edits as concurrent.

When to use this pattern

  • Two concurrent edits to the same polygon have been detected, and discarding one is not acceptable.
  • The common ancestor is available, which means the pipeline stored it deliberately.
  • The zone is a coverage area, a service region or a delivery boundary — something where the union of two extensions is meaningful. It is not appropriate for parcels, where an overlap is a legal dispute.

Union loses the removals

The union puts back what somebody deliberately took out A service zone is shown as the ancestor both editors loaded. Editor A extends it northwards to cover a new district. Editor B, working independently, trims the southern edge because the service no longer reaches an industrial estate down there. Taking the union of A's result and B's result produces a zone that has A's northern extension and also has the southern estate back, because a union can only ever add area. B's removal has not merely been lost — it has been reversed, and the resulting zone claims coverage the operator specifically decided not to offer. A three-way merge against the ancestor sees the additions and the removals separately: A added the north, B removed the south, the two regions do not touch, so the merged zone is the ancestor plus the north minus the south. That result is what both editors would have produced had they worked in sequence, and it is derivable only because the ancestor was kept. one service zone · two independent edits ancestor A: extend north B: trim south union(A, B) — wrong three-way merge removed estate is back north added, south gone A union can only add area, so it cannot represent a decision to remove one B's trim is not lost, it is reversed: the merged zone claims coverage the operator specifically decided not to offer, and it will keep claiming it until someone notices. The three-way result is what the two editors would have produced working in sequence, and it is derivable only because the ancestor was stored deliberately.
Figure 1. Without the ancestor, A's addition and B's removal are both just "a difference between two shapes", and nothing can tell them apart.

Complete runnable implementation

python 
from dataclasses import dataclass

from shapely.geometry import mapping, shape
from shapely.ops import unary_union
from shapely.validation import make_valid

# Slivers below this area are artefacts of coordinate precision rather than
# real disagreements, and must not trigger a refusal. Square degrees at
# EPSG:4326; ~1e-12 is under a square metre at mid-latitudes.
SLIVER_AREA = 1e-12


class MergeConflict(Exception):
    """Both edits made a deliberate, opposite decision about the same ground."""

    def __init__(self, overlap_area: float, region) -> None:
        super().__init__(f"contested area {overlap_area:.3e} sq deg")
        self.region = region


@dataclass(frozen=True, slots=True)
class Delta:
    added: object      # shapely geometry: in the edit, not in the ancestor
    removed: object    # in the ancestor, not in the edit


def delta(ancestor, edited) -> Delta:
    """What one edit did, expressed as an addition and a removal."""
    return Delta(added=edited.difference(ancestor),
                 removed=ancestor.difference(edited))


def three_way_merge(ancestor_geojson: dict, a_geojson: dict,
                    b_geojson: dict) -> dict:
    """Merge two concurrent zone edits against their common ancestor.

    Raises MergeConflict when one edit added ground the other removed —
    the geometric equivalent of two people editing the same line.
    """
    ancestor = make_valid(shape(ancestor_geojson))
    a, b = make_valid(shape(a_geojson)), make_valid(shape(b_geojson))

    da, db = delta(ancestor, a), delta(ancestor, b)

    # A added what B removed, or the reverse: both made a decision about the
    # same ground and they disagree. Any automatic answer is a guess.
    contested = unary_union([
        da.added.intersection(db.removed),
        db.added.intersection(da.removed),
    ])
    if not contested.is_empty and contested.area > SLIVER_AREA:
        raise MergeConflict(contested.area, mapping(contested))

    merged = unary_union([ancestor, da.added, db.added])
    merged = merged.difference(unary_union([da.removed, db.removed]))

    # Boolean operations on real-world polygons routinely produce slivers and
    # self-touching rings; repair before anything downstream validates it.
    merged = make_valid(merged)
    merged = merged.buffer(0)

    if merged.is_empty:
        raise MergeConflict(0.0, mapping(ancestor))

    return mapping(merged)

The order matters: additions are applied before removals, so an area that one editor added and neither removed survives, while an area removed by either is gone regardless of who added it. Reversing the order lets an addition resurrect a removal, which is the union bug in a subtler form.

Disjoint changes merge; overlapping decisions do not Two cases are compared. In the first, editor A's addition sits in the north of the zone and editor B's removal sits in the south. The two changed regions do not intersect, so each edit's intent can be honoured in full and the merge is not a compromise but a faithful combination — this is the common case, because two people editing the same zone usually care about different parts of it. In the second, A extends the zone east across a boundary while B removes the very same strip, having decided the service does not reach it. The changed regions overlap almost entirely. There is no combination that honours both intents, because the intents are contradictory: one says this ground is covered and the other says it is not. A merge function that returns any geometry here has picked a winner without saying so, which is exactly the silent behaviour the version vector was introduced to eliminate. Raising instead pushes the decision to whoever has authority over that area, and carries the contested region in the exception so a reviewer can see precisely what is in dispute. disjoint changes — merge faithfully A added B removed the changed regions do not intersect, so both intents are honoured in full the common case — two people editing one zone usually care about different parts overlapping decisions — refuse A added B removed the same strip contradictory intents no combination honours both A merge that returns a geometry here has picked a winner without saying so — which is the silent behaviour the version vector existed to eliminate. Raising pushes the decision to whoever has authority over that ground, and carrying the contested region in the exception lets a reviewer see exactly what is in dispute.
Figure 2. The refusal is the feature. Detecting concurrency and then quietly resolving it geometrically would put the original problem back one layer down.

Parameter reference

Name Type Spatial constraint Default
SLIVER_AREA float Square degrees; below a square metre at mid-latitudes 1e-12
Ancestor GeoJSON The version both editors loaded; must be stored deliberately —
make_valid call On all three inputs — an invalid input makes every predicate unreliable —
buffer(0) call After the booleans, to clean self-touching rings —
Operation order — Additions then removals; reversing resurrects removed area —
MergeConflict.region GeoJSON The contested ground, for a reviewer to look at —

Gotchas and spatial edge cases

  1. A tolerance in square degrees is not a tolerance in square metres. At 60° north a degree of longitude is half its equatorial length, so the same SLIVER_AREA represents half the ground. If the threshold is contractual rather than cosmetic, reproject to a local equal-area CRS before measuring, as CRS Normalization Strategies describes.

  2. difference between polygons with nearly-coincident edges produces slivers. Two editors who both traced the same boundary by hand will differ by microdegrees, and every shared edge becomes a thread of area in the delta. Without the sliver threshold, every merge of hand-drawn geometry reports a conflict.

  3. make_valid can change the geometry type. An invalid polygon may come back as a GeometryCollection containing polygons and stray lines, and unary_union on that keeps the lines. Filter to polygonal parts before returning, or a zero-area line ends up in the stored zone and breaks the next area calculation.

  4. A merge that empties the zone is a conflict, not a result. If both editors removed most of the area, the intersection of what remains can be empty, and storing an empty geometry deletes the zone by arithmetic. Raising is the only safe response.

  5. This merge is for coverage areas, not for parcels. Cadastral boundaries have legal meaning and an overlap between two of them is a dispute to be recorded, not a shape to be computed. Applying a geometric merge there produces a parcel that no register recognises.

  6. The merged geometry needs a new version vector that dominates both inputs. Producing the shape without recording the merged lineage means the next edit rediscovers the same conflict — the failure the last test in the version-vector guide exists to catch.

Two people tracing the same line never trace the same line Two editors both adjust a zone that shares a long boundary with a neighbouring one, and both trace that shared boundary by hand. Their traces differ by microdegrees — a fraction of a millimetre on the ground — so the difference between each edit and the ancestor contains a thread of area running the whole length of the shared edge. Without a sliver threshold, that thread intersects the other edit's removal somewhere along its length, the contested area is non-empty, and the merge refuses. Since hand-traced boundaries are the normal case rather than an exotic one, a merge with no tolerance refuses almost every real conflict and the mechanism is abandoned. With a threshold below any area a person could intend, the threads are ignored and only a genuine disagreement — an area both editors made a deliberate, opposite decision about — triggers the refusal. The threshold is therefore not a fudge factor but the line between a coordinate artefact and an intent. two hand traces of one shared boundary editor A's trace editor B's trace the gap between them is microdegrees — a fraction of a millimetre on the ground no sliver threshold the thread is non-empty, so the merge refuses refuses almost every real conflict · the mechanism is abandoned threshold below any area a person could intend threads ignored · only a deliberate disagreement refuses not a fudge factor — the line between an artefact and an intent
Figure 3. Every boundary operation on hand-digitised data produces these threads, which is why the threshold belongs in the merge rather than in a cleanup pass afterwards.

Verification

python 
import pytest
from shapely.geometry import Polygon, mapping, shape

ANCESTOR = mapping(Polygon([(0, 0), (0, 10), (10, 10), (10, 0)]))


def extended_north() -> dict:
    return mapping(Polygon([(0, 0), (0, 14), (10, 14), (10, 0)]))


def trimmed_south() -> dict:
    return mapping(Polygon([(0, 3), (0, 10), (10, 10), (10, 3)]))


def test_disjoint_changes_merge_faithfully():
    """North added, south removed — both intents survive."""
    merged = shape(three_way_merge(ANCESTOR, extended_north(), trimmed_south()))
    assert merged.bounds == (0.0, 3.0, 10.0, 14.0)


def test_union_would_have_restored_the_trimmed_area():
    """The bug this function exists to avoid, asserted explicitly."""
    naive = shape(extended_north()).union(shape(trimmed_south()))
    assert naive.bounds[1] == 0.0, "union keeps the removed southern strip"

    merged = shape(three_way_merge(ANCESTOR, extended_north(), trimmed_south()))
    assert merged.bounds[1] == 3.0


def test_contradictory_edits_refuse():
    """A added the eastern strip; B removed it."""
    a = mapping(Polygon([(0, 0), (0, 10), (14, 10), (14, 0)]))
    b = mapping(Polygon([(0, 0), (0, 10), (8, 10), (8, 0)]))
    with pytest.raises(MergeConflict):
        three_way_merge(ANCESTOR, a, b)


def test_hand_drawn_slivers_do_not_refuse():
    """Microdegree differences along a shared edge are not a conflict."""
    a = mapping(Polygon([(0, 0), (0, 10.0000001), (10, 10), (10, 0)]))
    b = mapping(Polygon([(0, 0), (0, 9.9999999), (10, 10), (10, 0)]))
    three_way_merge(ANCESTOR, a, b)      # must not raise

The second test is worth keeping even though it asserts something about code that is not being used: it documents the failure mode in executable form, so anyone tempted to replace the function with a one-line union sees immediately what that costs.