FA-87426 / Collision detection broadphase / Open access

SAH build splits along the shorter centroid extent · case 01

Long thin scenes are cut across their narrow side and both children overlap heavily.

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

ROOT CAUSE

The axis test is inverted (ex <= ey picks x).

VERIFIED REPAIR

Split the axis with the larger centroid extent.

Unsuccessful approach: Breaking ties toward y changes the axis for square centroid distributions.

Case contract

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

Why this case matters

Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prims):
    n = len(prims)
    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]
    ex = max(c[0] for c in cent) - min(c[0] for c in cent)
    ey = max(c[1] for c in cent) - min(c[1] for c in cent)
    axis = 0 if ex <= ey else 1
    order = sorted(range(n), key=lambda i: (cent[i][axis], i))
    def box(ids):
        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]
    def perim(b):
        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))
    pa = perim(box(order))
    best_k, best = 0, float(n)
    for k in range(1, n):
        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa
        if cost < best:
            best_k, best = k, cost
    return [best_k, axis, round(best, 6), sorted(order[:best_k])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[1, 4, 3, 5], [1, 2, 2, 7], [4, 1, 7, 7], [1, 2, 8, 6], [10, 6, 16, 8], [9, 3, 10, 9], [8, 2, 13, 3]]], [4, 0, 5.217391, [0, 1, 2, 3]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[1, 1, 6, 2], [8, 9, 12, 15], [9, 8, 13, 13]]], [1, 1, 2.153846, [0]]], [[[[2, 3, 3, 7], [4, 8, 10, 11]]], [1, 0, 1.875, [0]]], [[[[8, 3, 12, 6], [8, 6, 14, 7], [4, 7, 9, 10], [9, 7, 15, 13]]], [2, 0, 3.761905, [0, 2]]], [[[[4, 4, 7, 7], [9, 6, 16, 13]]], [1, 0, 1.952381, [0]]], [[[[9, 9, 12, 15], [0, 6, 2, 11], [4, 9, 6, 12], [2, 0, 7, 6], [9, 9, 12, 11], [3, 6, 8, 12], [6, 2, 12, 3]]], [4, 0, 6.074074, [1, 2, 3, 5]]], [[[[5, 2, 12, 5], [5, 1, 9, 2], [1, 0, 5, 2], [8, 6, 15, 10], [7, 0, 12, 6], [3, 2, 6, 6], [2, 6, 7, 13]]], [3, 0, 6.074074, [2, 5, 6]]]], [[[[[1, 1, 3, 6], [7, 9, 8, 16], [6, 2, 13, 3], [9, 8, 14, 15]]], [2, 1, 3.285714, [0, 2]]], [[[[6, 4, 9, 8], [2, 6, 8, 10], [9, 5, 12, 6], [4, 8, 7, 14], [6, 7, 10, 12]]], [2, 0, 4.5, [1, 3]]], [[[[2, 5, 9, 9], [9, 2, 10, 7], [2, 0, 7, 7], [4, 5, 6, 12]]], [0, 0, 4.0, []]], [[[[7, 1, 10, 2], [10, 4, 17, 9], [10, 5, 13, 6]]], [1, 0, 2.555556, [0]]], [[[[9, 0, 14, 7], [7, 3, 10, 9], [0, 4, 5, 10], [9, 5, 16, 12], [7, 7, 8, 10]]], [3, 0, 4.178571, [1, 2, 4]]], [[[[4, 0, 10, 7], [5, 1, 6, 3]]], [0, 0, 2.0, []]], [[[[10, 9, 13, 15], [8, 0, 14, 6], [10, 3, 11, 7]]], [2, 1, 2.666667, [1, 2]]], [[[[5, 6, 6, 11], [5, 5, 10, 8]]], [0, 0, 2.0, []]]], [[[[[8, 8, 10, 10], [8, 4, 14, 10], [5, 10, 9, 13], [0, 4, 1, 8], [8, 6, 10, 7]]], [2, 0, 4.130435, [2, 3]]], [[[[8, 9, 13, 14], [0, 9, 7, 15], [5, 4, 10, 10], [6, 2, 10, 8], [3, 10, 10, 13], [2, 8, 9, 12], [5, 6, 12, 11]]], [3, 0, 6.038462, [1, 4, 5]]], [[[[2, 3, 9, 7], [8, 2, 10, 6], [10, 6, 17, 12], [3, 4, 6, 6], [9, 0, 12, 2], [4, 8, 9, 9]]], [4, 0, 4.703704, [0, 1, 3, 5]]], [[[[4, 1, 6, 4], [5, 3, 12, 10], [8, 2, 10, 6]]], [0, 0, 3.0, []]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[3, 10, 10, 11], [3, 1, 7, 4], [10, 6, 12, 7], [3, 7, 9, 9], [6, 7, 7, 12]]], [2, 1, 4.3, [1, 2]]], [[[[7, 7, 11, 10], [6, 5, 9, 9]]], [0, 0, 2.0, []]], [[[[7, 10, 9, 13], [10, 2, 11, 3], [0, 1, 1, 2], [8, 2, 10, 5], [0, 10, 4, 11]]], [2, 0, 4.173913, [2, 4]]]], [[[[[1, 7, 8, 11], [0, 0, 1, 2], [7, 2, 12, 9], [5, 7, 6, 12], [6, 8, 12, 12]]], [1, 0, 4.625, [1]]], [[[[9, 0, 12, 5], [1, 5, 2, 6], [4, 5, 10, 12], [6, 2, 12, 5], [4, 8, 10, 15]]], [3, 0, 4.038462, [1, 2, 4]]], [[[[10, 0, 16, 1], [1, 7, 8, 10], [3, 5, 5, 10], [6, 8, 13, 9], [5, 9, 10, 10]]], [4, 0, 4.0, [1, 2, 3, 4]]], [[[[3, 6, 5, 8], [10, 0, 11, 1], [5, 1, 11, 8]]], [0, 0, 3.0, []]], [[[[0, 5, 5, 10], [4, 4, 10, 11], [9, 7, 14, 9]]], [2, 0, 2.952381, [0, 1]]], [[[[4, 0, 7, 3], [5, 8, 12, 12], [2, 1, 5, 4], [8, 0, 14, 7], [2, 10, 9, 11]]], [3, 1, 4.541667, [0, 2, 3]]], [[[[10, 0, 13, 3], [0, 1, 2, 8], [2, 3, 3, 6]]], [2, 0, 2.238095, [1, 2]]], [[[[0, 6, 3, 11], [6, 8, 8, 9], [2, 6, 6, 13], [1, 4, 5, 5], [6, 4, 11, 5], [1, 6, 4, 9], [7, 1, 11, 3]]], [4, 0, 5.304348, [0, 2, 3, 5]]]], [[[[[4, 0, 11, 7], [3, 0, 5, 1], [6, 4, 12, 8], [3, 1, 10, 2], [8, 5, 11, 7], [5, 3, 7, 5]]], [4, 0, 5.705882, [0, 1, 3, 5]]], [[[[1, 4, 3, 5], [1, 5, 4, 11], [9, 9, 10, 12], [0, 7, 7, 10], [3, 10, 6, 14]]], [3, 0, 4.3, [0, 1, 3]]], [[[[10, 2, 16, 3], [7, 8, 11, 15], [9, 1, 13, 5], [5, 0, 9, 4], [0, 10, 3, 17]]], [3, 0, 4.212121, [1, 3, 4]]], [[[[2, 5, 6, 10], [5, 4, 7, 5]]], [0, 1, 2.0, []]], [[[[3, 4, 10, 7], [3, 6, 8, 10], [10, 9, 14, 13], [0, 9, 2, 10], [6, 9, 8, 16], [4, 0, 10, 5]]], [3, 0, 5.2, [0, 1, 3]]], [[[[3, 9, 8, 12], [5, 8, 6, 13]]], [0, 0, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[0, 5, 4, 8], [0, 2, 2, 7], [3, 0, 8, 1], [9, 9, 16, 15], [7, 3, 11, 4]]], [4, 0, 3.870968, [0, 1, 2, 4]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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
case 0	`[5, 1, 6.043478, [0, 1, 2, 3, 6]]`	`[4, 0, 5.217391, [0, 1, 2, 3]]`	Failed
case 1	`[2, 0, 4.461538, [2, 4]]`	`[2, 0, 4.461538, [2, 4]]`	Passed
case 2	`[1, 0, 2.153846, [0]]`	`[1, 1, 2.153846, [0]]`	Failed
case 3	`[1, 0, 1.875, [0]]`	`[1, 0, 1.875, [0]]`	Passed
case 4	`[2, 0, 3.761905, [0, 2]]`	`[2, 0, 3.761905, [0, 2]]`	Passed
case 5	`[1, 1, 1.952381, [0]]`	`[1, 0, 1.952381, [0]]`	Failed
case 6	`[4, 0, 6.074074, [1, 2, 3, 5]]`	`[4, 0, 6.074074, [1, 2, 3, 5]]`	Passed
case 7	`[3, 0, 6.074074, [2, 5, 6]]`	`[3, 0, 6.074074, [2, 5, 6]]`	Passed

SHA-256 / 820a82f6b92845824f8e72db4750e8de23c433302c6dcb0ec74baff689c7fec6

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prims):
    n = len(prims)
    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]
    ex = max(c[0] for c in cent) - min(c[0] for c in cent)
    ey = max(c[1] for c in cent) - min(c[1] for c in cent)
    axis = 0 if ex > ey else 1
    order = sorted(range(n), key=lambda i: (cent[i][axis], i))
    def box(ids):
        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]
    def perim(b):
        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))
    pa = perim(box(order))
    best_k, best = 0, float(n)
    for k in range(1, n):
        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa
        if cost < best:
            best_k, best = k, cost
    return [best_k, axis, round(best, 6), sorted(order[:best_k])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[1, 4, 3, 5], [1, 2, 2, 7], [4, 1, 7, 7], [1, 2, 8, 6], [10, 6, 16, 8], [9, 3, 10, 9], [8, 2, 13, 3]]], [4, 0, 5.217391, [0, 1, 2, 3]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[1, 1, 6, 2], [8, 9, 12, 15], [9, 8, 13, 13]]], [1, 1, 2.153846, [0]]], [[[[2, 3, 3, 7], [4, 8, 10, 11]]], [1, 0, 1.875, [0]]], [[[[8, 3, 12, 6], [8, 6, 14, 7], [4, 7, 9, 10], [9, 7, 15, 13]]], [2, 0, 3.761905, [0, 2]]], [[[[4, 4, 7, 7], [9, 6, 16, 13]]], [1, 0, 1.952381, [0]]], [[[[9, 9, 12, 15], [0, 6, 2, 11], [4, 9, 6, 12], [2, 0, 7, 6], [9, 9, 12, 11], [3, 6, 8, 12], [6, 2, 12, 3]]], [4, 0, 6.074074, [1, 2, 3, 5]]], [[[[5, 2, 12, 5], [5, 1, 9, 2], [1, 0, 5, 2], [8, 6, 15, 10], [7, 0, 12, 6], [3, 2, 6, 6], [2, 6, 7, 13]]], [3, 0, 6.074074, [2, 5, 6]]]], [[[[[1, 1, 3, 6], [7, 9, 8, 16], [6, 2, 13, 3], [9, 8, 14, 15]]], [2, 1, 3.285714, [0, 2]]], [[[[6, 4, 9, 8], [2, 6, 8, 10], [9, 5, 12, 6], [4, 8, 7, 14], [6, 7, 10, 12]]], [2, 0, 4.5, [1, 3]]], [[[[2, 5, 9, 9], [9, 2, 10, 7], [2, 0, 7, 7], [4, 5, 6, 12]]], [0, 0, 4.0, []]], [[[[7, 1, 10, 2], [10, 4, 17, 9], [10, 5, 13, 6]]], [1, 0, 2.555556, [0]]], [[[[9, 0, 14, 7], [7, 3, 10, 9], [0, 4, 5, 10], [9, 5, 16, 12], [7, 7, 8, 10]]], [3, 0, 4.178571, [1, 2, 4]]], [[[[4, 0, 10, 7], [5, 1, 6, 3]]], [0, 0, 2.0, []]], [[[[10, 9, 13, 15], [8, 0, 14, 6], [10, 3, 11, 7]]], [2, 1, 2.666667, [1, 2]]], [[[[5, 6, 6, 11], [5, 5, 10, 8]]], [0, 0, 2.0, []]]], [[[[[8, 8, 10, 10], [8, 4, 14, 10], [5, 10, 9, 13], [0, 4, 1, 8], [8, 6, 10, 7]]], [2, 0, 4.130435, [2, 3]]], [[[[8, 9, 13, 14], [0, 9, 7, 15], [5, 4, 10, 10], [6, 2, 10, 8], [3, 10, 10, 13], [2, 8, 9, 12], [5, 6, 12, 11]]], [3, 0, 6.038462, [1, 4, 5]]], [[[[2, 3, 9, 7], [8, 2, 10, 6], [10, 6, 17, 12], [3, 4, 6, 6], [9, 0, 12, 2], [4, 8, 9, 9]]], [4, 0, 4.703704, [0, 1, 3, 5]]], [[[[4, 1, 6, 4], [5, 3, 12, 10], [8, 2, 10, 6]]], [0, 0, 3.0, []]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[3, 10, 10, 11], [3, 1, 7, 4], [10, 6, 12, 7], [3, 7, 9, 9], [6, 7, 7, 12]]], [2, 1, 4.3, [1, 2]]], [[[[7, 7, 11, 10], [6, 5, 9, 9]]], [0, 0, 2.0, []]], [[[[7, 10, 9, 13], [10, 2, 11, 3], [0, 1, 1, 2], [8, 2, 10, 5], [0, 10, 4, 11]]], [2, 0, 4.173913, [2, 4]]]], [[[[[1, 7, 8, 11], [0, 0, 1, 2], [7, 2, 12, 9], [5, 7, 6, 12], [6, 8, 12, 12]]], [1, 0, 4.625, [1]]], [[[[9, 0, 12, 5], [1, 5, 2, 6], [4, 5, 10, 12], [6, 2, 12, 5], [4, 8, 10, 15]]], [3, 0, 4.038462, [1, 2, 4]]], [[[[10, 0, 16, 1], [1, 7, 8, 10], [3, 5, 5, 10], [6, 8, 13, 9], [5, 9, 10, 10]]], [4, 0, 4.0, [1, 2, 3, 4]]], [[[[3, 6, 5, 8], [10, 0, 11, 1], [5, 1, 11, 8]]], [0, 0, 3.0, []]], [[[[0, 5, 5, 10], [4, 4, 10, 11], [9, 7, 14, 9]]], [2, 0, 2.952381, [0, 1]]], [[[[4, 0, 7, 3], [5, 8, 12, 12], [2, 1, 5, 4], [8, 0, 14, 7], [2, 10, 9, 11]]], [3, 1, 4.541667, [0, 2, 3]]], [[[[10, 0, 13, 3], [0, 1, 2, 8], [2, 3, 3, 6]]], [2, 0, 2.238095, [1, 2]]], [[[[0, 6, 3, 11], [6, 8, 8, 9], [2, 6, 6, 13], [1, 4, 5, 5], [6, 4, 11, 5], [1, 6, 4, 9], [7, 1, 11, 3]]], [4, 0, 5.304348, [0, 2, 3, 5]]]], [[[[[4, 0, 11, 7], [3, 0, 5, 1], [6, 4, 12, 8], [3, 1, 10, 2], [8, 5, 11, 7], [5, 3, 7, 5]]], [4, 0, 5.705882, [0, 1, 3, 5]]], [[[[1, 4, 3, 5], [1, 5, 4, 11], [9, 9, 10, 12], [0, 7, 7, 10], [3, 10, 6, 14]]], [3, 0, 4.3, [0, 1, 3]]], [[[[10, 2, 16, 3], [7, 8, 11, 15], [9, 1, 13, 5], [5, 0, 9, 4], [0, 10, 3, 17]]], [3, 0, 4.212121, [1, 3, 4]]], [[[[2, 5, 6, 10], [5, 4, 7, 5]]], [0, 1, 2.0, []]], [[[[3, 4, 10, 7], [3, 6, 8, 10], [10, 9, 14, 13], [0, 9, 2, 10], [6, 9, 8, 16], [4, 0, 10, 5]]], [3, 0, 5.2, [0, 1, 3]]], [[[[3, 9, 8, 12], [5, 8, 6, 13]]], [0, 0, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[0, 5, 4, 8], [0, 2, 2, 7], [3, 0, 8, 1], [9, 9, 16, 15], [7, 3, 11, 4]]], [4, 0, 3.870968, [0, 1, 2, 4]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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
case 0	`[4, 0, 5.217391, [0, 1, 2, 3]]`	`[4, 0, 5.217391, [0, 1, 2, 3]]`	Passed
case 1	`[1, 1, 4.461538, [2]]`	`[2, 0, 4.461538, [2, 4]]`	Failed
case 2	`[1, 1, 2.153846, [0]]`	`[1, 1, 2.153846, [0]]`	Passed
case 3	`[1, 1, 1.875, [0]]`	`[1, 0, 1.875, [0]]`	Failed
case 4	`[2, 1, 3.571429, [0, 1]]`	`[2, 0, 3.761905, [0, 2]]`	Failed
case 5	`[1, 0, 1.952381, [0]]`	`[1, 0, 1.952381, [0]]`	Passed
case 6	`[2, 1, 6.074074, [3, 6]]`	`[4, 0, 6.074074, [1, 2, 3, 5]]`	Failed
case 7	`[5, 1, 5.62963, [0, 1, 2, 4, 5]]`	`[3, 0, 6.074074, [2, 5, 6]]`	Failed

SHA-256 / 20aef92adbdb08f3519fb2372be1341fa6153be23a37189675d85955c368c353

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prims):
    n = len(prims)
    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]
    ex = max(c[0] for c in cent) - min(c[0] for c in cent)
    ey = max(c[1] for c in cent) - min(c[1] for c in cent)
    axis = 0 if ex >= ey else 1
    order = sorted(range(n), key=lambda i: (cent[i][axis], i))
    def box(ids):
        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]
    def perim(b):
        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))
    pa = perim(box(order))
    best_k, best = 0, float(n)
    for k in range(1, n):
        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa
        if cost < best:
            best_k, best = k, cost
    return [best_k, axis, round(best, 6), sorted(order[:best_k])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[1, 4, 3, 5], [1, 2, 2, 7], [4, 1, 7, 7], [1, 2, 8, 6], [10, 6, 16, 8], [9, 3, 10, 9], [8, 2, 13, 3]]], [4, 0, 5.217391, [0, 1, 2, 3]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[1, 1, 6, 2], [8, 9, 12, 15], [9, 8, 13, 13]]], [1, 1, 2.153846, [0]]], [[[[2, 3, 3, 7], [4, 8, 10, 11]]], [1, 0, 1.875, [0]]], [[[[8, 3, 12, 6], [8, 6, 14, 7], [4, 7, 9, 10], [9, 7, 15, 13]]], [2, 0, 3.761905, [0, 2]]], [[[[4, 4, 7, 7], [9, 6, 16, 13]]], [1, 0, 1.952381, [0]]], [[[[9, 9, 12, 15], [0, 6, 2, 11], [4, 9, 6, 12], [2, 0, 7, 6], [9, 9, 12, 11], [3, 6, 8, 12], [6, 2, 12, 3]]], [4, 0, 6.074074, [1, 2, 3, 5]]], [[[[5, 2, 12, 5], [5, 1, 9, 2], [1, 0, 5, 2], [8, 6, 15, 10], [7, 0, 12, 6], [3, 2, 6, 6], [2, 6, 7, 13]]], [3, 0, 6.074074, [2, 5, 6]]]], [[[[[1, 1, 3, 6], [7, 9, 8, 16], [6, 2, 13, 3], [9, 8, 14, 15]]], [2, 1, 3.285714, [0, 2]]], [[[[6, 4, 9, 8], [2, 6, 8, 10], [9, 5, 12, 6], [4, 8, 7, 14], [6, 7, 10, 12]]], [2, 0, 4.5, [1, 3]]], [[[[2, 5, 9, 9], [9, 2, 10, 7], [2, 0, 7, 7], [4, 5, 6, 12]]], [0, 0, 4.0, []]], [[[[7, 1, 10, 2], [10, 4, 17, 9], [10, 5, 13, 6]]], [1, 0, 2.555556, [0]]], [[[[9, 0, 14, 7], [7, 3, 10, 9], [0, 4, 5, 10], [9, 5, 16, 12], [7, 7, 8, 10]]], [3, 0, 4.178571, [1, 2, 4]]], [[[[4, 0, 10, 7], [5, 1, 6, 3]]], [0, 0, 2.0, []]], [[[[10, 9, 13, 15], [8, 0, 14, 6], [10, 3, 11, 7]]], [2, 1, 2.666667, [1, 2]]], [[[[5, 6, 6, 11], [5, 5, 10, 8]]], [0, 0, 2.0, []]]], [[[[[8, 8, 10, 10], [8, 4, 14, 10], [5, 10, 9, 13], [0, 4, 1, 8], [8, 6, 10, 7]]], [2, 0, 4.130435, [2, 3]]], [[[[8, 9, 13, 14], [0, 9, 7, 15], [5, 4, 10, 10], [6, 2, 10, 8], [3, 10, 10, 13], [2, 8, 9, 12], [5, 6, 12, 11]]], [3, 0, 6.038462, [1, 4, 5]]], [[[[2, 3, 9, 7], [8, 2, 10, 6], [10, 6, 17, 12], [3, 4, 6, 6], [9, 0, 12, 2], [4, 8, 9, 9]]], [4, 0, 4.703704, [0, 1, 3, 5]]], [[[[4, 1, 6, 4], [5, 3, 12, 10], [8, 2, 10, 6]]], [0, 0, 3.0, []]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[3, 10, 10, 11], [3, 1, 7, 4], [10, 6, 12, 7], [3, 7, 9, 9], [6, 7, 7, 12]]], [2, 1, 4.3, [1, 2]]], [[[[7, 7, 11, 10], [6, 5, 9, 9]]], [0, 0, 2.0, []]], [[[[7, 10, 9, 13], [10, 2, 11, 3], [0, 1, 1, 2], [8, 2, 10, 5], [0, 10, 4, 11]]], [2, 0, 4.173913, [2, 4]]]], [[[[[1, 7, 8, 11], [0, 0, 1, 2], [7, 2, 12, 9], [5, 7, 6, 12], [6, 8, 12, 12]]], [1, 0, 4.625, [1]]], [[[[9, 0, 12, 5], [1, 5, 2, 6], [4, 5, 10, 12], [6, 2, 12, 5], [4, 8, 10, 15]]], [3, 0, 4.038462, [1, 2, 4]]], [[[[10, 0, 16, 1], [1, 7, 8, 10], [3, 5, 5, 10], [6, 8, 13, 9], [5, 9, 10, 10]]], [4, 0, 4.0, [1, 2, 3, 4]]], [[[[3, 6, 5, 8], [10, 0, 11, 1], [5, 1, 11, 8]]], [0, 0, 3.0, []]], [[[[0, 5, 5, 10], [4, 4, 10, 11], [9, 7, 14, 9]]], [2, 0, 2.952381, [0, 1]]], [[[[4, 0, 7, 3], [5, 8, 12, 12], [2, 1, 5, 4], [8, 0, 14, 7], [2, 10, 9, 11]]], [3, 1, 4.541667, [0, 2, 3]]], [[[[10, 0, 13, 3], [0, 1, 2, 8], [2, 3, 3, 6]]], [2, 0, 2.238095, [1, 2]]], [[[[0, 6, 3, 11], [6, 8, 8, 9], [2, 6, 6, 13], [1, 4, 5, 5], [6, 4, 11, 5], [1, 6, 4, 9], [7, 1, 11, 3]]], [4, 0, 5.304348, [0, 2, 3, 5]]]], [[[[[4, 0, 11, 7], [3, 0, 5, 1], [6, 4, 12, 8], [3, 1, 10, 2], [8, 5, 11, 7], [5, 3, 7, 5]]], [4, 0, 5.705882, [0, 1, 3, 5]]], [[[[1, 4, 3, 5], [1, 5, 4, 11], [9, 9, 10, 12], [0, 7, 7, 10], [3, 10, 6, 14]]], [3, 0, 4.3, [0, 1, 3]]], [[[[10, 2, 16, 3], [7, 8, 11, 15], [9, 1, 13, 5], [5, 0, 9, 4], [0, 10, 3, 17]]], [3, 0, 4.212121, [1, 3, 4]]], [[[[2, 5, 6, 10], [5, 4, 7, 5]]], [0, 1, 2.0, []]], [[[[3, 4, 10, 7], [3, 6, 8, 10], [10, 9, 14, 13], [0, 9, 2, 10], [6, 9, 8, 16], [4, 0, 10, 5]]], [3, 0, 5.2, [0, 1, 3]]], [[[[3, 9, 8, 12], [5, 8, 6, 13]]], [0, 0, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[0, 5, 4, 8], [0, 2, 2, 7], [3, 0, 8, 1], [9, 9, 16, 15], [7, 3, 11, 4]]], [4, 0, 3.870968, [0, 1, 2, 4]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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
case 0	`[4, 0, 5.217391, [0, 1, 2, 3]]`	`[4, 0, 5.217391, [0, 1, 2, 3]]`	Passed
case 1	`[2, 0, 4.461538, [2, 4]]`	`[2, 0, 4.461538, [2, 4]]`	Passed
case 2	`[1, 1, 2.153846, [0]]`	`[1, 1, 2.153846, [0]]`	Passed
case 3	`[1, 0, 1.875, [0]]`	`[1, 0, 1.875, [0]]`	Passed
case 4	`[2, 0, 3.761905, [0, 2]]`	`[2, 0, 3.761905, [0, 2]]`	Passed
case 5	`[1, 0, 1.952381, [0]]`	`[1, 0, 1.952381, [0]]`	Passed
case 6	`[4, 0, 6.074074, [1, 2, 3, 5]]`	`[4, 0, 6.074074, [1, 2, 3, 5]]`	Passed
case 7	`[3, 0, 6.074074, [2, 5, 6]]`	`[3, 0, 6.074074, [2, 5, 6]]`	Passed

SHA-256 / d5ad80e749e6c87caf52ce47a3ab12131c78254686b55b91b11203643cbce629

Verification & scope

A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. 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:50:58.600593+00:00.

Case digest / deccf1cf5874de977eb6a01af8547035e92e305e5b5a6499797167d08447fce9