FAILURE MAP
← Case archive

FA-70671 / GIS polygon topology / Open access

Coverage gap and overlap areas: extent breakpoints · case 01

Uncovered strips along the extent edge are missing from the gap total.

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

ROOT CAUSE

The extent edges are not used as y breakpoints, so cells straddling or beyond the covered rows vanish.

VERIFIED REPAIR

At the extent breakpoints step restore `ys = sorted({v for q in rects for v in (q[1], q[3])} | {extent[1], extent[3]})`, leaving the rest of the model unchanged.

Unsuccessful approach: Only the lower extent edge is added as a breakpoint.

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])})
    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 #6', [[[8, 8, 11, 10], [0, 0, 3, 2], [6, 5, 11, 9], [5, 1, 6, 5]], [0, 0, 10, 10]], [72, 2]), ('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])], [('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]), ('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])], [('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]), ('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 #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 #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 #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[28, 0][88, 0]Failed
control #1[35, 4][84, 4]Failed
control #2[44, 0][84, 0]Failed
control #3[14, 4][91, 4]Failed
control #4[0, 0][94, 0]Failed
control #6[72, 2][72, 2]Passed
control #11[70, 3][70, 3]Passed
regression #12[0, 0][0, 0]Passed

SHA-256 / a180ccf93cc733110c6ef72673e8cdbdb110e1ec15a24172ab249195ca3b1fdb

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]})
    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 #6', [[[8, 8, 11, 10], [0, 0, 3, 2], [6, 5, 11, 9], [5, 1, 6, 5]], [0, 0, 10, 10]], [72, 2]), ('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])], [('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]), ('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])], [('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]), ('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 #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 #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 #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[68, 0][88, 0]Failed
control #1[75, 4][84, 4]Failed
control #2[64, 0][84, 0]Failed
control #3[84, 4][91, 4]Failed
control #4[70, 0][94, 0]Failed
control #6[72, 2][72, 2]Passed
control #11[70, 3][70, 3]Passed
regression #12[0, 0][0, 0]Passed

SHA-256 / 963003d48a00edfc0d77bbf34507842b917148135dbc6dbca096eed5a5dff4c8

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

SHA-256 / fe5118ff67c4a779c901f923cddef7ad550f16b1452d9973af4f9f8b5981f3cc

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

Case digest / 7d8251aa95371d827d66a566312e884e24da60d1e36cab7a6dbb91b10cf07da2