FAILURE MAP
← Case archive

FA-70416 / GIS polygon topology / Open access

DE-9IM matrix named predicate evaluation: touches alternatives · case 01

Geometries that meet only boundary-to-boundary are not reported as touching.

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

ROOT CAUSE

The boundary/boundary alternative F***T**** is missing from touches.

VERIFIED REPAIR

At the touches alternatives step restore `(match('FT*******') or match('F**T*****') or match('F***T****'))`, leaving the rest of the model unchanged.

Unsuccessful approach: The patched version restores boundary/boundary but drops the boundary/interior alternative F**T*****.

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*****'))
    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 #6', ['212101212', 'touches', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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 #94', ['FF1F00212', 'touches', 1, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('control #3', ['FF2F11212', 'touches', 2, 2], True), ('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), ('control #15', ['212FF1FF2', 'disjoint', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)]]
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 #3FalseTrueFailed
control #4TrueTruePassed
control #5FalseFalsePassed
control #6FalseFalsePassed
regression #119TrueTruePassed

SHA-256 / 4cd8364aa412a850947af9cb497692879b9cfb59ef2c7973bc2f769c5bed588e

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****'))
    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 #6', ['212101212', 'touches', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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 #94', ['FF1F00212', 'touches', 1, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('control #3', ['FF2F11212', 'touches', 2, 2], True), ('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), ('control #15', ['212FF1FF2', 'disjoint', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)]]
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 #6FalseFalsePassed
regression #119FalseTrueFailed

SHA-256 / 3e1d66b2f5dc8d67abc4c2689868033d8f14910ac5c896871fd9a64bafe75d66

3 / The verified repair

Exit 0
"""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 #6', ['212101212', 'touches', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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 #94', ['FF1F00212', 'touches', 1, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('control #3', ['FF2F11212', 'touches', 2, 2], True), ('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), ('control #15', ['212FF1FF2', 'disjoint', 2, 2], False), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)], [('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), ('regression #92', ['FF2F11212', 'touches', 2, 2], True), ('regression #119', ['FF21F1212', 'touches', 2, 1], True)]]
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 #6FalseFalsePassed
regression #119TrueTruePassed

SHA-256 / 94073d7df999d134449add08cc01fdb69c5d508e91f5cc122044c78799f44e06

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.531286+00:00.

Case digest / c80392116a7763993db214f18b73b215242dc261677b2509624f84bca43fe887