FA-70541 / GIS polygon topology / Open access

Hole placement validation against shell and siblings: shell contact allowance · case 01

Holes that touch the shell at a vertex are rejected as outside.

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

ROOT CAUSE

A hole vertex lying on the shell boundary is treated as outside.

VERIFIED REPAIR

At the shell contact allowance step restore `if any(cls(p, shell) < 0 for p in vs):`, leaving the rest of the model unchanged.

Unsuccessful approach: Requiring every vertex to be outside-or-on lets holes that poke through the shell pass.

Case contract

Input [shell, holes], closed integer rings. Point classification against a ring: on an edge = 0, inside by half-open crossing number = 1, else -1. For each hole in order: "outside" if any hole vertex is strictly outside the shell; else "coincident" if every hole vertex lies on the shell boundary; else "nested" if for some OTHER hole all its vertices are inside-or-on that hole and at least one is strictly inside; else "ok". Return one label per hole.

Why this case matters

Polygon validity rules require holes to lie inside the shell and not inside each other; mislabelled holes block valid data or let invalid parcels through.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    shell, holes = x
    def cls(pt, ring):
        px, py = pt
        for a, b in zip(ring, ring[1:]):
            if (b[0] - a[0]) * (py - a[1]) - (b[1] - a[1]) * (px - a[0]) == 0 and min(a[0], b[0]) <= px <= max(a[0], b[0]) and min(a[1], b[1]) <= py <= max(a[1], b[1]):
                return 0
        c = False
        for a, b in zip(ring, ring[1:]):
            if (a[1] > py) != (b[1] > py) and px < a[0] + (py - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return 1 if c else -1
    out = []
    for i, h in enumerate(holes):
        vs = h[:-1]
        if any(cls(p, shell) <= 0 for p in vs):
            out.append('outside')
            continue
        if all(cls(p, shell) == 0 for p in vs):
            out.append('coincident')
            continue
        nested = False
        for j, g in enumerate(holes):
            if j != i and all(cls(p, g) >= 0 for p in vs) and any(cls(p, g) > 0 for p in vs):
                nested = True
        out.append('nested' if nested else 'ok')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['ok']), ('control #1', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]], [[8, 8], [8, 12], [12, 12], [12, 8], [8, 8]]]], ['ok', 'ok']), ('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok'])], [('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident'])], [('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok'])], [('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside'])], [('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside']), ('boundary #17', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 6], [6, 6], [6, 2], [2, 2]], [[6, 2], [6, 6], [10, 6], [10, 2], [6, 2]]]], ['ok', 'ok']), ('control #18', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], []], []), ('regression #19', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [5, 10], [10, 10], [10, 5], [5, 5]], [[5, 5], [5, 8], [8, 8], [8, 5], [5, 5]]]], ['ok', 'nested'])]]
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 fixture	Actual	Expected	Outcome
control #0	`['ok']`	`['ok']`	Passed
control #1	`['ok', 'ok']`	`['ok', 'ok']`	Passed
regression #2	`['outside']`	`['ok']`	Failed
regression #3	`['outside']`	`['outside']`	Passed
regression #4	`['outside']`	`['outside']`	Passed
regression #5	`['outside']`	`['outside']`	Passed
regression #6	`['ok', 'nested']`	`['ok', 'nested']`	Passed
regression #7	`['nested', 'ok', 'ok']`	`['nested', 'ok', 'ok']`	Passed

SHA-256 / 1ee3c11ea717017b726c0fd5425ee6174284b3aff2a41482e673565e628da08c

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    shell, holes = x
    def cls(pt, ring):
        px, py = pt
        for a, b in zip(ring, ring[1:]):
            if (b[0] - a[0]) * (py - a[1]) - (b[1] - a[1]) * (px - a[0]) == 0 and min(a[0], b[0]) <= px <= max(a[0], b[0]) and min(a[1], b[1]) <= py <= max(a[1], b[1]):
                return 0
        c = False
        for a, b in zip(ring, ring[1:]):
            if (a[1] > py) != (b[1] > py) and px < a[0] + (py - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return 1 if c else -1
    out = []
    for i, h in enumerate(holes):
        vs = h[:-1]
        if all(cls(p, shell) <= 0 for p in vs):
            out.append('outside')
            continue
        if all(cls(p, shell) == 0 for p in vs):
            out.append('coincident')
            continue
        nested = False
        for j, g in enumerate(holes):
            if j != i and all(cls(p, g) >= 0 for p in vs) and any(cls(p, g) > 0 for p in vs):
                nested = True
        out.append('nested' if nested else 'ok')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['ok']), ('control #1', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]], [[8, 8], [8, 12], [12, 12], [12, 8], [8, 8]]]], ['ok', 'ok']), ('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok'])], [('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident'])], [('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok'])], [('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside'])], [('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside']), ('boundary #17', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 6], [6, 6], [6, 2], [2, 2]], [[6, 2], [6, 6], [10, 6], [10, 2], [6, 2]]]], ['ok', 'ok']), ('control #18', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], []], []), ('regression #19', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [5, 10], [10, 10], [10, 5], [5, 5]], [[5, 5], [5, 8], [8, 8], [8, 5], [5, 5]]]], ['ok', 'nested'])]]
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 fixture	Actual	Expected	Outcome
control #0	`['ok']`	`['ok']`	Passed
control #1	`['ok', 'ok']`	`['ok', 'ok']`	Passed
regression #2	`['ok']`	`['ok']`	Passed
regression #3	`['ok']`	`['outside']`	Failed
regression #4	`['ok']`	`['outside']`	Failed
regression #5	`['ok']`	`['outside']`	Failed
regression #6	`['ok', 'nested']`	`['ok', 'nested']`	Passed
regression #7	`['nested', 'ok', 'ok']`	`['nested', 'ok', 'ok']`	Passed

