FAILURE MAP
← Case archive

FA-70696 / GIS polygon topology / Open access

Shapefile part rings assembled into polygons: output exterior ordering · case 01

Promoted orphan rings appear after all regular exteriors regardless of their index.

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

ROOT CAUSE

Results follow dictionary insertion order (regular exteriors first, then promoted holes).

VERIFIED REPAIR

At the output exterior ordering step restore `for o in sorted(assign)]`, leaving the rest of the model unchanged.

Unsuccessful approach: Sorting only the regular exteriors drops promoted orphan rings from the output.

Case contract

Input: a list of closed integer rings from one shapefile record. Clockwise rings (negative shoelace sum) are exteriors, counter-clockwise rings are holes, zero-area rings are ignored. Each hole joins the SMALLEST-area exterior whose interior contains the hole first vertex (crossing-number test). A hole contained by no exterior is promoted to an exterior of its own. Return [[exterior_index, sorted hole indexes], ...] sorted by exterior index.

Why this case matters

Shapefile readers must rebuild polygon structure from flat part lists; islands in lakes and orphan holes are the classic failure cases.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rings = x
    def a2(r):
        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))
    def inside(pt, r):
        c = False
        for a, b in zip(r, r[1:]):
            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return c
    outers = [i for i, r in enumerate(rings) if a2(r) < 0]
    holes = [i for i, r in enumerate(rings) if a2(r) > 0]
    assign = {i: [] for i in outers}
    for h in holes:
        best = None
        for o in outers:
            if inside(rings[h][0], rings[o]) and (best is None or abs(a2(rings[o])) < abs(a2(rings[best]))):
                best = o
        if best is None:
            assign[h] = []
        else:
            assign[best].append(h)
    return [[o, sorted(assign[o])] for o in assign]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]])], [('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]
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[[0, [1]]][[0, [1]]]Passed
control #1[[0, [3]], [1, [2]]][[0, [3]], [1, [2]]]Passed
regression #2[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #3[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #4[[0, []], [1, []]][[0, []], [1, []]]Passed
regression #5[[1, []], [0, []]][[0, []], [1, []]]Failed
regression #6[[0, []], [1, []]][[0, []], [1, []]]Passed
boundary #7[[0, []]][[0, []]]Passed

SHA-256 / 972d98447f62c8c87b91110c038aec823bb4cce516d31e1c7dd59c11f6dc4089

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rings = x
    def a2(r):
        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))
    def inside(pt, r):
        c = False
        for a, b in zip(r, r[1:]):
            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return c
    outers = [i for i, r in enumerate(rings) if a2(r) < 0]
    holes = [i for i, r in enumerate(rings) if a2(r) > 0]
    assign = {i: [] for i in outers}
    for h in holes:
        best = None
        for o in outers:
            if inside(rings[h][0], rings[o]) and (best is None or abs(a2(rings[o])) < abs(a2(rings[best]))):
                best = o
        if best is None:
            assign[h] = []
        else:
            assign[best].append(h)
    return [[o, sorted(assign[o])] for o in sorted(outers)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]])], [('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]
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[[0, [1]]][[0, [1]]]Passed
control #1[[0, [3]], [1, [2]]][[0, [3]], [1, [2]]]Passed
regression #2[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #3[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #4[[0, []]][[0, []], [1, []]]Failed
regression #5[[1, []]][[0, []], [1, []]]Failed
regression #6[[0, []]][[0, []], [1, []]]Failed
boundary #7[[0, []]][[0, []]]Passed

SHA-256 / 0208a869388b983ebc84130c864b59f06138965258b0e6b32834c01fb4c9ccef

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    rings = x
    def a2(r):
        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))
    def inside(pt, r):
        c = False
        for a, b in zip(r, r[1:]):
            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return c
    outers = [i for i, r in enumerate(rings) if a2(r) < 0]
    holes = [i for i, r in enumerate(rings) if a2(r) > 0]
    assign = {i: [] for i in outers}
    for h in holes:
        best = None
        for o in outers:
            if inside(rings[h][0], rings[o]) and (best is None or abs(a2(rings[o])) < abs(a2(rings[best]))):
                best = o
        if best is None:
            assign[h] = []
        else:
            assign[best].append(h)
    return [[o, sorted(assign[o])] for o in sorted(assign)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]])], [('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]
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[[0, [1]]][[0, [1]]]Passed
control #1[[0, [3]], [1, [2]]][[0, [3]], [1, [2]]]Passed
regression #2[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #3[[0, [1]], [2, [3]]][[0, [1]], [2, [3]]]Passed
regression #4[[0, []], [1, []]][[0, []], [1, []]]Passed
regression #5[[0, []], [1, []]][[0, []], [1, []]]Passed
regression #6[[0, []], [1, []]][[0, []], [1, []]]Passed
boundary #7[[0, []]][[0, []]]Passed

SHA-256 / 18092f8b8d20a8a3ac4bd4a5d4cce51839343913a4d5db2ec5e04ec948c1721d

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

Case digest / 37596bebfe2bec0e142fda404039b32fa49a432f95c5ab48171f6317cd96105b