seveibar/am3352-ram-dogbone-and-single-layer-route-test

routing/smooth.ts

import {length,segmentDist} from './single-layer'
type P={x:number,y:number};type R={name:string,layer:string,points:P[]}
const clearanceViolation=(a:P,b:P,c:P,d:P,margin:number)=>{
 if(Math.max(a.x,b.x)+margin<Math.min(c.x,d.x)||Math.max(c.x,d.x)+margin<Math.min(a.x,b.x)||Math.max(a.y,b.y)+margin<Math.min(c.y,d.y)||Math.max(c.y,d.y)+margin<Math.min(a.y,b.y))return false
 return segmentDist(a,b,c,d)<margin-1e-6
}
const distance=(a:P,b:P)=>Math.hypot(a.x-b.x,a.y-b.y)
const clean=(ps:P[])=>ps.filter((p,i)=>!i||distance(p,ps[i-1])>1e-8).filter((p,i,a)=>!i||i===a.length-1||((p.x-a[i-1].x)*(a[i+1].x-p.x)+(p.y-a[i-1].y)*(a[i+1].y-p.y)<0)||Math.abs((p.x-a[i-1].x)*(a[i+1].y-p.y)-(p.y-a[i-1].y)*(a[i+1].x-p.x))>1e-9)
function simple(ps:P[]){
 for(let i=1;i<ps.length-1;i++){const a=ps[i-1],b=ps[i],c=ps[i+1];if(Math.abs((b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x))<1e-10&&(b.x-a.x)*(c.x-b.x)+(b.y-a.y)*(c.y-b.y)<0)return false}
 for(let i=1;i<ps.length;i++)for(let j=i+2;j<ps.length;j++){
  const a=ps[i-1],b=ps[i],c=ps[j-1],d=ps[j]
  if(Math.max(a.x,b.x)+1e-9<Math.min(c.x,d.x)||Math.max(c.x,d.x)+1e-9<Math.min(a.x,b.x)||Math.max(a.y,b.y)+1e-9<Math.min(c.y,d.y)||Math.max(c.y,d.y)+1e-9<Math.min(a.y,b.y))continue
  if(segmentDist(a,b,c,d)<1e-9)return false
 }
 return true
}
export function quality(routes:R[]){
 let bends=0,shortSegments=0,non45Length=0,sharpBends=0,rapidReversals=0,totalLength=0
 for(const r of routes){const ps=clean(r.points);let lastTurn=0
  for(let i=1;i<ps.length;i++){const a=ps[i-1],b=ps[i],d=distance(a,b),angle=Math.atan2(b.y-a.y,b.x-a.x);totalLength+=d;if(d<.3)shortSegments++
   const error=Math.abs(angle/(Math.PI/4)-Math.round(angle/(Math.PI/4)))*(Math.PI/4);if(error>2*Math.PI/180)non45Length+=d
   if(i<ps.length-1){const c=ps[i+1],turn=Math.atan2((b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x),(b.x-a.x)*(c.x-b.x)+(b.y-a.y)*(c.y-b.y));if(Math.abs(turn)>5*Math.PI/180){bends++;if(Math.abs(turn)>Math.PI/4+.01)sharpBends++;if(lastTurn*turn<0&&d<.3)rapidReversals++;lastTurn=turn}}
  }
 }
 return {penalty:bends+2*shortSegments+20*non45Length+2*sharpBends+3*rapidReversals,bends,shortSegments,non45Length,sharpBends,rapidReversals,totalLength}
}
function* candidates(a:P,b:P,target:number):Generator<P[]> {
 yield [a,b]
 const dx=b.x-a.x,dy=b.y-a.y,sx=Math.sign(dx),sy=Math.sign(dy),m=Math.min(Math.abs(dx),Math.abs(dy))
 const bases=[[a,{x:a.x+sx*m,y:a.y+sy*m},b],[a,{x:b.x-sx*m,y:b.y-sy*m},b],[a,{x:a.x,y:b.y},b],[a,{x:b.x,y:a.y},b]].map(clean)
 for(const base of bases){yield base;const extra=target-length(base);if(extra<.001)continue
  for(let k=1;k<base.length;k++){const p=base[k-1],q=base[k],d=distance(p,q);if(d<.3)continue;const ux=(q.x-p.x)/d,uy=(q.y-p.y)/d
   for(const sign of [-1,1])for(const inset of [0,.15,.3]){
    const w=d-2*inset;if(w<.25)continue
    const A={x:p.x+ux*inset,y:p.y+uy*inset},B={x:q.x-ux*inset,y:q.y-uy*inset}
    for(const bevel of [.5,.3,.15,.075,0]){
     const h=(extra+(8-4*Math.SQRT2)*bevel)/2;if(h<2*bevel||w<4*bevel||h>.5*target)continue
     const v=(u:number,n:number)=>({x:A.x+ux*u-uy*n*sign,y:A.y+uy*u+ux*n*sign})
     const loop=bevel?[A,v(bevel,bevel),v(bevel,h-bevel),v(2*bevel,h),v(w-2*bevel,h),v(w-bevel,h-bevel),v(w-bevel,bevel),B]:[A,v(0,h),v(w,h),B]
     yield clean([...base.slice(0,k),...loop,...base.slice(k)])
    }
   }
  }
 }
}
export function smoothTraces(traces:any[],bounds:any){
 const output=structuredClone(traces),routes:R[]=output.map((t:any)=>{const ps=t.route.filter((p:any)=>p.route_type==='wire'&&p.layer!=='top');return{name:t.source_trace_id,layer:ps[0].layer,points:ps.map((p:any)=>({x:p.x,y:p.y}))}})
 const vias=output.flatMap((t:any)=>t.route.filter((p:any)=>p.route_type==='via').map((p:any)=>({...p,net:t.source_trace_id})))
 const before=quality(routes);let accepted=0
 for(const r of routes){const originalLength=length(r.points)
  for(let pass=0;pass<3;pass++){
   let changed=false
   for(let i=0;i<r.points.length-2;i++){
    let best:P[]|undefined,bestJ=0,bestGain=0
    for(const span of [128,64,32,16,8,4,2]){const j=Math.min(r.points.length-1,i+span);if(j<=i+1)continue
     const old=r.points.slice(i,j+1),target=length(old),oldScore=quality([{...r,points:old}]).penalty
     for(const candidate of candidates(old[0],old.at(-1)!,target)){
      if(candidate.length>=old.length&&span<4)continue
      if(Math.abs(length(r.points)-target+length(candidate)-originalLength)>.004)continue
      const gain=oldScore-quality([{...r,points:candidate}]).penalty;if(gain<=bestGain+.01)continue
      if(candidate.some(p=>p.x<bounds.minX+.3||p.x>bounds.maxX-.3||p.y<bounds.minY+.3||p.y>bounds.maxY-.3))continue
      let valid=true
      for(let k=1;k<candidate.length&&valid;k++){
       const a=candidate[k-1],b=candidate[k]
       for(const v of vias)if(v.net!==r.name&&clearanceViolation(a,b,v,v,.3)){valid=false;break}
       for(const other of routes)if(other!==r&&other.layer===r.layer)for(let s=1;s<other.points.length;s++)if(clearanceViolation(a,b,other.points[s-1],other.points[s],.2)){valid=false;break}
       // Reject intersections with retained parts of this route, including near shortcuts.
       for(let s=1;s<r.points.length&&valid;s++)if(s<i||s>j+1)if(clearanceViolation(a,b,r.points[s-1],r.points[s],.1))valid=false
       for(let s=1;s<k-1&&valid;s++)if(clearanceViolation(a,b,candidate[s-1],candidate[s],.1))valid=false
      }
      if(valid&&!simple([...(i?[r.points[i-1]]:[]),...candidate,...(j<r.points.length-1?[r.points[j+1]]:[])]))valid=false
      if(valid){best=candidate;bestJ=j;bestGain=gain}
     }
    }
    if(best){const trial=clean([...r.points.slice(0,i),...best,...r.points.slice(bestJ+1)]);if(Math.abs(length(trial)-originalLength)<=.004&&quality([{...r,points:trial}]).penalty<quality([r]).penalty){r.points=trial;changed=true;accepted++}}
   }
   if(!changed)break
  }
 }
 output.forEach((t:any,i:number)=>{const first=t.route.findIndex((p:any)=>p.route_type==='via'),last=t.route.findLastIndex((p:any)=>p.route_type==='via');t.route=[...t.route.slice(0,first+1),...routes[i].points.map(p=>({route_type:'wire',...p,layer:routes[i].layer,width:.1})),...t.route.slice(last)]})
 const report={before,after:quality(routes),accepted};console.log('SMOOTHING_REPORT '+JSON.stringify(report));return{traces:output,report}
}