FA-70426 / GIS polygon topology / Open access

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

Lines that meet at a single crossing point are reported as overlapping.

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

ROOT CAUSE

Line/line overlaps use the area pattern, whose T accepts a 0-dimensional interior intersection.

THE FAILURE

Line/line overlaps use the area pattern, whose T accepts a 0-dimensional interior intersection.

Unsuccessful approach: Applying the line pattern to points requires a 1-dimensional intersection that points can never have.

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 da != db:
            return False
        return match('T*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 #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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), ('regression #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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), ('regression #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 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 #112	`True`	`True`	Passed
regression #115	`True`	`False`	Failed

SHA-256 / 28fc5697d6fc12ecbb4e72a9a728cf25f180f8baae808955fcf43b247f3e5aa8

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), ('regression #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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), ('regression #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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), ('regression #112', ['0F0FFF0F2', 'overlaps', 0, 0], True), ('regression #115', ['0F1FF0102', 'overlaps', 1, 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 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 #112	`False`	`True`	Failed
regression #115	`False`	`False`	Passed

SHA-256 / 78b1eef14beb3cdcbd254fa0408e94e7bf50727a39709a31721b32e80a9dff0a

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.

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

Case digest / e3f1ccfb1dd65e1df191bface14661b60939b73edae77e6dcdad8bc1bb812bf3