FAILURE MAP
← Case archive

FA-70656 / GIS polygon topology / Open access

Coverage gap and overlap areas: interior containment · case 01

Rectangles that merely share an edge are reported as overlapping.

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

ROOT CAUSE

Cells are tested by their lower-left corner with closed bounds, so a cell starting on a neighbour edge counts for both.

VERIFIED REPAIR

At the interior containment step restore `if q[0] < cx < q[2] and q[1] < cy < q[3])`, leaving the rest of the model unchanged.

Unsuccessful approach: The x bound is half-open but the y bound is still closed.

Case contract

Input [rects, extent]: axis-aligned integer rectangles [x0, y0, x1, y1] forming a coverage and an extent box. Split the plane on all rectangle and extent edges; for each cell inside the extent count the rectangles whose OPEN interior contains the cell centre. Gap area sums cells with count 0, overlap area sums (once) cells with count >= 2. Parts outside the extent are ignored. Return [gap, overlap].

Why this case matters

Cadastral and zoning coverages must tile the study area exactly; QA reports gaps and overlaps by area.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rects, extent = x
    xs = sorted({v for q in rects for v in (q[0], q[2])} | {extent[0], extent[2]})
    ys = sorted({v for q in rects for v in (q[1], q[3])} | {extent[1], extent[3]})
    gap = overlap = 0
    for i in range(len(xs) - 1):
        for j in range(len(ys) - 1):
            x0, x1, y0, y1 = xs[i], xs[i + 1], ys[j], ys[j + 1]
            if x0 < extent[0] or x1 > extent[2] or y0 < extent[1] or y1 > extent[3]:
                continue
            cx, cy = (x0 + x1) / 2, (y0 + y1) / 2
            n = sum(1 for q in rects if q[0] <= x0 <= q[2] and q[1] <= y0 <= q[3])
            cell = (x1 - x0) * (y1 - y0)
            if n == 0:
                gap += cell
            elif n > 1:
                overlap += cell
    return [gap, overlap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 4, 3, 8]], [0, 0, 10, 10]], [88, 0]), ('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #6', [[[8, 8, 11, 10], [0, 0, 3, 2], [6, 5, 11, 9], [5, 1, 6, 5]], [0, 0, 10, 10]], [72, 2]), ('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('control #9', [[[7, 6, 11, 11], [8, 8, 9, 12], [5, 0, 10, 5], [8, 3, 13, 7]], [0, 0, 10, 10]], [61, 8]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('regression #12', [[[0, 0, 5, 10], [5, 0, 10, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #13', [[[0, 0, 5, 5], [5, 5, 10, 10]], [0, 0, 10, 10]], [50, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('regression #15', [[[-5, 0, 5, 10], [5, 0, 15, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #16', [[[0, -3, 10, 4], [0, 4, 10, 13]], [0, 0, 10, 10]], [0, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #18', [[[2, 2, 4, 4]], [0, 0, 10, 10]], [96, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])]]
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 #0[40, 0][88, 0]Failed
control #1[70, 15][84, 4]Failed
control #2[40, 10][84, 0]Failed
control #3[74, 18][91, 4]Failed
control #4[73, 0][94, 0]Failed
control #5[28, 0][80, 0]Failed
boundary #17[16, 0][16, 0]Passed
regression #19[0, 100][0, 100]Passed

SHA-256 / 397c70181e01af871fb6b168ead52783ef5ad5dc5677d4d65f78defe171b7c13

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rects, extent = x
    xs = sorted({v for q in rects for v in (q[0], q[2])} | {extent[0], extent[2]})
    ys = sorted({v for q in rects for v in (q[1], q[3])} | {extent[1], extent[3]})
    gap = overlap = 0
    for i in range(len(xs) - 1):
        for j in range(len(ys) - 1):
            x0, x1, y0, y1 = xs[i], xs[i + 1], ys[j], ys[j + 1]
            if x0 < extent[0] or x1 > extent[2] or y0 < extent[1] or y1 > extent[3]:
                continue
            cx, cy = (x0 + x1) / 2, (y0 + y1) / 2
            n = sum(1 for q in rects if q[0] <= x0 < q[2] and q[1] <= y0 <= q[3])
            cell = (x1 - x0) * (y1 - y0)
            if n == 0:
                gap += cell
            elif n > 1:
                overlap += cell
    return [gap, overlap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 4, 3, 8]], [0, 0, 10, 10]], [88, 0]), ('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #6', [[[8, 8, 11, 10], [0, 0, 3, 2], [6, 5, 11, 9], [5, 1, 6, 5]], [0, 0, 10, 10]], [72, 2]), ('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('control #9', [[[7, 6, 11, 11], [8, 8, 9, 12], [5, 0, 10, 5], [8, 3, 13, 7]], [0, 0, 10, 10]], [61, 8]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('regression #12', [[[0, 0, 5, 10], [5, 0, 10, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #13', [[[0, 0, 5, 5], [5, 5, 10, 10]], [0, 0, 10, 10]], [50, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('regression #15', [[[-5, 0, 5, 10], [5, 0, 15, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #16', [[[0, -3, 10, 4], [0, 4, 10, 13]], [0, 0, 10, 10]], [0, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #18', [[[2, 2, 4, 4]], [0, 0, 10, 10]], [96, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])]]
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 #0[82, 0][88, 0]Failed
control #1[82, 5][84, 4]Failed
control #2[72, 2][84, 0]Failed
control #3[89, 8][91, 4]Failed
control #4[94, 0][94, 0]Passed
control #5[60, 0][80, 0]Failed
boundary #17[16, 0][16, 0]Passed
regression #19[0, 100][0, 100]Passed

SHA-256 / a81d4dd3974fa4d989f5250906b56eff82cb308b53b1345592b44a1177fd0b2b

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rects, extent = x
    xs = sorted({v for q in rects for v in (q[0], q[2])} | {extent[0], extent[2]})
    ys = sorted({v for q in rects for v in (q[1], q[3])} | {extent[1], extent[3]})
    gap = overlap = 0
    for i in range(len(xs) - 1):
        for j in range(len(ys) - 1):
            x0, x1, y0, y1 = xs[i], xs[i + 1], ys[j], ys[j + 1]
            if x0 < extent[0] or x1 > extent[2] or y0 < extent[1] or y1 > extent[3]:
                continue
            cx, cy = (x0 + x1) / 2, (y0 + y1) / 2
            n = sum(1 for q in rects if q[0] < cx < q[2] and q[1] < cy < q[3])
            cell = (x1 - x0) * (y1 - y0)
            if n == 0:
                gap += cell
            elif n > 1:
                overlap += cell
    return [gap, overlap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 4, 3, 8]], [0, 0, 10, 10]], [88, 0]), ('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #1', [[[5, 5, 6, 11], [5, 4, 8, 9]], [0, 0, 10, 10]], [84, 4]), ('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #6', [[[8, 8, 11, 10], [0, 0, 3, 2], [6, 5, 11, 9], [5, 1, 6, 5]], [0, 0, 10, 10]], [72, 2]), ('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #2', [[[0, 6, 6, 8], [5, 2, 6, 6]], [0, 0, 10, 10]], [84, 0]), ('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #8', [[[0, 8, 3, 10], [7, 4, 10, 8], [7, 3, 10, 8]], [0, 0, 10, 10]], [79, 12]), ('control #9', [[[7, 6, 11, 11], [8, 8, 9, 12], [5, 0, 10, 5], [8, 3, 13, 7]], [0, 0, 10, 10]], [61, 8]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #3', [[[4, 7, 5, 9], [1, 8, 4, 14], [0, 8, 5, 9]], [0, 0, 10, 10]], [91, 4]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('control #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3]), ('regression #12', [[[0, 0, 5, 10], [5, 0, 10, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #13', [[[0, 0, 5, 5], [5, 5, 10, 10]], [0, 0, 10, 10]], [50, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('control #5', [[[1, 2, 6, 6]], [0, 0, 10, 10]], [80, 0]), ('regression #14', [[[0, 0, 6, 10], [4, 0, 10, 10], [3, 3, 7, 7]], [0, 0, 10, 10]], [0, 28]), ('regression #15', [[[-5, 0, 5, 10], [5, 0, 15, 10]], [0, 0, 10, 10]], [0, 0]), ('regression #16', [[[0, -3, 10, 4], [0, 4, 10, 13]], [0, 0, 10, 10]], [0, 0]), ('boundary #17', [[], [0, 0, 4, 4]], [16, 0]), ('regression #18', [[[2, 2, 4, 4]], [0, 0, 10, 10]], [96, 0]), ('regression #19', [[[0, 0, 10, 10], [0, 0, 10, 10], [0, 0, 10, 10]], [0, 0, 10, 10]], [0, 100])]]
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 #0[88, 0][88, 0]Passed
control #1[84, 4][84, 4]Passed
control #2[84, 0][84, 0]Passed
control #3[91, 4][91, 4]Passed
control #4[94, 0][94, 0]Passed
control #5[80, 0][80, 0]Passed
boundary #17[16, 0][16, 0]Passed
regression #19[0, 100][0, 100]Passed

SHA-256 / 5bb922cc96629799eead63d6c342a1d2261d168afc1755f5722d3e8b2b581e12

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

Case digest / 5c4f47d7b640a5ecad54573c133e6bb4679a9829324e304301fb2377f22303d3