FAILURE MAP
← Case archive

FA-70666 / GIS polygon topology / Open access

Coverage gap and overlap areas: extent clipping · case 01

Gaps and overlaps outside the study area are reported.

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

ROOT CAUSE

Cells outside the extent are not skipped.

VERIFIED REPAIR

At the extent clipping step restore `if x0 < extent[0] or x1 > extent[2] or y0 < extent[1] or y1 > extent[3]:`, leaving the rest of the model unchanged.

Unsuccessful approach: Only cells beyond the x extent are skipped.

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 False:
                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]), ('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 #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]), ('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]), ('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 #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('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]), ('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]), ('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])], [('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 #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]), ('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])], [('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('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[93, 4][84, 4]Failed
control #2[84, 0][84, 0]Passed
control #3[119, 4][91, 4]Failed
control #4[110, 0][94, 0]Failed
control #5[80, 0][80, 0]Passed
control #6[77, 3][72, 2]Failed
control #7[67, 5][52, 3]Failed

SHA-256 / 2866e76a20a67495d991662123979a09f0c9c2099624c169e50ecf419c27ce16

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]:
                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]), ('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 #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]), ('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]), ('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 #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('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]), ('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]), ('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])], [('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 #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]), ('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])], [('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('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[93, 4][84, 4]Failed
control #2[84, 0][84, 0]Passed
control #3[119, 4][91, 4]Failed
control #4[110, 0][94, 0]Failed
control #5[80, 0][80, 0]Passed
control #6[72, 2][72, 2]Passed
control #7[60, 5][52, 3]Failed

SHA-256 / 5a86a364d3b7f5fe456378b023612dd628b59e5e441ce8de36952924b421bd25

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]), ('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 #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]), ('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]), ('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 #11', [[[4, 5, 8, 10], [3, 3, 5, 8], [7, 0, 8, 3]], [0, 0, 10, 10]], [70, 3])], [('control #4', [[[1, 7, 3, 12]], [0, 0, 10, 10]], [94, 0]), ('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]), ('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]), ('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])], [('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 #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]), ('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])], [('control #7', [[[4, 7, 9, 12], [8, 7, 11, 12], [2, 1, 8, 6]], [0, 0, 10, 10]], [52, 3]), ('control #10', [[[4, 6, 8, 12], [8, 5, 14, 8], [4, 5, 6, 9], [8, 2, 14, 6]], [0, 0, 10, 10]], [70, 8]), ('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
control #6[72, 2][72, 2]Passed
control #7[52, 3][52, 3]Passed

SHA-256 / c9d94303c756cc9f8fb9c40d386f83a3aad82c4aafce2f17580781dbe62c90bc

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

Case digest / 418ca780428bb9d89d0dcf4a0fc69f6ccc4232905f8f066ce15ecc09afc6dda8