Verifying Topological Claims with DE-9IM

Named predicates like “contains” and “touches” are convenient and occasionally not what a question means. The nine-intersection matrix underneath them describes exactly how two geometries relate, and reading it directly lets you check a claim against the relation the user actually intended rather than the closest available function name. This guide uses it to verify model assertions, as the exact-checking stage of spatial reasoning and relation inference.

When to Use This Approach

Use the named predicates for ordinary cases and drop to the matrix when a claim falls between them, when the boundary case matters, or when you need to explain to a reader why a claim failed.

The distinction between containing and covering is the one that surfaces most often in practice: a parcel whose edge lies exactly on a district boundary is covered by the district and not contained in it, and a system that reports “not inside” for that case will be told, correctly, that it is wrong.

Implementation

The verifier maps a natural-language claim to an intersection pattern, evaluates it, and returns a three-valued verdict with the matrix so a failure can be explained.

import logging
from dataclasses import dataclass
from typing import Optional

from shapely.geometry.base import BaseGeometry
from shapely.errors import GEOSException
from shapely.validation import make_valid

log = logging.getLogger("topology_verification")

# Patterns describing how the interiors, boundaries and exteriors of two geometries meet.
# "T" means they must intersect, "F" that they must not, "*" that it does not matter.
PATTERNS = {
    "inside":     "T*F**F***",     # strictly within, boundary not touching the outside
    "covered_by": "T*F**F***",     # same test, applied with covers semantics below
    "adjacent":   "F***T****",     # boundaries meet, interiors do not
    "crosses":    "T*T******",
    "overlaps":   "T*T***T**",
}


@dataclass(frozen=True)
class Verdict:
    holds: Optional[bool]          # None means unverifiable, never a guess
    matrix: Optional[str]
    note: str


def _prepare(geom: BaseGeometry) -> Optional[BaseGeometry]:
    if geom is None or geom.is_empty:
        return None
    if geom.is_valid:
        return geom
    try:
        fixed = make_valid(geom)
        return fixed if not fixed.is_empty else None
    except GEOSException as exc:
        log.warning("geometry could not be repaired: %s", exc)
        return None


def verify(subject: BaseGeometry, reference: BaseGeometry, claim: str,
           tolerance_m: float = 0.0, to_metric=None) -> Verdict:
    """Verify one relation claim exactly. Returns None when it cannot be checked."""
    a, b = _prepare(subject), _prepare(reference)
    if a is None or b is None:
        return Verdict(None, None, "one or both geometries are unavailable or unusable")

    if tolerance_m > 0 and to_metric is not None:
        try:
            a = to_metric(a).buffer(tolerance_m)      # tolerance for separately digitised data
            b = to_metric(b)
        except Exception as exc:
            return Verdict(None, None, f"could not apply tolerance: {exc}")

    pattern = PATTERNS.get(claim)
    if pattern is None:
        return Verdict(None, None, f"no intersection pattern defined for claim {claim!r}")

    try:
        matrix = a.relate(b)
        holds = a.relate_pattern(b, pattern)
    except GEOSException as exc:
        return Verdict(None, None, f"relation computation failed: {exc}")

    if claim == "covered_by":
        holds = b.covers(a)                            # boundary-inclusive containment
    return Verdict(holds, matrix, "" if holds else f"matrix {matrix} does not match {pattern}")

Returning the matrix alongside the verdict is what turns a failed check into an explanation. “Not inside” is a bare contradiction; “not inside — the parcel’s boundary meets the district’s boundary, so it is covered rather than contained” is an answer that resolves the disagreement in one sentence.

The tolerance parameter exists because exact adjacency is rare in real data. Two parcels digitised in different surveys will be a few centimetres apart or a few centimetres overlapping, and a strict boundary-touching test reports neighbours as unrelated. Applying a small buffer to one side, in a metric projection, restores the intended meaning — and the tolerance must be reported with the answer, because “adjacent within half a metre” is a materially different claim from “adjacent”.

Validation & Testing

from shapely.geometry import box, Point


def test_edge_touching_parcel_is_covered_not_contained():
    district = box(0, 0, 10, 10)
    parcel = box(0, 2, 4, 6)                       # shares the western edge
    assert verify(parcel, district, "inside").holds is False
    assert verify(parcel, district, "covered_by").holds is True


def test_unusable_geometry_returns_none_not_false():
    v = verify(None, box(0, 0, 1, 1), "inside")
    assert v.holds is None and "unavailable" in v.note


def test_unknown_claim_is_unverifiable_not_false():
    v = verify(box(0, 0, 1, 1), box(0, 0, 2, 2), "upstream_of")
    assert v.holds is None and "no intersection pattern" in v.note


def test_matrix_is_returned_for_a_failed_claim():
    v = verify(Point(20, 20), box(0, 0, 10, 10), "inside")
    assert v.holds is False and v.matrix and len(v.matrix) == 9

The second and third tests are the ones that keep the three-valued contract honest. Every simplification of this function will be tempted to return False for an input it could not evaluate, and that single change converts “we do not know” into “we checked and it is not so” across the entire system.

Gotchas & Edge Cases

Patterns applied to mismatched dimensions. Several relations are only defined between geometries of the same dimension: a point never overlaps a polygon, however much it may sit inside one. Check dimensions before applying a pattern, and report a dimension mismatch as unverifiable rather than false.

Tolerance applied in degrees. Buffering by a value that looks like half a metre but is expressed in degrees produces a buffer of tens of kilometres. Project before buffering, always, and assert the projection in the same test that asserts the tolerance.

Buffering both sides. Applying the tolerance to both geometries doubles it silently. Buffer one side only, and state which.

Invalid geometry silently repaired into a different answer. A self-intersecting polygon repaired by splitting into parts can genuinely change a containment result. Report that a repair occurred alongside the verdict, so a surprising answer can be traced to it.

A claim verified against the wrong reference. The commonest logical error is checking “is the site in the conservation area” against a different conservation area with a similar name. Verification is only as good as the grounding that supplied the reference, which is why place resolution carries identifiers rather than names.

Relations checked in a projected frame with a different origin. Both geometries must be in the same frame before any predicate runs. A mismatch produces a confident answer computed over geometry that is nowhere near each other, and no predicate detects it.

Frequently Asked Questions

One last piece of advice on adoption. Introduce this verifier as a check on answers before introducing it as a source of them: run it silently for a period, log every claim it would have retracted, and read the list. That list is a direct measurement of how often the system currently asserts spatial relations it cannot support, and it is usually more persuasive than any argument for adding the layer.

Related

• Up to the parent topic: Spatial Reasoning and Relation Inference
• Answering Direction and Distance Queries Deterministically
• Related topic: Topology Rule Enforcement via LLMs
• Concept: Geocoding and Place-Name Resolution