zach/dotter

// SVG -> polylines in inches, for plotting. Handles path, line, polyline,

// polygon, rect, circle and ellipse elements, nested transforms, physical

// units and the root viewBox. Curves are flattened to within `tolerance`

// inches. Text must be converted to paths first (e.g. in Inkscape).

const PX_PER_INCH = 96;

const UNIT_INCHES = { in: 1, mm: 1 / 25.4, cm: 1 / 2.54, pt: 1 / 72, pc: 1 / 6, px: 1 / 96, '': 1 / 96, q: 1 / 101.6 };

const SKIP_TAGS = new Set(['defs', 'clippath', 'mask', 'symbol', 'marker', 'pattern', 'metadata', 'title',

  'desc', 'style', 'script', 'text', 'image', 'lineargradient', 'radialgradient', 'filter', 'foreignobject']);

/** Parse an SVG length like "8.5in" or "210mm" into inches (null if absent or %). */

export function lengthToInches(value) {

  if (value == null) return null;

  const m = String(value).trim().match(/^([+-]?(?:\d+\.?\d*|\.\d+)(?:e[+-]?\d+)?)\s*([a-z%]*)$/i);

  if (!m || m[2] === '%') return null;

  const unit = UNIT_INCHES[m[2].toLowerCase()];

  return unit == null ? null : parseFloat(m[1]) * unit;

}

// --- Affine matrices [a, b, c, d, e, f]: x' = a x + c y + e, y' = b x + d y + f ---

export const IDENTITY = [1, 0, 0, 1, 0, 0];

export function multiply(m, n) {

  return [

    m[0] * n[0] + m[2] * n[1], m[1] * n[0] + m[3] * n[1],

    m[0] * n[2] + m[2] * n[3], m[1] * n[2] + m[3] * n[3],

    m[0] * n[4] + m[2] * n[5] + m[4], m[1] * n[4] + m[3] * n[5] + m[5],

  ];

}

export function apply(m, [x, y]) {

  return [m[0] * x + m[2] * y + m[4], m[1] * x + m[3] * y + m[5]];

}

/** Parse a transform attribute into a matrix. */

export function parseTransform(text) {

  let m = IDENTITY;

  if (!text) return m;

  const re = /(matrix|translate|scale|rotate|skewX|skewY)\s*\(([^)]*)\)/g;

  let match;

  while ((match = re.exec(text))) {

    const v = (match[2].match(/[+-]?(?:\d+\.?\d*|\.\d+)(?:e[+-]?\d+)?/gi) || []).map(Number);

    let t = IDENTITY;

    switch (match[1]) {

      case 'matrix': t = v.length === 6 ? v : IDENTITY; break;

      case 'translate': t = [1, 0, 0, 1, v[0] || 0, v[1] || 0]; break;

      case 'scale': t = [v[0] ?? 1, 0, 0, v[1] ?? v[0] ?? 1, 0, 0]; break;

      case 'rotate': {

        const a = (v[0] || 0) * Math.PI / 180;

        const r = [Math.cos(a), Math.sin(a), -Math.sin(a), Math.cos(a), 0, 0];

        if (v.length >= 3) {

          t = multiply(multiply([1, 0, 0, 1, v[1], v[2]], r), [1, 0, 0, 1, -v[1], -v[2]]);

        } else {

          t = r;

        }

        break;

      }

      case 'skewX': t = [1, 0, Math.tan((v[0] || 0) * Math.PI / 180), 1, 0, 0]; break;

      case 'skewY': t = [1, Math.tan((v[0] || 0) * Math.PI / 180), 0, 1, 0, 0]; break;

    }

    m = multiply(m, t);

  }

  return m;

}

// --- Path data ---

function tokenize(d) {

  const tokens = [];

  const re = /([MmZzLlHhVvCcSsQqTtAa])|([+-]?(?:\d+\.?\d*|\.\d+)(?:[eE][+-]?\d+)?)/g;

  let m;

  while ((m = re.exec(d))) tokens.push(m[1] ?? Number(m[2]));

  return tokens;

}

const ARG_COUNTS = { M: 2, L: 2, H: 1, V: 1, C: 6, S: 4, Q: 4, T: 2, A: 7, Z: 0 };

/** Recursively flatten a cubic Bezier until it is within tol of its chord. */

