Furniture layout of a room

/** The four corners of a rectangle centred at (x, y), `w` across and `d` deep, turned `rot`; extra margins front/back/sides widen the box (used as the reserved zone). */
function corners(x, y, w, d, rot, { front = 0, side = 0 } = {}) {
  const c = Math.cos(rad(rot)), s = Math.sin(rad(rot));
  // local frame: u across (x), v from front (0) to back (d): the box spans v in [-front, d]
  const u0 = -w / 2 - side, u1 = w / 2 + side, v0 = -front, v1 = d;
  return [[u0, v0], [u1, v0], [u1, v1], [u0, v1]].map(([u, v]) => [x + u * c - v * s, y + u * s + v * c]);
}

/** Do two convex rectangles overlap by more than a hair (separating axis)? */
function overlaps(a, b, eps = 1) {
  for (const ax of [...axes(a), ...axes(b)]) { const [a0, a1] = range(a, ax), [b0, b1] = range(b, ax); if (a1 <= b0 + eps || b1 <= a0 + eps) return false; }
  return true;
}

function inside(poly, p) {
  let c = false;
  for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
    const a = poly[i], b = poly[j];
    if ((a[1] > p[1]) !== (b[1] > p[1]) && p[0] < ((b[0] - a[0]) * (p[1] - a[1])) / (b[1] - a[1]) + a[0]) c = !c;
  }
  return c;
}

/** Does the rectangle sit inside the room (corners and edge midpoints in, none in a hole)? */
function fits(room, rect) {
  // a piece stands against the wall: its back is ON the boundary, where "inside" is a coin toss, so the points are pulled 2 mm toward the middle
  const mx = rect.reduce((s, q) => s + q[0], 0) / 4, my = rect.reduce((s, q) => s + q[1], 0) / 4;
  const pull = (q) => { const dx = mx - q[0], dy = my - q[1], l = Math.hypot(dx, dy) || 1; return [q[0] + (dx / l) * 2, q[1] + (dy / l) * 2]; };
  const pts = [...rect, ...rect.map((q, i) => [(q[0] + rect[(i + 1) % 4][0]) / 2, (q[1] + rect[(i + 1) % 4][1]) / 2])].map(pull);
  if (!pts.every((p) => inside(room.poly, p))) return false;
  for (const h of room.holes || []) if (pts.some((p) => inside(h, p))) return false;
  return true;
}

const area = (poly) => { let s = 0; for (let i = 0; i < poly.length; i++) { const a = poly[i], b = poly[(i + 1) % poly.length]; s += a[0] * b[1] - b[0] * a[1]; } return s / 2; };

const doorRects = doors.map((d) => {
  const e = edges.find((x) => distToSeg([d.x, d.y], x.a, x.b) < 400) || edges[0];
  const ang = (Math.atan2(e.dir[1], e.dir[0]) * 180) / Math.PI;
  // box centred on the door, aligned with the wall: v from -(w) to +(w)
  return corners(d.x, d.y, d.w + 300, d.w, ang, { front: d.w });
});

const rot = (Math.atan2(e.n[0], -e.n[1]) * 180) / Math.PI;
if (e.l < p.w + 2 * (p.side || 0) - 1) continue;
// slide along the wall from one end; the first free spot wins (deterministic)
const from = p.w / 2 + (p.side || 0), to = e.l - p.w / 2 - (p.side || 0);
for (let t = from; t <= to + 0.5; t += step) {
  const wx = e.a[0] + e.dir[0] * t, wy = e.a[1] + e.dir[1] * t;
  const x = wx + e.n[0] * p.d, y = wy + e.n[1] * p.d;   // origin = the front of the piece; the back stands on the wall
  const rect = corners(x, y, p.w, p.d, rot);
  const zr = corners(x, y, p.w, p.d, rot, { front: p.clear, side: p.side || 0 });
  if (free(rect, p, zr)) { done = { family, x: Math.round(x), y: Math.round(y), rot: Math.round(rot * 1000) / 1000, w: p.w, d: p.d, rect, zone: zr, why: 'against the wall ' + Math.round(e.l) + ' mm long' }; break; }

const mid = [(Math.min(...xs) + Math.max(...xs)) / 2, (Math.min(...ys) + Math.max(...ys)) / 2];
const along = edges[0] ? (Math.atan2(edges[0].dir[1], edges[0].dir[0]) * 180) / Math.PI : 0;
const spots = [[0, 0]];
for (let k = 1; k <= 20; k++) for (const [ux, uy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) spots.push([ux * k * 150, uy * k * 150]);
for (const rot of [along, along + 90]) {
  for (const [dx, dy] of spots) {
    const cx = mid[0] + dx, cy = mid[1] + dy;
    const ox = cx + Math.sin(rad(rot)) * (p.d / 2), oy = cy - Math.cos(rad(rot)) * (p.d / 2);   // the front-centre of the box
    const rect = corners(ox, oy, p.w, p.d, rot);
    const zr = corners(ox, oy, p.w, p.d, rot, { front: p.clear / 2, side: p.clear / 2 });
    if (free(rect, p, zr)) { done = { family, x: Math.round(cx), y: Math.round(cy), rot: Math.round(rot * 1000) / 1000, w: p.w, d: p.d, rect, zone: zr, why: 'in the middle of the room' }; break; }

/** A placement's four plan corners (the box of the piece itself, no clearance). */
export function footprint(p) {
  const free = PIECES[p.family]?.at === 'free';
  return free ? corners(p.x + Math.sin(rad(p.rot)) * (p.d / 2), p.y - Math.cos(rad(p.rot)) * (p.d / 2), p.w, p.d, p.rot) : corners(p.x, p.y, p.w, p.d, p.rot);
}