FAILURE MAP
← Case archive

FA-70681 / GIS polygon topology / Open access

Shapefile part rings assembled into polygons: smallest containing exterior · case 01

Holes in islands inside lakes are attached to the outer mainland ring.

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

ROOT CAUSE

Each hole is attached to the first exterior that contains it.

VERIFIED REPAIR

At the smallest containing exterior step restore `and (best is None or abs(a2(rings[o])) < abs(a2(rings[best])))`, leaving the rest of the model unchanged.

Unsuccessful approach: Choosing the largest containing exterior repeats the error for nested islands.

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:
                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 #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]]])], [('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]]]), ('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 #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 #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, 3]], [2, []]][[0, [1]], [2, [3]]]Failed
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 / 0242479df31ba7a88cafae6f832cea989ef22e4bc888f7529a3f707e352b357e

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(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 #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]]])], [('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]]]), ('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 #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 #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, 3]], [2, []]][[0, [1]], [2, [3]]]Failed
regression #3[[0, []], [2, [1, 3]]][[0, [1]], [2, [3]]]Failed
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 / a2a6ccc6b669dbce3467111d22544b52fe30d9ecf8129d084d6cb1abdeca0980

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 #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]]])], [('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]]]), ('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 #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 #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 / 9a8c26b80f778b36d9c30f0999733848b664d607a7d57d197524ff3af4952019

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

Case digest / c66d2e23e7b4d4db46acd4b83f4a59cf3d1bd7d3f42bde532166be509805de6c