SHA-256 / 3d305e33a8936aa7af706c699e00e979b71340f78d8afc1f4da66bf545dbc0e5

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    shell, holes = x
    def cls(pt, ring):
        px, py = pt
        for a, b in zip(ring, ring[1:]):
            if (b[0] - a[0]) * (py - a[1]) - (b[1] - a[1]) * (px - a[0]) == 0 and min(a[0], b[0]) <= px <= max(a[0], b[0]) and min(a[1], b[1]) <= py <= max(a[1], b[1]):
                return 0
        c = False
        for a, b in zip(ring, ring[1:]):
            if (a[1] > py) != (b[1] > py) and px < a[0] + (py - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):
                c = not c
        return 1 if c else -1
    out = []
    for i, h in enumerate(holes):
        vs = h[:-1]
        if any(cls(p, shell) < 0 for p in vs):
            out.append('outside')
            continue
        if all(cls(p, shell) == 0 for p in vs):
            out.append('coincident')
            continue
        nested = False
        for j, g in enumerate(holes):
            if j != i and all(cls(p, g) >= 0 for p in vs) and any(cls(p, g) > 0 for p in vs):
                nested = True
        out.append('nested' if nested else 'ok')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['ok']), ('control #1', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]], [[8, 8], [8, 12], [12, 12], [12, 8], [8, 8]]]], ['ok', 'ok']), ('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok'])], [('regression #3', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[18, 18], [18, 25], [25, 25], [25, 18], [18, 18]]]], ['outside']), ('regression #4', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [30, 10], [5, 15], [5, 5]]]], ['outside']), ('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #6', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]]]], ['ok', 'nested']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident'])], [('regression #5', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[25, 10], [10, 5], [10, 15], [25, 10]]]], ['outside']), ('regression #7', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[4, 4], [4, 6], [6, 6], [6, 4], [4, 4]], [[2, 2], [2, 12], [12, 12], [12, 2], [2, 2]], [[14, 2], [14, 5], [18, 5], [18, 2], [14, 2]]]], ['nested', 'ok', 'ok']), ('regression #8', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[6, 6], [6, 12], [12, 12], [12, 6], [6, 6]]]], ['ok', 'ok']), ('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok'])], [('boundary #9', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]], [[2, 2], [2, 8], [8, 8], [8, 2], [2, 2]]]], ['ok', 'ok']), ('boundary #10', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [0, 20], [20, 20], [20, 0], [0, 0]]]], ['coincident']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('boundary #12', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 3], [3, 5], [0, 0]]]], ['ok']), ('regression #13', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[22, 2], [22, 5], [25, 5], [25, 2], [22, 2]], [[2, 2], [2, 5], [5, 5], [5, 2], [2, 2]]]], ['outside', 'ok']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside'])], [('regression #2', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 5], [0, 9], [4, 9], [4, 5], [0, 5]]]], ['ok']), ('boundary #11', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[0, 0], [5, 0], [0, 5], [0, 0]]]], ['coincident']), ('regression #14', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[-5, 2], [-5, 5], [3, 5], [3, 2], [-5, 2]], [[5, 5], [5, 9], [9, 9], [9, 5], [5, 5]], [[6, 6], [6, 7], [7, 7], [7, 6], [6, 6]]]], ['outside', 'ok', 'nested']), ('control #15', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 8], [8, 4]]]], ['ok']), ('regression #16', [[[0, 0], [20, 0], [10, 20], [0, 0]], [[[8, 4], [12, 4], [10, 25], [8, 4]]]], ['outside']), ('boundary #17', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[2, 2], [2, 6], [6, 6], [6, 2], [2, 2]], [[6, 2], [6, 6], [10, 6], [10, 2], [6, 2]]]], ['ok', 'ok']), ('control #18', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], []], []), ('regression #19', [[[0, 0], [20, 0], [20, 20], [0, 20], [0, 0]], [[[5, 5], [5, 10], [10, 10], [10, 5], [5, 5]], [[5, 5], [5, 8], [8, 8], [8, 5], [5, 5]]]], ['ok', 'nested'])]]
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 fixture	Actual	Expected	Outcome
control #0	`['ok']`	`['ok']`	Passed
control #1	`['ok', 'ok']`	`['ok', 'ok']`	Passed
regression #2	`['ok']`	`['ok']`	Passed
regression #3	`['outside']`	`['outside']`	Passed
regression #4	`['outside']`	`['outside']`	Passed
regression #5	`['outside']`	`['outside']`	Passed
regression #6	`['ok', 'nested']`	`['ok', 'nested']`	Passed
regression #7	`['nested', 'ok', 'ok']`	`['nested', 'ok', 'ok']`	Passed

SHA-256 / 5a243fa4f682fe0d391d165c6fbccafc8b437c170209e464c422845ae49905e5

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

Case digest / f387bae8531ec17b62d3e1fc37e147703d18410e82462cbd7b2b9a75ad9db749