Lays parts out on sheets or a roll, reports the sheets used and the efficiency, checks the result, reads part outlines from DXF and writes the nest as DXF.
How the precision is kept
Part geometry is 64-bit. Placement is decided on a raster of res-sized cells, so every part lands on a multiple of res from the margin and the clearance between parts is rounded up to whole cells. Areas use the exact arc-segment formula. Arcs are flattened to chords with a stated sag for the raster and for the re-check. The DXF writer keeps 6 decimals.
Open item. Write DXF coordinates and bulges with the shortest text that reads back to the same 64-bit number instead of 6 fixed decimals.
Calculations under this policy
19 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
Each point is computed from the start angle plus θ × k ÷ steps, not by adding a step repeatedly, so error does not build up along the arc. The acos argument is clamped to [−1, 1]. A sag of 0 would divide by zero; the nest and re-check paths in this file pass a positive sag.
addons/cabinetcraft/lib/nest/nest.js
lines 55 to 76
CadCraft 0.8.2
/** A loop with bulges → points along it (arcs as chords whose sag is at most `sag`). */
export function flatten(loop, sag = 0.05) {
const out = [];
const n = loop.length;
for (let i = 0; i < n; i++) {
const p = loop[i], q = loop[(i + 1) % n], b = p.b || 0;
out.push({ x: p.x, y: p.y });
if (!b || n < 2) continue;
const th = 4 * Math.atan(b); // signed sweep
const ch = Math.hypot(q.x - p.x, q.y - p.y);
if (ch < 1e-12) continue;
const r = ch / (2 * Math.sin(Math.abs(th) / 2));
const steps = Math.max(1, Math.ceil(Math.abs(th) / (2 * Math.acos(Math.max(-1, Math.min(1, 1 - Math.min(sag, r) / r))))));
// centre: from the chord's middle, along its normal (left for CCW)
const mx = (p.x + q.x) / 2, my = (p.y + q.y) / 2, ux = (q.x - p.x) / ch, uy = (q.y - p.y) / ch;
const d = r * Math.cos(th / 2) * Math.sign(th);
const cx = mx - uy * d, cy = my + ux * d;
const a0 = Math.atan2(p.y - cy, p.x - cx);
for (let k = 1; k < steps; k++) { const a = a0 + th * k / steps; out.push({ x: cx + r * Math.cos(a), y: cy + r * Math.sin(a) }); }
}
return out;
}
Area of a loop with arcs
64-bit
The signed area of a closed loop, with each arc's segment included.
The arc term is the closed form, not a sum over chords. For a very shallow arc |θ| − sin|θ| subtracts two nearly equal numbers and loses digits; the area concerned is itself small. The shoelace sum uses the loop's own coordinates, so a part far from its origin has large products next to their difference.
addons/cabinetcraft/lib/nest/nest.js
lines 78 to 92
CadCraft 0.8.2
/** Signed area of a loop (bulges included exactly). */
export function loopArea(loop) {
let a = 0;
const n = loop.length;
for (let i = 0; i < n; i++) {
const p = loop[i], q = loop[(i + 1) % n];
a += p.x * q.y - q.x * p.y;
const b = p.b || 0;
if (b) {
const th = 4 * Math.atan(b), ch = Math.hypot(q.x - p.x, q.y - p.y);
if (ch > 1e-12) { const r = ch / (2 * Math.sin(Math.abs(th) / 2)); a += Math.sign(th) * r * r * (Math.abs(th) - Math.sin(Math.abs(th))); }
}
}
return a / 2;
}
Area of a part
64-bit
A part's area: its outline less its holes.
area = |A₀| − Σ |Aₖ|
The absolute loop areas are combined in order; the holes are subtracted one by one.
addons/cabinetcraft/lib/nest/nest.js
lines 94 to 95
CadCraft 0.8.2
/** A part's area: its outline less its holes. */
export const regionArea = (loops) => loops.reduce((s, l, i) => s + (i === 0 ? 1 : -1) * Math.abs(loopArea(l)), 0);
A part moved to its place
64-bit
Rotates, mirrors and moves a part's loops to their position on the sheet.
q = (x, y) + R(rot) · (m pₓ, p_y), m = −1 when mirrored; bulge × m
The cosine and sine are computed once per call. Bulges are carried through unchanged except for the mirror sign, so arcs stay arcs. Nothing is rounded.
addons/cabinetcraft/lib/nest/nest.js
lines 105 to 112
CadCraft 0.8.2
/** Place loops: q = (x, y) + R(rot)·M(p). Mirroring flips the bulges. */
export function placeLoops(loops, { rot = 0, mirror = false, x = 0, y = 0 }) {
const c = Math.cos(rot), s = Math.sin(rot), m = mirror ? -1 : 1;
return loops.map((l) => {
const out = l.map((p) => { const px = m * p.x; const q = { x: x + c * px - s * p.y, y: y + s * px + c * p.y }; if (p.b) q.b = m * p.b; return q; });
return out;
});
}
Turns a part may take
64-bit
The rotation angles tried for a part, from its grain and the turn step.
no grain: rot = k × 2π ÷ n, n = round(360 ÷ step); grain: rot = −g (+ π) ± tolerance
Angles are reduced modulo 2π, and one within 1e-12 of 2π becomes 0. The grain tolerance is limited to 0 to 45 degrees. The 9-decimal text of the angle is used only to drop repeats.
addons/cabinetcraft/lib/nest/nest.js
lines 116 to 137
CadCraft 0.8.2
/** The turns and mirrors a part may take. */
export function orientations(part, { step = 90, grainTol = 0 } = {}) {
const out = [];
const mirrors = part.mirrored ? [true] : part.mirror ? [false, true] : [false];
for (const mirror of mirrors) {
if (part.grain != null && Number.isFinite(part.grain)) {
const g = mirror ? Math.PI - part.grain : part.grain; // the grain's direction once mirrored
const base = -g;
const ends = part.turn === false ? [base] : [base, base + Math.PI];
const tol = Math.max(0, Math.min(45, grainTol || 0)) * Math.PI / 180;
const small = tol > 0 ? [0, -tol, tol, -tol / 2, tol / 2] : [0];
for (const e of ends) for (const d of small) out.push({ rot: norm(e + d), mirror });
} else {
const st = Math.abs(step || 0);
const n = st > 0 && st < 360 ? Math.max(1, Math.round(360 / st)) : 1;
for (let k = 0; k < n; k++) out.push({ rot: norm(k * TAU / n), mirror });
}
}
// drop repeats (a 180° turn of a part drawn symmetric is still tried: the raster decides)
const seen = new Set();
return out.filter((o) => { const k = o.mirror + ':' + o.rot.toFixed(9); if (seen.has(k)) return false; seen.add(k); return true; });
}
A shape on the raster
64-bit
Marks every grid cell a part touches.
cell i = ⌊(x − oₓ) ÷ res⌋; edge cells from the segment's lowest and highest point in each column
Conservative by construction: every cell an edge passes through is set, and the inside is filled along each column's middle line. The result is whole cells, so it over-covers the part by up to one cell on each side. A point exactly on a column line also sets the column to its left.
addons/cabinetcraft/lib/nest/nest.js
lines 142 to 201
CadCraft 0.8.2
/**
* Every cell a region touches, as intervals per column. polys: flattened loops (even-odd region). The grid's cell (i, j)
* covers [ox + i·res, ox + (i + 1)·res] × [oy + j·res, …]. → { cols, rows, iv: [Int32Array [a0, b0, a1, b1 …]] }
*/
export function rasterize(polys, ox, oy, cols, rows, res) {
const grid = new Uint8Array(cols * rows);
const set = (i, j0, j1) => {
if (i < 0 || i >= cols) return;
if (j0 > j1) { const t = j0; j0 = j1; j1 = t; }
j0 = Math.max(0, j0); j1 = Math.min(rows - 1, j1);
for (let j = j0; j <= j1; j++) grid[i * rows + j] = 1;
};
// the edges: for each column the segment crosses, the cells between its lowest and highest point in that column
for (const pl of polys) {
const n = pl.length;
for (let k = 0; k < n; k++) {
const p = pl[k], q = pl[(k + 1) % n];
const ax = (p.x - ox) / res, ay = (p.y - oy) / res, bx = (q.x - ox) / res, by = (q.y - oy) / res;
const i0 = Math.floor(Math.min(ax, bx)), i1 = Math.floor(Math.max(ax, bx));
if (i0 === i1 || Math.abs(bx - ax) < 1e-12) { set(i0, Math.floor(Math.min(ay, by)), Math.floor(Math.max(ay, by))); if (Math.abs(bx - ax) < 1e-12 && Number.isInteger(ax)) set(ax - 1, Math.floor(Math.min(ay, by)), Math.floor(Math.max(ay, by))); continue; }
const yAt = (x) => ay + (by - ay) * (x - ax) / (bx - ax);
const lo = Math.min(ax, bx), hi = Math.max(ax, bx);
for (let i = i0; i <= i1; i++) {
const xa = Math.max(lo, i), xb = Math.min(hi, i + 1);
const ya = yAt(xa), yb = yAt(xb);
set(i, Math.floor(Math.min(ya, yb)), Math.floor(Math.max(ya, yb)));
// a point exactly on a column line touches the column on its left too
if (Number.isInteger(xa) && xa === i) set(i - 1, Math.floor(ya), Math.floor(ya));
}
}
}
// the inside: a scan line through each column's middle (even-odd)
const xs = [];
for (let i = 0; i < cols; i++) {
const x = ox + (i + 0.5) * res;
xs.length = 0;
for (const pl of polys) {
const n = pl.length;
for (let k = 0; k < n; k++) {
const p = pl[k], q = pl[(k + 1) % n];
if ((p.x <= x) !== (q.x <= x)) xs.push(p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x));
}
}
xs.sort((a, b) => a - b);
for (let k = 0; k + 1 < xs.length; k += 2) set(i, Math.floor((xs[k] - oy) / res), Math.floor((xs[k + 1] - oy) / res));
}
const iv = new Array(cols);
for (let i = 0; i < cols; i++) {
const runs = [];
let j = 0;
while (j < rows) {
if (!grid[i * rows + j]) { j++; continue; }
const a = j;
while (j < rows && grid[i * rows + j]) j++;
runs.push(a, j - 1);
}
iv[i] = Int32Array.from(runs);
}
return { cols, rows, iv };
}
Raster cell size and clearance
64-bit
The cell size of the raster, the arc sag, and the number of cells kept clear around each part.
res = max((h − 2 margin) ÷ 750, 1e-6), at most smallest ÷ 4; sag = min(res ÷ 8, 0.1); grow = ⌈(spacing + 2 sag) ÷ res − 1e-9⌉
The clearance is rounded up to whole cells, so parts end up at least spacing + 2 × sag apart and up to a cell more. The usable height and width are rounded down to whole cells with a 1e-9 allowance.
addons/cabinetcraft/lib/nest/nest.js
lines 302 to 308
CadCraft 0.8.2
let res = Number(opts.res) > 0 ? Number(opts.res) : Math.max((H0 - 2 * margin) / 750, 1e-6);
if (!(Number(opts.res) > 0) && Number.isFinite(smallest) && smallest > 0) res = Math.min(res, smallest / 4);
const sag = Math.min(res / 8, 0.1);
const grow = Math.ceil((spacing + 2 * sag) / res - 1e-9); // cells of clearance round a placed part
const growObs = sheet.obstacleGap != null ? Math.ceil((Math.max(0, Number(sheet.obstacleGap) || 0) + 2 * sag) / res - 1e-9) : grow; // …and round an obstacle
const H = Math.floor((H0 - 2 * margin) / res + 1e-9);
const Wc = roll ? Infinity : Math.floor((W0 - 2 * margin) / res + 1e-9);
Placed position of a part
64-bit
The position of each placed part in sheet coordinates.
x = margin + gₓ × res − shape origin x; y = margin + g_y × res − shape origin y
The grid cell is turned back into a coordinate with one multiplication and two additions in 64-bit; nothing is rounded. The position is therefore a whole number of cells from the margin, less the offset of the shape's own bounding box.
addons/cabinetcraft/lib/nest/nest.js
lines 441 to 443
CadCraft 0.8.2
const x = margin + b.gx * res - s.ox, y = margin + b.gy * res - s.oy;
const pl = { rot: s.orient.rot, mirror: s.orient.mirror, x, y };
out.push({ part: cp.k.index, id: cp.k.part.id, name: cp.k.part.name, copy: cp.copy, sheet: b.sheet, ...pl, loops: placeLoops(cp.k.loops, pl), area: cp.k.area });
Used length and efficiency
64-bit
The length used on each sheet and the share of the sheet area the parts cover.
used = max x of the placed outlines + margin; efficiency = Σ part area ÷ (sheets × w × h), or ÷ (used × h) on a roll
The largest x is taken from outlines flattened with a sag of 0.001, so where an arc is the furthest edge it can be up to 0.001 short. The part areas are the exact loop areas, summed in placement order.
addons/cabinetcraft/lib/nest/nest.js
lines 448 to 458
CadCraft 0.8.2
const on = out.filter((p) => p.sheet === i);
let used = 0;
for (const p of on) for (const q of flatten(p.loops[0], 1e-3)) used = Math.max(used, q.x);
sheetsOut.push({ used: Math.min(roll ? Infinity : W0, used + margin), area: on.reduce((s, p) => s + p.area, 0) });
}
const area = out.reduce((s, p) => s + p.area, 0);
const sheetArea = roll ? (sheetsOut[0]?.used || 0) * H0 : nSheets * W0 * H0;
const unplaced = best.unplaced.concat(bad.flatMap((k) => Array.from({ length: Math.max(1, Math.floor(k.part.qty ?? 1)) }, (_, c) => ({ part: k.index, id: k.part.id, name: k.part.name, copy: c, why: 'bad_shape' }))));
return {
placed: out, unplaced, sheets: sheetsOut, length: roll ? (sheetsOut[0]?.used || 0) : (sheetsOut.at(-1)?.used || 0),
efficiency: sheetArea > 0 ? area / sheetArea : 0, area, res, tries: triesDone, order: best.label, roll, ms: now() - t0,
Distance between two edges
64-bit
The shortest distance between two segments, 0 when they cross.
0 when the cross-product signs differ on both segments; else min of the four end-point-to-segment distances
The crossing test uses the signs of 64-bit cross products with no tolerance; it is not an exact predicate. The point distances use a clamped projection and Math.hypot.
addons/cabinetcraft/lib/nest/nest.js
lines 464 to 471
CadCraft 0.8.2
const segDist = (a, b, c, d) => {
// the shortest distance between segments ab and cd (0 when they cross)
const cross = (o, p, q) => (p.x - o.x) * (q.y - o.y) - (p.y - o.y) * (q.x - o.x);
const d1 = cross(a, b, c), d2 = cross(a, b, d), d3 = cross(c, d, a), d4 = cross(c, d, b);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return 0;
const pt = (p, s, e) => { const dx = e.x - s.x, dy = e.y - s.y, L = dx * dx + dy * dy; let t = L ? ((p.x - s.x) * dx + (p.y - s.y) * dy) / L : 0; t = Math.max(0, Math.min(1, t)); return Math.hypot(s.x + t * dx - p.x, s.y + t * dy - p.y); };
return Math.min(pt(a, c, d), pt(b, c, d), pt(c, a, b), pt(d, a, b));
};
Re-check of a nest
64-bit
Checks that no two placed parts overlap or come closer than the spacing, and that all lie inside the margins.
outside when the bounding box passes a margin by more than eps; overlap when d ≤ eps or one part's first point is inside the other; close when d < gap − eps
Works on the outlines flattened with a sag of 0.001, not on the raster. Chords lie inside convex arcs, so a distance to an arc edge can read up to 0.001 more than the true one per arc. eps is 1e-6, absolute.
addons/cabinetcraft/lib/nest/nest.js
lines 478 to 509
CadCraft 0.8.2
/** The exact re-check of a result (see the header). */
export function checkNest(result, sheet = {}, { spacing = 0, eps = 1e-6 } = {}) {
const problems = [];
const margin = Math.max(0, Number(sheet.margin) || 0);
const roll = !(Number(sheet.w) > 0) || !Number.isFinite(Number(sheet.w));
const W = roll ? Infinity : Number(sheet.w), H = Number(sheet.h);
const items = result.placed.map((p) => { const polys = p.loops.map((l) => flatten(l, 1e-3)); return { p, polys, bb: bboxOf(polys) }; });
for (const it of items) {
const { bb } = it;
if (bb.x0 < margin - eps || bb.y0 < margin - eps || bb.y1 > H - margin + eps || bb.x1 > W - margin + eps) problems.push({ kind: 'outside', a: it.p });
}
const obstacles = (sheet.obstacles || []).map((loops) => { const polys = loops.map((l) => flatten(l, 1e-3)); return { p: { sheet: 0, obstacle: true }, polys, bb: bboxOf(polys) }; });
const all = items.concat(obstacles);
for (let i = 0; i < items.length; i++) {
for (let j = i + 1; j < all.length; j++) {
const A = items[i], B = all[j];
if (A.p.sheet !== B.p.sheet) continue;
const gap = B.p.obstacle && sheet.obstacleGap != null ? Number(sheet.obstacleGap) || 0 : spacing;
if (A.bb.x1 + gap < B.bb.x0 - eps || B.bb.x1 + gap < A.bb.x0 - eps || A.bb.y1 + gap < B.bb.y0 - eps || B.bb.y1 + gap < A.bb.y0 - eps) continue;
let dmin = Infinity;
for (const pa of A.polys) for (let a = 0; a < pa.length && dmin > 0; a++) {
const s = pa[a], e = pa[(a + 1) % pa.length];
for (const pb of B.polys) for (let b = 0; b < pb.length; b++) { const d = segDist(s, e, pb[b], pb[(b + 1) % pb.length]); if (d < dmin) { dmin = d; if (!d) break; } }
}
// no edge closer than the spacing: still wrong when one lies inside the other's region
const inside = inRegion(A.polys[0][0], B.polys) || inRegion(B.polys[0][0], A.polys);
if (dmin <= eps || inside) problems.push({ kind: 'overlap', a: A.p, b: B.p });
else if (dmin < gap - eps) problems.push({ kind: 'close', a: A.p, b: B.p, d: dmin });
}
}
return problems;
}
Lines and arcs joined into loops
64-bit
Joins separate line and arc pieces into closed loops where their ends meet.
ends meet when their distance ≤ 1.5 × tol
The loop keeps each piece's own end point as given; ends that meet within the tolerance are not averaged, so a loop can carry a gap of up to 1.5 × tol at a joint. A reversed piece has its bulge negated.
addons/cabinetcraft/lib/nest/nest.js
lines 513 to 545
CadCraft 0.8.2
/** Pieces {a: [x, y], b: [x, y], bulge} (and whole circles) → closed loops with bulges, ends joined within tol. */
function chain(pieces, tol) {
const loops = [], open = [];
const key = (p) => Math.round(p[0] / tol) + ',' + Math.round(p[1] / tol);
const left = pieces.slice();
const ends = new Map();
const index = () => { ends.clear(); left.forEach((s, i) => { for (const [p, end] of [[s.a, 0], [s.b, 1]]) { const k = key(p); if (!ends.has(k)) ends.set(k, []); ends.get(k).push([i, end]); } }); };
const near = (p, q) => Math.hypot(p[0] - q[0], p[1] - q[1]) <= tol * 1.5;
while (left.length) {
index();
const first = left.shift();
const pts = [{ x: first.a[0], y: first.a[1], b: first.bulge || 0 }];
let cur = first.b;
const used = new Set();
for (let guard = 0; guard < 100000; guard++) {
if (near(cur, first.a)) break;
// the next piece touching cur (search near keys too)
let hit = -1, flip = false;
for (let i = 0; i < left.length && hit < 0; i++) {
if (used.has(i)) continue;
if (near(left[i].a, cur)) { hit = i; flip = false; } else if (near(left[i].b, cur)) { hit = i; flip = true; }
}
if (hit < 0) break;
used.add(hit);
const s = left[hit];
pts.push({ x: cur[0], y: cur[1], b: flip ? -(s.bulge || 0) : (s.bulge || 0) });
cur = flip ? s.a : s.b;
}
for (const i of [...used].sort((a, b) => b - a)) left.splice(i, 1);
if (near(cur, first.a) && pts.length >= 2) loops.push(pts); else open.push(pts);
}
return { loops, open };
}
Bulge of an arc
64-bit
The bulge value of an arc from its sweep in degrees.
bulge = tan(sweep × π ÷ 180 ÷ 4)
One multiplication by π ÷ 180, a division by 4 and one tangent.
Turns line, arc, circle and polyline pieces of a flat pattern into closed loops with bulges.
arc end = c + r (cos a, sin a); sweep = (a₁ − a₀) mod 360; circle = two bulges of 1
Arc end points are recomputed from center, radius and angle in degrees. A sweep within 1e-9 of 0 or 360 is a full circle. Ends are joined with tol = 1e-4 by default, an absolute value.
addons/cabinetcraft/lib/nest/nest.js
lines 549 to 565
CadCraft 0.8.2
/** PartCraft's flat pattern pieces → loops (see the header). */
export function loopsFromSegs(segs, tol = 1e-4) {
const pieces = [], loops = [];
for (const s of segs || []) {
if (s.type === 'line') pieces.push({ a: s.a, b: s.b, bulge: 0 });
else if (s.type === 'arc') {
let sw = ((s.a1 - s.a0) % 360 + 360) % 360;
if (sw < 1e-9) sw = 360;
const P = (deg) => [s.c[0] + s.r * Math.cos(deg * Math.PI / 180), s.c[1] + s.r * Math.sin(deg * Math.PI / 180)];
if (sw >= 360 - 1e-9) { loops.push(circleLoop(s.c, s.r)); continue; }
pieces.push({ a: P(s.a0), b: P(s.a0 + sw), bulge: bulgeOfArc(sw) });
} else if (s.type === 'circle') loops.push(circleLoop(s.c, s.r));
else if (s.type === 'poly' && s.pts?.length >= 2) for (let i = 0; i + 1 < s.pts.length; i++) pieces.push({ a: s.pts[i], b: s.pts[i + 1], bulge: 0 });
}
const r = chain(pieces, tol);
return { loops: loops.concat(r.loops), open: r.open.length };
}
Arcs and ellipses read from DXF
64-bit
Reads ARC and ELLIPSE entities into pieces or loops.
ellipse: n = max(8, ⌈sweep ÷ (2π ÷ 96)⌉) points at equal parameter steps
DXF numbers are read with unary plus into 64-bit. An arc keeps its exact shape as a bulge. An ellipse becomes straight chords, 96 for a full one, with no sag control; the chord polygon's area is about 0.07 % below the ellipse's.
addons/cabinetcraft/lib/nest/nest.js
lines 636 to 648
CadCraft 0.8.2
else if (e.type === 'ARC') {
const c = [num(e.g, 10), num(e.g, 20)], r = num(e.g, 40), a0 = num(e.g, 50), a1 = num(e.g, 51);
let sw = ((a1 - a0) % 360 + 360) % 360; if (sw < 1e-9) sw = 360;
const P = (deg) => [c[0] + r * Math.cos(deg * Math.PI / 180), c[1] + r * Math.sin(deg * Math.PI / 180)];
if (sw >= 360 - 1e-9) loops.push(circleLoop(c, r)); else pieces.push({ a: P(a0), b: P(a0 + sw), bulge: bulgeOfArc(sw) });
} else if (e.type === 'ELLIPSE') {
const c = [num(e.g, 10), num(e.g, 20)], mx = num(e.g, 11), my = num(e.g, 21), ratio = num(e.g, 40, 1), s0 = num(e.g, 41, 0), s1 = num(e.g, 42, TAU);
const L = Math.hypot(mx, my), ux = mx / (L || 1), uy = my / (L || 1);
let sw = s1 - s0; if (sw <= 0) sw += TAU;
const n = Math.max(8, Math.ceil(sw / (TAU / 96)));
const pts = [];
for (let m = 0; m <= n; m++) { const a = s0 + sw * m / n, ex = L * Math.cos(a), ey = L * ratio * Math.sin(a); pts.push([c[0] + ux * ex - uy * ey, c[1] + uy * ex + ux * ey]); }
if (Math.abs(sw - TAU) < 1e-9) loops.push(pts.slice(0, -1).map(([x, y]) => ({ x, y, b: 0 }))); else for (let m = 0; m + 1 < pts.length; m++) pieces.push({ a: pts[m], b: pts[m + 1], bulge: 0 });
Joining tolerance for a DXF
64-bit
The distance within which loose line and arc ends of a DXF are joined.
tol = max(1e-6, 1e-7 × largest absolute coordinate)
The tolerance scales with the drawing's largest coordinate, with a floor of 1e-6.
addons/cabinetcraft/lib/nest/nest.js
lines 652 to 654
CadCraft 0.8.2
let ext = 0;
for (const p of pieces) ext = Math.max(ext, Math.abs(p.a[0]), Math.abs(p.a[1]), Math.abs(p.b[0]), Math.abs(p.b[1]));
const ch = chain(pieces, Math.max(1e-6, ext * 1e-7));
Outlines and their holes
64-bit
Sorts loops into parts: an outline and the holes directly inside it.
A loop is inside another when two of its points, the first and the middle one of its flattened outline, pass the even-odd test. Loops with area of 1e-12 or less are dropped, an absolute value. Even nesting depth makes an outline, odd a hole.
addons/cabinetcraft/lib/nest/nest.js
lines 568 to 583
CadCraft 0.8.2
/** Loops → parts: an outline and the holes directly inside it (even depth = an outline). */
export function partsFromLoops(loops) {
const items = loops.map((l) => ({ l, poly: flatten(l, 1e-3), area: Math.abs(loopArea(l)) })).filter((x) => x.area > 1e-12);
items.sort((a, b) => b.area - a.area);
for (const it of items) {
it.depth = 0; it.parent = null;
for (const o of items) {
if (o === it || o.area <= it.area) continue;
if (inRegion(it.poly[0], [o.poly]) && inRegion(it.poly[Math.floor(it.poly.length / 2)], [o.poly])) { it.depth++; if (!it.parent || o.area < it.parent.area) it.parent = o; }
}
}
const parts = [];
for (const it of items) if (it.depth % 2 === 0) { it.part = { loops: [it.l] }; parts.push(it.part); }
for (const it of items) if (it.depth % 2 === 1 && it.parent?.part) it.parent.part.loops.push(it.l);
return parts;
}
Numbers written to the DXF
64-bit
Formats every coordinate, bulge and text height of the nest DXF.
text = v.toFixed(6) with trailing zeros removed; |v| < 1e-12 written as 0
Coordinates and bulges are written with 6 decimals, so the file holds 0.000001 of the job unit rather than the full 64-bit value. A value that is not finite is written as 0.
offset₀ = 0; offsetₛ₊₁ = offsetₛ − (Hₛ + gap), gap = 0.1 × tallest sheet by default
Offsets are a running difference. Each part's y has its sheet's offset added before the 6-decimal formatting, so parts on later sheets are written relative to a larger number.
addons/cabinetcraft/lib/nest/nest.js
lines 671 to 674
CadCraft 0.8.2
const g = gap ?? H * 0.1;
const th = textHeight ?? Math.max(H / 150, units === 'in' ? 0.1 : 2.5);
const offs = [];
{ let y = 0; for (let s = 0; s < nSheets; s++) { offs.push(y); y -= dims[s].H + g; } }
In detail
Method
Raster nesting: each part and turn drawn once on a grid, grown by the spacing in whole cells, placed where the used length stays shortest; several piece orders tried within a time limit. Area by the shoelace sum plus r² (θ − sin θ) ÷ 2 per arc. Re-check by segment-to-segment distances on the flattened outlines.
Number types
64-bit numbers for geometry; Uint8Array and Int32Array hold grid cells and cell intervals, which are indexes, not measured values.
Tolerances
Default res = (sheet width − 2 × margin) ÷ 750, at most a quarter of the smallest part's width, at least 1e-6. Sag for the raster = min(res ÷ 8, 0.1); sag 0.001 for sizes and the re-check. Re-check eps = 1e-6 absolute. Chain tolerance for DXF pieces = max(1e-6, 1e-7 × largest coordinate). Full-circle tests 1e-9.
Checked by
tools/nest/test.mjs runs lib/nest/nest.js, which was byte-identical to this file at the review. It compares loopArea of a two-bulge circle with π r² and of a half-circle bulge with π r² ÷ 2 at a relative 1e-9, runs checkNest on nests with and without spacing, and reads a written DXF back and compares the total area at a relative 1e-6.
Limits
Parts sit on the res grid, so a nest is not the tightest possible and gaps are at least the spacing plus twice the sag. A full ellipse read from DXF becomes 96 chords. The written DXF has 6 decimals for coordinates and bulges.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.