function flattenCubic(p0, p1, p2, p3, tol, out, depth = 0) {

  const dx = p3[0] - p0[0];

  const dy = p3[1] - p0[1];

  const len = Math.hypot(dx, dy);

  const dist = (p) => (len > 1e-12

    ? Math.abs((p[0] - p0[0]) * dy - (p[1] - p0[1]) * dx) / len

    : Math.hypot(p[0] - p0[0], p[1] - p0[1]));

  if (depth > 16 || Math.max(dist(p1), dist(p2)) <= tol) {

    out.push(p3);

    return;

  }

  const mid = (a, b) => [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];

  const p01 = mid(p0, p1);

  const p12 = mid(p1, p2);

  const p23 = mid(p2, p3);

  const p012 = mid(p01, p12);

  const p123 = mid(p12, p23);

  const m = mid(p012, p123);

  flattenCubic(p0, p01, p012, m, tol, out, depth + 1);

  flattenCubic(m, p123, p23, p3, tol, out, depth + 1);

}

/** Flatten an SVG elliptical arc (endpoint parameterization). */

function flattenArc(p0, rx, ry, phiDeg, largeArc, sweep, p1, tol, out) {

  rx = Math.abs(rx);

  ry = Math.abs(ry);

  if (rx === 0 || ry === 0) {

    out.push(p1);

    return;

  }

  const phi = phiDeg * Math.PI / 180;

  const cos = Math.cos(phi);

  const sin = Math.sin(phi);

  const dx2 = (p0[0] - p1[0]) / 2;

  const dy2 = (p0[1] - p1[1]) / 2;

  const x1p = cos * dx2 + sin * dy2;

  const y1p = -sin * dx2 + cos * dy2;

  const lambda = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);

  if (lambda > 1) {

    rx *= Math.sqrt(lambda);

    ry *= Math.sqrt(lambda);

  }

  const num = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p;

  const den = rx * rx * y1p * y1p + ry * ry * x1p * x1p;

  let coef = Math.sqrt(Math.max(0, num / den));

  if (largeArc === sweep) coef = -coef;

  const cxp = coef * (rx * y1p / ry);

  const cyp = coef * (-ry * x1p / rx);

  const cx = cos * cxp - sin * cyp + (p0[0] + p1[0]) / 2;

  const cy = sin * cxp + cos * cyp + (p0[1] + p1[1]) / 2;

  const angle = (ux, uy, vx, vy) => Math.atan2(ux * vy - uy * vx, ux * vx + uy * vy);

  const theta1 = angle(1, 0, (x1p - cxp) / rx, (y1p - cyp) / ry);

  let dTheta = angle((x1p - cxp) / rx, (y1p - cyp) / ry, (-x1p - cxp) / rx, (-y1p - cyp) / ry);

  if (!sweep && dTheta > 0) dTheta -= 2 * Math.PI;

  if (sweep && dTheta < 0) dTheta += 2 * Math.PI;

  // Chord error for a step angle a on radius r is r(1 - cos(a/2)).

  const r = Math.max(rx, ry);

  const maxStep = tol < r ? 2 * Math.acos(1 - tol / r) : Math.PI / 2;

  const n = Math.max(1, Math.ceil(Math.abs(dTheta) / maxStep));

  for (let i = 1; i <= n; i++) {

    const t = theta1 + dTheta * i / n;

    const x = rx * Math.cos(t);

    const y = ry * Math.sin(t);

    out.push(i === n ? p1 : [cos * x - sin * y + cx, sin * x + cos * y + cy]);

  }

}

/**

 * Flatten SVG path data into subpaths (arrays of [x, y]) in user units.

 * `tol` is the allowed deviation in the same units.

 */

