Post-processing fix for Earcut's non-comforming output

remove-t-junctions.js

// Post-processing fix for Earcut's issue https://github.com/mapbox/earcut/issues/74
// Split triangle edges wherever another vertex lies strictly on them (exact-coordinate input).
export function removeTJunctions(data, tri) {
  const n = data.length / 2;

  // bucket every vertex into a uniform spatial hash so edge lookups stay local
  let minx=Infinity,miny=Infinity,maxx=-Infinity,maxy=-Infinity;
  for (let i=0;i<n;i++){const x=data[2*i],y=data[2*i+1];if(x<minx)minx=x;if(y<miny)miny=y;if(x>maxx)maxx=x;if(y>maxy)maxy=y;}
  const size = Math.max(maxx-minx, maxy-miny) / Math.max(1, Math.sqrt(n)) || 1;
  const key = (cx,cy) => cx*73856093 ^ cy*19349663;
  const cell = new Map();
  for (let i=0;i<n;i++){
    const cx=Math.floor((data[2*i]-minx)/size), cy=Math.floor((data[2*i+1]-miny)/size);
    const k=key(cx,cy); let a=cell.get(k); if(!a){a=[];cell.set(k,a);} a.push(i);
  }

  const out = [];
  for (let t=0;t<tri.length;t+=3){
    const idx=[tri[t],tri[t+1],tri[t+2]];
    let handled=false;
    for (let e=0;e<3 && !handled;e++){
      const A=idx[e], B=idx[(e+1)%3], C=idx[(e+2)%3];          // C is the apex
      const ax=data[2*A],ay=data[2*A+1],bx=data[2*B],by=data[2*B+1];
      const c0x=Math.floor((Math.min(ax,bx)-minx)/size), c0y=Math.floor((Math.min(ay,by)-miny)/size);
      const c1x=Math.floor((Math.max(ax,bx)-minx)/size), c1y=Math.floor((Math.max(ay,by)-miny)/size);
      const onedge=[];
      for (let cx=c0x;cx<=c1x;cx++) for (let cy=c0y;cy<=c1y;cy++){
        const arr=cell.get(key(cx,cy)); if(!arr) continue;
        for (const p of arr){
          if (p===A||p===B||p===C) continue;
          const px=data[2*p],py=data[2*p+1];
          if ((bx-ax)*(py-ay)-(by-ay)*(px-ax) !== 0) continue;  // not collinear
          const dot=(px-ax)*(bx-ax)+(py-ay)*(by-ay), len2=(bx-ax)**2+(by-ay)**2;
          if (dot<=0 || dot>=len2) continue;                    // not strictly between A and B
          onedge.push([p,dot]);
        }
      }
      if (onedge.length){                                       // fan apex C across A -> p... -> B
        onedge.sort((u,v)=>u[1]-v[1]);
        let prev=A; for (const [p] of onedge){ out.push(C,prev,p); prev=p; } out.push(C,prev,B);
        handled=true;
      }
    }
    if (!handled) out.push(idx[0],idx[1],idx[2]);
  }
  return out;
}