FAILURE MAP
← Case archive

FA-70431 / GIS polygon topology / Open access

DE-9IM matrix named predicate evaluation: overlaps equal dimension guard · case 01

A line lying partly inside a polygon is reported as overlapping it.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

overlaps is evaluated without requiring equal dimensions.

THE FAILURE

overlaps is evaluated without requiring equal dimensions.

Unsuccessful approach: Only the dimA < dimB case is rejected; polygon/line pairs still report overlaps.

Case contract

Input [matrix, predicate, dimA, dimB] with a 9-character intersection matrix over "F012" (row-major II, IB, IE, BI, BB, BE, EI, EB, EE). Pattern characters: "*" anything, "T" any non-F value, "F" only F, "0"/"1"/"2" that exact dimension. disjoint = FF*FF****; intersects = not disjoint; touches (not both points) = FT******* or F**T***** or F***T****; within = T*F**F***; contains = T*****FF*; covers = any of T*****FF*, *T****FF*, ***T**FF*, ****T*FF*; overlaps needs equal dimensions and 1*T***T** for lines else T*T***T**; crosses = T*T****** if dimA < dimB, T*****T** if dimA > dimB, 0******** for two lines, otherwise false; equals = T*F**FFF*. Unknown predicates return None.

Why this case matters

Spatial SQL predicates, topology rules and QA checks are expressed as DE-9IM patterns; a wrong pattern changes join results silently.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    matrix, pred, da, db = x
    def match(pattern):
        for m, p in zip(matrix, pattern):
            if p == '*':
                continue
            if p == 'T' and m == 'F':
                return False
            if p == 'F' and m != 'F':
                return False
            if p in '012' and m != p:
                return False
        return True
    if pred == 'disjoint':
        return match('FF*FF****')
    if pred == 'intersects':
        return not match('FF*FF****')
    if pred == 'touches':
        return (da, db) != (0, 0) and (match('FT*******') or match('F**T*****') or match('F***T****'))
    if pred == 'within':
        return match('T*F**F***')
    if pred == 'contains':
        return match('T*****FF*')
    if pred == 'covers':
        return any(match(p) for p in ('T*****FF*', '*T****FF*', '***T**FF*', '****T*FF*'))
    if pred == 'overlaps':
        if False:
            return False
        return match('1*T***T**') if da == 1 else match('T*T***T**')
    if pred == 'crosses':
        if da < db:
            return match('T*T******')
        if da > db:
            return match('T*****T**')
        return da == 1 and match('0********')
    if pred == 'equals':
        return match('T*F**FFF*')
    return None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', ['FF2F11212', 'crosses', 2, 2], False), ('control #1', ['FF2F11212', 'intersects', 2, 2], True), ('control #2', ['FF2F11212', 'within', 2, 2], False), ('control #3', ['FF2F11212', 'touches', 2, 2], True), ('control #4', ['212101212', 'overlaps', 2, 2], True), ('control #5', ['212101212', 'crosses', 2, 2], False), ('control #33', ['101FF0212', 'overlaps', 1, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False)], [('control #3', ['FF2F11212', 'touches', 2, 2], True), ('control #4', ['212101212', 'overlaps', 2, 2], True), ('control #5', ['212101212', 'crosses', 2, 2], False), ('control #6', ['212101212', 'touches', 2, 2], False), ('control #7', ['212101212', 'intersects', 2, 2], True), ('control #8', ['2FF1FF212', 'contains', 2, 2], False), ('control #54', ['1010F0212', 'overlaps', 1, 2], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #6', ['212101212', 'touches', 2, 2], False), ('control #7', ['212101212', 'intersects', 2, 2], True), ('control #8', ['2FF1FF212', 'contains', 2, 2], False), ('control #9', ['2FF1FF212', 'crosses', 2, 2], False), ('control #10', ['2FF1FF212', 'intersects', 2, 2], True), ('control #11', ['2FF1FF212', 'disjoint', 2, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #9', ['2FF1FF212', 'crosses', 2, 2], False), ('control #10', ['2FF1FF212', 'intersects', 2, 2], True), ('control #11', ['2FF1FF212', 'disjoint', 2, 2], False), ('control #12', ['212FF1FF2', 'intersects', 2, 2], True), ('control #13', ['212FF1FF2', 'contains', 2, 2], True), ('control #14', ['212FF1FF2', 'covers', 2, 2], True), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #12', ['212FF1FF2', 'intersects', 2, 2], True), ('control #13', ['212FF1FF2', 'contains', 2, 2], True), ('control #14', ['212FF1FF2', 'covers', 2, 2], True), ('control #15', ['212FF1FF2', 'disjoint', 2, 2], False), ('control #16', ['2FF1FF2F2', 'equals', 2, 2], False), ('control #17', ['2FF1FF2F2', 'disjoint', 2, 2], False), ('control #33', ['101FF0212', 'overlaps', 1, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False)]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