export function parsePathData(d, tol = 0.1) {

  const tokens = tokenize(d || '');

  const subpaths = [];

  let current = null;

  let pos = [0, 0];

  let start = [0, 0];

  let lastCtrl = null; // For S/s and T/t reflection

  let lastCmd = '';

  let i = 0;

  let cmd = null;

  const begin = (p) => {

    current = [p];

    subpaths.push(current);

    start = p;

  };

  while (i < tokens.length) {

    if (typeof tokens[i] === 'string') cmd = tokens[i++];

    else if (cmd == null) break;

    const upper = cmd.toUpperCase();

    const rel = cmd !== upper;

    const n = ARG_COUNTS[upper];

    if (upper === 'Z') {

      if (current && current.length) current.push([...start]);

      pos = [...start];

      current = null;

      lastCtrl = null;

      lastCmd = 'Z';

      continue;

    }

    if (i + n > tokens.length || tokens.slice(i, i + n).some((t) => typeof t !== 'number')) break;

    const a = tokens.slice(i, i + n);

    i += n;

    const pt = (x, y) => (rel ? [pos[0] + x, pos[1] + y] : [x, y]);

    if (!current && upper !== 'M') begin([...pos]);

    switch (upper) {

      case 'M': {

        pos = pt(a[0], a[1]);

        begin(pos);

        cmd = rel ? 'l' : 'L'; // Extra coordinate pairs are implicit linetos.

        lastCtrl = null;

        break;

      }

      case 'L': pos = pt(a[0], a[1]); current.push(pos); lastCtrl = null; break;

      case 'H': pos = [rel ? pos[0] + a[0] : a[0], pos[1]]; current.push(pos); lastCtrl = null; break;

      case 'V': pos = [pos[0], rel ? pos[1] + a[0] : a[0]]; current.push(pos); lastCtrl = null; break;

      case 'C': case 'S': {

        let c1;

        let c2;

        let end;

        if (upper === 'C') {

          c1 = pt(a[0], a[1]); c2 = pt(a[2], a[3]); end = pt(a[4], a[5]);

        } else {

          c1 = lastCtrl && 'CS'.includes(lastCmd) ? [2 * pos[0] - lastCtrl[0], 2 * pos[1] - lastCtrl[1]] : [...pos];

          c2 = pt(a[0], a[1]); end = pt(a[2], a[3]);

        }

        flattenCubic(pos, c1, c2, end, tol, current);

        lastCtrl = c2;

        pos = end;

        break;

      }

      case 'Q': case 'T': {

        let q;

        let end;

        if (upper === 'Q') {

          q = pt(a[0], a[1]); end = pt(a[2], a[3]);

        } else {

          q = lastCtrl && 'QT'.includes(lastCmd) ? [2 * pos[0] - lastCtrl[0], 2 * pos[1] - lastCtrl[1]] : [...pos];

          end = pt(a[0], a[1]);

        }

        // Elevate quadratic to cubic.

        const c1 = [pos[0] + 2 / 3 * (q[0] - pos[0]), pos[1] + 2 / 3 * (q[1] - pos[1])];

        const c2 = [end[0] + 2 / 3 * (q[0] - end[0]), end[1] + 2 / 3 * (q[1] - end[1])];

        flattenCubic(pos, c1, c2, end, tol, current);

        lastCtrl = q;

        pos = end;

        break;

      }

      case 'A': {

        const end = pt(a[5], a[6]);

        flattenArc(pos, a[0], a[1], a[2], Boolean(a[3]), Boolean(a[4]), end, tol, current);

        pos = end;

        lastCtrl = null;

        break;

      }

    }

    lastCmd = upper;

  }

  return subpaths.filter((s) => s.length >= 2);

}

function num(el, name, dflt = 0) {

  const v = parseFloat(el.getAttribute(name));

  return Number.isFinite(v) ? v : dflt;

}

/** Path data equivalent of a basic shape element, or null. */

export function shapeToPathData(tag, el) {

  switch (tag) {

    case 'path': return el.getAttribute('d');

    case 'line': return `M${num(el, 'x1')},${num(el, 'y1')} L${num(el, 'x2')},${num(el, 'y2')}`;

    case 'polyline':

    case 'polygon': {

      const pts = (el.getAttribute('points') || '').trim();

      if (!pts) return null;

      return `M${pts}${tag === 'polygon' ? 'Z' : ''}`;

    }

    case 'rect': {

      const x = num(el, 'x');

      const y = num(el, 'y');

      const w = num(el, 'width');

      const h = num(el, 'height');

      if (w <= 0 || h <= 0) return null;

      let rx = el.hasAttribute('rx') ? num(el, 'rx') : null;

      let ry = el.hasAttribute('ry') ? num(el, 'ry') : null;

      rx = Math.min(rx ?? ry ?? 0, w / 2);

      ry = Math.min(ry ?? rx ?? 0, h / 2);

      if (rx <= 0 || ry <= 0) return `M${x},${y}H${x + w}V${y + h}H${x}Z`;

      return `M${x + rx},${y}H${x + w - rx}A${rx},${ry} 0 0 1 ${x + w},${y + ry}V${y + h - ry}` +

        `A${rx},${ry} 0 0 1 ${x + w - rx},${y + h}H${x + rx}A${rx},${ry} 0 0 1 ${x},${y + h - ry}` +

        `V${y + ry}A${rx},${ry} 0 0 1 ${x + rx},${y}Z`;

    }

    case 'circle':

    case 'ellipse': {

      const cx = num(el, 'cx');

      const cy = num(el, 'cy');

      const rx = tag === 'circle' ? num(el, 'r') : num(el, 'rx');

      const ry = tag === 'circle' ? rx : num(el, 'ry');

      if (rx <= 0 || ry <= 0) return null;

      return `M${cx + rx},${cy}A${rx},${ry} 0 1 1 ${cx - rx},${cy}A${rx},${ry} 0 1 1 ${cx + rx},${cy}Z`;

    }

    default: return null;

  }

}

