FA-70421 / GIS polygon topology / Open access

DE-9IM matrix named predicate evaluation: touches point pair exclusion · case 01

Two points are reported as touching.

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

ROOT CAUSE

The rule that touches is undefined for point/point inputs is omitted.

VERIFIED REPAIR

At the touches point pair exclusion step restore `(da, db) != (0, 0) and`, leaving the rest of the model unchanged.

Unsuccessful approach: Rejecting every input with a point first operand also drops valid point/line touches.

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 True 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 fixture	Actual	Expected	Outcome
control #0	`False`	`False`	Passed
control #1	`True`	`True`	Passed
control #2	`False`	`False`	Passed
control #3	`True`	`True`	Passed
control #4	`True`	`True`	Passed
control #5	`False`	`False`	Passed
regression #93	`True`	`True`	Passed
regression #121	`True`	`False`	Failed

SHA-256 / 3e3894b2853b005fa3dc4ad8f03813c4b5506cba3ea299f7f525e3b0030a1979

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 != 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 fixture	Actual	Expected	Outcome
control #0	`False`	`False`	Passed
control #1	`True`	`True`	Passed
control #2	`False`	`False`	Passed
control #3	`True`	`True`	Passed
control #4	`True`	`True`	Passed
control #5	`False`	`False`	Passed
regression #93	`False`	`True`	Failed
regression #121	`False`	`False`	Passed

SHA-256 / 82e3f9c6efbde051672351488ff2cbd1841e0106edd5a1757d3cd4f219d6690b

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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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), ('regression #93', ['F0FFFF102', 'touches', 0, 1], True), ('regression #121', ['F0FFFFFF2', 'touches', 0, 0], 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 fixture	Actual	Expected	Outcome
control #0	`False`	`False`	Passed
control #1	`True`	`True`	Passed
control #2	`False`	`False`	Passed
control #3	`True`	`True`	Passed
control #4	`True`	`True`	Passed
control #5	`False`	`False`	Passed
regression #93	`True`	`True`	Passed
regression #121	`False`	`False`	Passed

SHA-256 / 4a68062e203f2c20fe8dc7aefb90f8fe71161dfd1c7a39f0d8726fff25f1d73e

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

Case digest / c74d0021b636ef235eda4ad42c34a214737bf31295c8a05ada733b0b7c5f7bdb