File size: 4,366 Bytes
6cb442b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | """Validate a packing of n unit squares (possibly rotated) in the container [0, side]^2.
Exact mode: side and every coordinate are Fraction/int and each direction (c, s)
satisfies c^2 + s^2 == 1 exactly (axis-aligned, or Pythagorean like 3/5, 4/5).
Then the verdict is a proof (eps = 0, no tolerance).
Float mode: verdict means "valid within eps"; NOT a proof. Worst violations are reported.
"""
from __future__ import annotations
from dataclasses import dataclass
from fractions import Fraction
import math
Num = object # Fraction | int | float
@dataclass(frozen=True)
class Sq:
x: Num # center x
y: Num # center y
c: Num # cos(rotation)
s: Num # sin(rotation)
def _is_exact(v) -> bool:
return isinstance(v, (Fraction, int)) and not isinstance(v, bool)
def _radius(u, q: Sq):
"""Half-extent of unit square q (edge dirs (c,s), (-s,c)) projected on unit axis u."""
ux, uy = u
return (abs(ux * q.c + uy * q.s) + abs(-ux * q.s + uy * q.c)) / 2
def penetration(a: Sq, b: Sq):
"""Min overlap depth over the 4 separating axes. >0: interiors overlap; <=0: apart/touching."""
dx, dy = b.x - a.x, b.y - a.y
axes = ((a.c, a.s), (-a.s, a.c), (b.c, b.s), (-b.s, b.c))
return min(_radius(u, a) + _radius(u, b) - abs(dx * u[0] + dy * u[1]) for u in axes)
def outside_amount(q: Sq, side):
"""How far q sticks out of [0, side]^2. <= 0 means inside."""
h = (abs(q.c) + abs(q.s)) / 2
return max(h - q.x, q.x + h - side, h - q.y, q.y + h - side)
def validate(squares, side, eps=None, expected_n=None, max_report=10):
n = len(squares)
exact = _is_exact(side) and all(_is_exact(v) for q in squares for v in (q.x, q.y, q.c, q.s))
if exact: # normalise ints to Fraction so all arithmetic stays rational
side = Fraction(side)
squares = [Sq(*(Fraction(v) for v in (q.x, q.y, q.c, q.s))) for q in squares]
if eps is None:
eps = Fraction(0) if exact else 1e-9
one = Fraction(1) if exact else 1.0
unit_tol = 0 if exact else 1e-9
bad, issues = 0, []
def flag(msg):
nonlocal bad
bad += 1
if len(issues) < max_report:
issues.append(msg)
if expected_n is not None and n != expected_n:
flag(f"expected {expected_n} squares, got {n}")
for i, q in enumerate(squares):
if abs(q.c * q.c + q.s * q.s - one) > unit_tol:
flag(f"square {i}: (c, s) is not a unit vector")
max_outside = 0
for i, q in enumerate(squares):
o = outside_amount(q, side)
if o > eps:
flag(f"square {i}: outside container by {float(o):.3e}")
max_outside = max(max_outside, o)
max_overlap = 0
order = sorted(range(n), key=lambda i: squares[i].x)
for pos, i in enumerate(order):
a = squares[i]
for j in order[pos + 1:]:
b = squares[j]
dx = b.x - a.x # >= 0 by sort
if dx * dx > 2: # circumradius sqrt(2)/2 each -> no overlap possible for rest
break
dy = b.y - a.y
if dx * dx + dy * dy > 2:
continue
p = penetration(a, b)
if p > eps:
flag(f"squares {i},{j}: overlap depth {float(p):.3e}")
max_overlap = max(max_overlap, p)
return {"valid": bad == 0, "mode": "exact" if exact else f"float(eps={eps})",
"proof": exact and bad == 0, "n": n, "max_overlap": float(max_overlap),
"max_outside": float(max_outside), "violations": bad, "issues": issues}
def parse_squares(items):
"""items: list of dicts, one form for all squares.
Exact: {"x","y","c","s"} as ints/strings like "3/5".
Float: {"x","y","theta_rad"} or {"x","y","theta_deg"} (unit must be explicit; we never guess)."""
if not items:
return []
if all("c" in d and "s" in d for d in items):
return [Sq(*(Fraction(str(d[k])) for k in ("x", "y", "c", "s"))) for d in items]
for key, conv in (("theta_rad", float), ("theta_deg", lambda v: math.radians(float(v)))):
if all(key in d for d in items):
out = []
for d in items:
t = conv(d[key])
out.append(Sq(float(d["x"]), float(d["y"]), math.cos(t), math.sin(t)))
return out
raise ValueError("use c/s, theta_rad, or theta_deg consistently for all squares")
|