FAILURE MAP
← Case archive

FA-70676 / GIS polygon topology / Open access

Shapefile part rings assembled into polygons: exterior winding convention · case 01

Every shapefile polygon comes out inside-out.

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

ROOT CAUSE

The GeoJSON convention (counter-clockwise exterior) is applied to shapefile parts.

VERIFIED REPAIR

At the exterior winding convention step restore `outers = [i for i, r in enumerate(rings) if a2(r) < 0] holes = [i for i, r in enumerate(rings) if a2(r) > 0]`, leaving the rest of the model unchanged.

Unsuccessful approach: Zero-area rings are now treated as holes and promoted to exteriors.

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 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, []]])], [('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 #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 #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 #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, []]]), ('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]]]), ('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 #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, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('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 #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]]])]]
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]]]Failed
control #1[[0, []], [1, []], [2, []], [3, []]][[0, [3]], [1, [2]]]Failed
regression #2[[0, []], [1, [2]], [3, []]][[0, [1]], [2, [3]]]Failed
regression #3[[1, []], [2, []], [3, [0]]][[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 / 86dcb498fe789ecf3d1494ae6992788f4ddbdef720be5c13f6a1a04712fd9039

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

SHA-256 / 38de0735f1b74b9a3c6a2e11cfb7993f8d8503c20027cffa6c5ffd0a71957b70

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, []]])], [('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 #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 #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 #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, []]]), ('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]]]), ('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 #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, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('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 #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]]])]]
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 / 37e9d0725ec83335c69915e84f83e77bd272a9ed40f7f1a7217d31f75a78cc1d

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

Case digest / e556521e79f49d4e684550ffbb12788b8b821f05c36b50017fdc27bc79415004