control #0FalseFalsePassed
control #1TrueTruePassed
control #2FalseFalsePassed
control #3TrueTruePassed
control #4TrueTruePassed
control #5FalseFalsePassed
control #33TrueFalseFailed
regression #123TrueFalseFailed

SHA-256 / 40a9b1d81cd4ef0eca7382f5b06b19dc19817cbb288516d0579c0b7b1cb477a0

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    matrix, pred, da, db = x
    def match(pattern):
        for m, p in zip(matrix, pattern):
            if p == '*':
                continue
            if p == 'T' and m == 'F':
                return False
            if p == 'F' and m != 'F':
                return False
            if p in '012' and m != p:
                return False
        return True
    if pred == 'disjoint':
        return match('FF*FF****')
    if pred == 'intersects':
        return not match('FF*FF****')
    if pred == 'touches':
        return (da, db) != (0, 0) and (match('FT*******') or match('F**T*****') or match('F***T****'))
    if pred == 'within':
        return match('T*F**F***')
    if pred == 'contains':
        return match('T*****FF*')
    if pred == 'covers':
        return any(match(p) for p in ('T*****FF*', '*T****FF*', '***T**FF*', '****T*FF*'))
    if pred == 'overlaps':
        if da < db:
            return False
        return match('1*T***T**') if da == 1 else match('T*T***T**')
    if pred == 'crosses':
        if da < db:
            return match('T*T******')
        if da > db:
            return match('T*****T**')
        return da == 1 and match('0********')
    if pred == 'equals':
        return match('T*F**FFF*')
    return None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', ['FF2F11212', 'crosses', 2, 2], False), ('control #1', ['FF2F11212', 'intersects', 2, 2], True), ('control #2', ['FF2F11212', 'within', 2, 2], False), ('control #3', ['FF2F11212', 'touches', 2, 2], True), ('control #4', ['212101212', 'overlaps', 2, 2], True), ('control #5', ['212101212', 'crosses', 2, 2], False), ('control #33', ['101FF0212', 'overlaps', 1, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False)], [('control #3', ['FF2F11212', 'touches', 2, 2], True), ('control #4', ['212101212', 'overlaps', 2, 2], True), ('control #5', ['212101212', 'crosses', 2, 2], False), ('control #6', ['212101212', 'touches', 2, 2], False), ('control #7', ['212101212', 'intersects', 2, 2], True), ('control #8', ['2FF1FF212', 'contains', 2, 2], False), ('control #54', ['1010F0212', 'overlaps', 1, 2], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #6', ['212101212', 'touches', 2, 2], False), ('control #7', ['212101212', 'intersects', 2, 2], True), ('control #8', ['2FF1FF212', 'contains', 2, 2], False), ('control #9', ['2FF1FF212', 'crosses', 2, 2], False), ('control #10', ['2FF1FF212', 'intersects', 2, 2], True), ('control #11', ['2FF1FF212', 'disjoint', 2, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #9', ['2FF1FF212', 'crosses', 2, 2], False), ('control #10', ['2FF1FF212', 'intersects', 2, 2], True), ('control #11', ['2FF1FF212', 'disjoint', 2, 2], False), ('control #12', ['212FF1FF2', 'intersects', 2, 2], True), ('control #13', ['212FF1FF2', 'contains', 2, 2], True), ('control #14', ['212FF1FF2', 'covers', 2, 2], True), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False), ('regression #124', ['2121F1212', 'overlaps', 2, 1], False)], [('control #12', ['212FF1FF2', 'intersects', 2, 2], True), ('control #13', ['212FF1FF2', 'contains', 2, 2], True), ('control #14', ['212FF1FF2', 'covers', 2, 2], True), ('control #15', ['212FF1FF2', 'disjoint', 2, 2], False), ('control #16', ['2FF1FF2F2', 'equals', 2, 2], False), ('control #17', ['2FF1FF2F2', 'disjoint', 2, 2], False), ('control #33', ['101FF0212', 'overlaps', 1, 2], False), ('regression #123', ['1020F1102', 'overlaps', 2, 1], False)]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
control #0FalseFalsePassed
control #1TrueTruePassed
control #2FalseFalsePassed
control #3TrueTruePassed
control #4TrueTruePassed
control #5FalseFalsePassed
control #33FalseFalsePassed
regression #123TrueFalseFailed

SHA-256 / 69d15090997a34d922df9b4ffb55f034eb69449b19f8faeaf9dad444b6e3b0a3

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Stipulated deterministic toy contract on a bounded input domain; results are rounded as stated and no conformance with any published standard or library is claimed. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:20.674365+00:00.

Case digest / 6e31d9b9af61d144b38536bc3b70b50b5143cf99d9ca3207da1ee1abfc50bcc1