function isHidden(el) {

  const style = el.getAttribute('style') || '';

  return el.getAttribute('display') === 'none' || el.getAttribute('visibility') === 'hidden' ||

    /display\s*:\s*none/.test(style) || /visibility\s*:\s*hidden/.test(style);

}

/** Document size in inches and the user-unit -> inch matrix for an <svg> root. */

export function documentFrame(svg) {

  const vb = (svg.getAttribute('viewBox') || '').trim().split(/[\s,]+/).map(Number);

  const hasVb = vb.length === 4 && vb.every(Number.isFinite) && vb[2] > 0 && vb[3] > 0;

  let width = lengthToInches(svg.getAttribute('width'));

  let height = lengthToInches(svg.getAttribute('height'));

  if (width == null) width = hasVb ? vb[2] / PX_PER_INCH : 8.5;

  if (height == null) height = hasVb ? vb[3] / PX_PER_INCH : 11;

  let m = [1 / PX_PER_INCH, 0, 0, 1 / PX_PER_INCH, 0, 0];

  if (hasVb) {

    // preserveAspectRatio="xMidYMid meet" (the default)

    const s = Math.min(width / vb[2], height / vb[3]);

    const tx = (width - vb[2] * s) / 2 - vb[0] * s;

    const ty = (height - vb[3] * s) / 2 - vb[1] * s;

    m = [s, 0, 0, s, tx, ty];

  }

  return { width, height, matrix: m };

}

/**

 * Convert a parsed SVG document (DOM Document or root element) to polylines

 * in inches. Options: tolerance (in), autoRotate (rotate portrait pages to fit

 * the landscape travel area).

 */

export function svgToPolylines(doc, { tolerance = 0.002, autoRotate = true } = {}) {

  const svg = doc.documentElement ?? doc;

  const { width, height, matrix } = documentFrame(svg);

  const rotate = autoRotate && height > width;

  // Rotate 90° counter-clockwise: page top edge goes to the machine's left side.

  const rootMatrix = rotate ? multiply([0, -1, 1, 0, 0, width], matrix) : matrix;

  const scale = Math.sqrt(Math.abs(rootMatrix[0] * rootMatrix[3] - rootMatrix[1] * rootMatrix[2]));

  const polylines = [];

  const walk = (el, m) => {

    const tag = (el.localName || el.nodeName || '').toLowerCase();

    if (SKIP_TAGS.has(tag) || isHidden(el)) return;

    const local = multiply(m, parseTransform(el.getAttribute('transform')));

    const d = shapeToPathData(tag, el);

    if (d) {

      const det = Math.sqrt(Math.abs(local[0] * local[3] - local[1] * local[2])) || scale;

      for (const sub of parsePathData(d, tolerance / det)) polylines.push(sub.map((p) => apply(local, p)));

    }

    for (const child of el.children ?? []) walk(child, local);

  };

  for (const child of svg.children ?? []) walk(child, rootMatrix);

  return {

    polylines,

    width: rotate ? height : width,

    height: rotate ? width : height,

    rotated: rotate,

  };

}

/** Join consecutive polylines whose ends meet within minGap (saves pen lifts). */

export function joinPolylines(polylines, minGap = 0.006) {

  const out = [];

  for (const p of polylines) {

    const prev = out[out.length - 1];

    if (prev) {

      const end = prev[prev.length - 1];

      if (Math.hypot(end[0] - p[0][0], end[1] - p[0][1]) <= minGap) {

        prev.push(...p.slice(1));

        continue;

      }

    }

    out.push([...p]);

  }

  return out;

}