Works out the usable material left on a plate after a nest, keeps it as numbered remnants with their size and area, and nests the next job on remnants first.
How the precision is kept
What the parts occupy is painted on a grid whose cell is the plate's smaller side ÷ 600 unless the caller gives one. The free cells are joined into regions and traced into outlines, so a remnant's outline, width, height and area are no finer than about one grid cell. The occupied area is grown by one extra cell so that the outline stays inside the true leftover, and checkRemnants re-checks that on the polygons. Sums of areas and the efficiency are plain 64-bit arithmetic.
Calculations under this policy
13 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.
A stock list with every number checked and each remnant's area, width and height worked out again from its outline.
area = regionArea(loops); w = x₁ − x₀; h = y₁ − y₀ of the outline (arcs flattened to a sag of 0.001); outline moved so its box corner is (0, 0)
The area, width and height stored in the file are not trusted: they are recomputed from the outline in 64-bit numbers. Coordinates must be within ±1e9. Moving the outline to its box corner subtracts the corner from every point.
addons/apparel/lib/nest/nest-stock.js
lines 62 to 90
CadCraft 0.8.2
export function cleanStock(obj) {
const out = newStock();
if (!obj || typeof obj !== 'object' || obj.format !== STOCK_FORMAT) return out;
const seen = new Set();
let max = 0;
for (const it of (Array.isArray(obj.items) ? obj.items : []).slice(0, LIMITS.items)) {
const number = fin(it?.number, 1, 9999999);
if (number === null || !Number.isInteger(number) || seen.has(number)) continue;
const loops = (Array.isArray(it.loops) ? it.loops : []).slice(0, LIMITS.loops).map(cleanLoop);
if (!loops.length || loops.some((l) => !l)) continue;
const area = regionArea(loops);
if (!(area > 0)) continue;
const b = boxOf(loops);
// local frame: the lower left corner of the bounding box is the origin
const moved = b.x0 !== 0 || b.y0 !== 0 ? loops.map((l) => l.map((p) => ({ ...p, x: p.x - b.x0, y: p.y - b.y0 }))) : loops;
seen.add(number);
max = Math.max(max, number);
const thickness = fin(it.thickness, 0, 1e4);
out.items.push({
id: stockId(number), number, kind: 'remnant', material: txt(it.material), thickness: thickness ?? 0,
w: b.x1 - b.x0, h: b.y1 - b.y0, loops: moved, area,
created: /^\d{4}-\d{2}-\d{2}$/.test(it.created) ? it.created : '',
source: { job: txt(it.source?.job), sheet: Math.max(0, Math.floor(fin(it.source?.sheet, 0, 1e6) ?? 0)), ...(Number.isInteger(it.source?.parent) ? { parent: it.source.parent } : {}) },
status: STATUSES.includes(it.status) ? it.status : 'available', usedIn: txt(it.usedIn), note: txt(it.note, 200),
});
}
out.next = Math.max(max + 1, Math.floor(fin(obj.next, 1, 1e7) ?? 1));
return out;
}
Stock totals
64-bit
The number of available remnants and their total area per material and thickness.
area = Σ remnant areas
A plain sum in list order. Remnants are grouped by the exact material text and thickness value.
addons/apparel/lib/nest/nest-stock.js
lines 95 to 105
CadCraft 0.8.2
export function stockSummary(stock) {
const map = new Map();
for (const it of stock.items) {
if (it.status !== 'available') continue;
const k = it.material + '|' + it.thickness;
const r = map.get(k) || { material: it.material, thickness: it.thickness, count: 0, area: 0 };
r.count++; r.area += it.area;
map.set(k, r);
}
return [...map.values()].sort((a, b) => a.material.localeCompare(b.material) || a.thickness - b.thickness);
}
Numbers in the stock CSV
64-bit
The text of a thickness, width, height or area in the exported stock list.
round(v × 10ᵈ) ÷ 10ᵈ; d = 3 for thickness, 2 for width and height, 1 for area
Rounding for the exported CSV only; the stock list itself keeps the unrounded values.
Marks which cells of the plate are free after the parts, the spacing and narrow strips are taken out.
cell = min(w, h) ÷ 600; sag = min(cell ÷ 8, 0.1); grow = ⌈(spacing + 2·sag) ÷ cell − 1e-9⌉ + 1 cells; strips narrower than minWidth removed by an opening of ⌊minWidth ÷ cell ÷ 2⌋ cells
The occupied area is grown by the spacing, the arc sag and one more cell, always rounding up, so the free area errs on the small side. The 1e-9 is taken off a count of cells.
addons/apparel/lib/nest/nest-stock.js
lines 241 to 253
CadCraft 0.8.2
const res = Number(resIn) > 0 ? Number(resIn) : Math.max(Math.min(w, h) / 600, 1e-6);
const cols = Math.max(1, Math.ceil(w / res - 1e-9)), rows = Math.max(1, Math.ceil(h / res - 1e-9));
const sag = Math.min(res / 8, 0.1);
const occ = new Uint8Array(cols * rows);
for (const p of placed) paint(occ, cols, rows, [flatten(p.loops[0], sag)], res); // a part's holes are its own: the slug is not stock
for (const loops of region.obstacles || []) paint(occ, cols, rows, loops.map((l) => flatten(l, sag)), res);
const grow = Math.ceil((Math.max(0, spacing) + 2 * sag) / res - 1e-9) + 1; // the spacing, the arc sag and one more cell
const blocked = dilateGrid(occ, cols, rows, grow);
let free = invert(blocked);
const mw = minWidth ?? Math.min(w, h) / 20;
const k = Math.max(0, Math.floor(mw / res / 2 - 1e-9));
if (k > 0) free = dilateGrid(invert(dilateGrid(invert(free), cols, rows, k)), cols, rows, k); // an opening: strips narrower than minWidth go
for (let i = 0; i < free.length; i++) if (blocked[i]) free[i] = 0;
Growing a region on the grid
Exact
Marks every cell within k cells of a marked cell, along rows and then columns.
Whole-number prefix sums in an Int32Array over a grid of 0 and 1 flags; no rounding is involved. The reach is a square of k cells, not a circle, so diagonals are grown further than k.
addons/apparel/lib/nest/nest-stock.js
lines 121 to 140
CadCraft 0.8.2
/** Where an axis-aligned box filter reaches: out[i] = 1 when any cell within k of i along the line is set (clipped to the grid). */
function dilateGrid(g, cols, rows, k) {
if (k <= 0) return g.slice();
const tmp = new Uint8Array(cols * rows), out = new Uint8Array(cols * rows);
// along j for each column
const pre = new Int32Array(Math.max(cols, rows) + 1);
for (let i = 0; i < cols; i++) {
const o = i * rows;
pre[0] = 0;
for (let j = 0; j < rows; j++) pre[j + 1] = pre[j] + g[o + j];
for (let j = 0; j < rows; j++) tmp[o + j] = pre[Math.min(rows, j + k + 1)] - pre[Math.max(0, j - k)] > 0 ? 1 : 0;
}
// along i for each row
for (let j = 0; j < rows; j++) {
pre[0] = 0;
for (let i = 0; i < cols; i++) pre[i + 1] = pre[i] + tmp[i * rows + j];
for (let i = 0; i < cols; i++) out[i * rows + j] = pre[Math.min(cols, i + k + 1)] - pre[Math.max(0, i - k)] > 0 ? 1 : 0;
}
return out;
}
Outline of a free region
Exact
The boundary of one connected region of free cells, as loops on grid corners.
Works on whole-number grid coordinates only. Where two cells touch at a corner, the turn is chosen by the sign of a cross product of whole numbers.
addons/apparel/lib/nest/nest-stock.js
lines 157 to 195
CadCraft 0.8.2
/** The boundary loops of one connected region (cell mask), counter-clockwise outer, clockwise holes, as grid-corner points. */
function traceRegion(mask, cols, rows) {
const edges = []; // [x0, y0, x1, y1]
const inM = (i, j) => i >= 0 && i < cols && j >= 0 && j < rows && mask(i, j);
for (let i = 0; i < cols; i++) for (let j = 0; j < rows; j++) {
if (!mask(i, j)) continue;
if (!inM(i, j - 1)) edges.push([i, j, i + 1, j]);
if (!inM(i + 1, j)) edges.push([i + 1, j, i + 1, j + 1]);
if (!inM(i, j + 1)) edges.push([i + 1, j + 1, i, j + 1]);
if (!inM(i - 1, j)) edges.push([i, j + 1, i, j]);
}
const key = (x, y) => x * (rows + 2) + y;
const out = new Map();
edges.forEach((e, k) => { const q = key(e[0], e[1]); if (!out.has(q)) out.set(q, []); out.get(q).push(k); });
const used = new Uint8Array(edges.length);
const loops = [];
for (let k0 = 0; k0 < edges.length; k0++) {
if (used[k0]) continue;
const loop = [];
let k = k0;
for (let guard = 0; guard < edges.length + 2; guard++) {
used[k] = 1;
const e = edges[k];
loop.push([e[0], e[1]]);
const cand = (out.get(key(e[2], e[3])) || []).filter((q) => !used[q] || q === k0);
if (!cand.length) break;
let next = cand[0];
if (cand.length > 1) { // a corner where two cells touch: turn left, round the same cell
const dx = e[2] - e[0], dy = e[3] - e[1];
const left = (q) => { const f = edges[q], ex = f[2] - f[0], ey = f[3] - f[1]; return dx * ey - dy * ex; }; // > 0: a left turn
next = cand.slice().sort((a, b) => left(b) - left(a))[0];
}
if (next === k0) break;
k = next;
}
if (loop.length >= 4) loops.push(loop);
}
return loops;
}
Removing points on a straight run
Exact
Drops grid points that lie between their neighbors on a straight line.
(b − a) × (c − b) ≠ 0 → keep
The cross product is of whole-number grid coordinates and is compared with exactly 0, which is exact for whole numbers of this size.
addons/apparel/lib/nest/nest-stock.js
lines 199 to 207
CadCraft 0.8.2
function dropCollinear(pts) {
const out = [];
const n = pts.length;
for (let i = 0; i < n; i++) {
const a = pts[(i + n - 1) % n], b = pts[i], c = pts[(i + 1) % n];
if ((b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]) !== 0) out.push(b);
}
return out;
}
Simplifying an outline
64-bit
Removes outline points within half a cell of the simplified line.
d = |(r − p) × (q − p)| ÷ |q − p|; kept when d > tol
Douglas–Peucker on the closed loop, split at point 0 and the point farthest from it. Kept points are not moved. A chord of zero length divides by 1 instead.
addons/apparel/lib/nest/nest-stock.js
lines 209 to 230
CadCraft 0.8.2
/** Douglas–Peucker on a closed loop, tolerance tol (it is split at the two vertices furthest apart). */
function simplifyClosed(pts, tol) {
const n = pts.length;
if (n <= 4) return pts;
let a = 0, b = 0, best = -1;
for (let i = 1; i < n; i++) { const d = Math.hypot(pts[i][0] - pts[0][0], pts[i][1] - pts[0][1]); if (d > best) { best = d; b = i; } }
const keep = new Uint8Array(n);
keep[a] = keep[b] = 1;
const seg = (lo, hi) => { // lo < hi in the unrolled index, wrapped on read
const stack = [[lo, hi]];
while (stack.length) {
const [s, e] = stack.pop();
if (e - s < 2) continue;
const p = pts[s % n], q = pts[e % n], dx = q[0] - p[0], dy = q[1] - p[1], L = Math.hypot(dx, dy) || 1;
let far = -1, fi = -1;
for (let i = s + 1; i < e; i++) { const r = pts[i % n]; const d = Math.abs((r[0] - p[0]) * dy - (r[1] - p[1]) * dx) / L; if (d > far) { far = d; fi = i; } }
if (far > tol) { keep[fi % n] = 1; stack.push([s, fi], [fi, e]); }
}
};
seg(a, b); seg(b, a + n);
return pts.filter((_, i) => keep[i]);
}
Remnant outline, size and area
64-bit
Each leftover region as an outline with holes, its area and its bounding size.
point = grid corner × cell, clamped to the plate; simplified by cell ÷ 2; area = regionArea(outline and holes); kept when area ≥ minArea (2 percent of the plate by default)
The outline's points are whole numbers of cells times the cell size, so the remnant follows the grid and not the parts' true edges. The area is computed from the simplified outline in 64-bit numbers.
addons/apparel/lib/nest/nest-stock.js
lines 279 to 292
CadCraft 0.8.2
const raw = traceRegion((i, j) => label[i * rows + j] === comp.id, cols, rows);
const loops = [];
for (const lp of raw) {
const pts = dropCollinear(lp.map(([x, y]) => [x, y])).map(([x, y]) => [x * res, y * res]);
if (pts.length < 3) continue;
const simp = simplifyClosed(pts, res * 0.5);
if (simp.length < 3) continue;
loops.push(simp.map(([x, y]) => ({ x: Math.min(w, Math.max(0, x)), y: Math.min(h, Math.max(0, y)) })));
}
if (!loops.length) continue;
loops.sort((a, b) => Math.abs(loopArea(b)) - Math.abs(loopArea(a)));
const outline = loops[0], holes = loops.slice(1);
const area = regionArea([outline, ...holes]);
if (!(area >= minA)) continue;
Does a remnant match the job
64-bit
Whether a remnant has the job's material and thickness.
|thickness − wanted| < 1e-6
The thickness tolerance is 1e-6 of the caller's unit, absolute. The material is compared as exact text.
Marks the remnants a job used and adds the ones it leaves, numbered.
stored outline = outline − (x₀, y₀); w, h and area as found by leftovers
Each new remnant's points are moved to its own box corner by one subtraction. After the stock item is made, the function overwrites the job's own remnant height with the label's text height (r.h = min(label height, r.h)), so a later reading of that job record gets the label height.
addons/apparel/lib/nest/nest-stock.js
lines 396 to 423
CadCraft 0.8.2
/** Commit a job to the stock (see the header). */
export function applyJob(stock, job, { name = '', date = '', saveRemnants = true, material = '', thickness = 0 } = {}) {
const next = cleanStock(JSON.parse(JSON.stringify(stock)));
const used = [];
const added = [];
for (const u of job.uses) {
const it = next.items.find((x) => x.id === u.id);
if (it) { it.status = 'used'; it.usedIn = name; used.push(it.id); }
}
if (saveRemnants) {
for (const r of job.remnants) {
const number = next.next++;
const b = { x0: r.x0, y0: r.y0 };
const loops = r.loops.map((l) => l.map((p) => ({ ...p, x: p.x - b.x0, y: p.y - b.y0 })));
const it = {
id: stockId(number), number, kind: 'remnant', material, thickness, w: r.w, h: r.h, loops, area: r.area, created: date,
source: { job: name, sheet: r.sheet, ...(r.parent ? { parent: r.parent } : {}) }, status: 'available', usedIn: '', note: '',
};
next.items.push(it);
added.push(it);
r.text = it.id; // the number in the job's drawing
r.at = { x: r.label.x, y: r.label.y };
r.h = Math.min(r.label.h, r.h);
r.id = it.id;
}
}
return { stock: next, added, used };
}
Exact re-check of remnants against parts
64-bit
Confirms on the polygons that no remnant touches a placed part and that the spacing is kept.
distance between every pair of edges; overlap when ≤ 1e-6 or one contains the other's first point; too close when < spacing − 1e-6
Works on the outlines with arcs flattened to a sag of 0.001, not on the grid. The 1e-6 is absolute in the caller's unit.
addons/apparel/lib/nest/nest-stock.js
lines 425 to 450
CadCraft 0.8.2
/** The exact re-check of a job's remnants against its parts (polygons, not the raster). [] = good. */
export function checkRemnants(job, { spacing = 0, eps = 1e-6 } = {}) {
const problems = [];
const segD = (a, b, c, d) => {
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));
};
const inside = (p, polys) => { let o = false; for (const pl of polys) for (let i = 0, j = pl.length - 1; i < pl.length; j = i++) { const a = pl[i], b = pl[j]; if ((a.y > p.y) !== (b.y > p.y) && p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x) o = !o; } return o; };
for (const r of job.remnants) {
const rp = r.loops.map((l) => flatten(l, 1e-3));
const area = regionArea(r.loops);
if (!(area > 0)) problems.push({ kind: 'empty', remnant: r });
for (const p of job.placed.filter((q) => q.sheet === r.sheet)) {
const pp = [flatten(p.loops[0], 1e-3)];
let dmin = Infinity;
for (const a of rp) for (let i = 0; i < a.length && dmin > 0; i++) for (const b of pp) for (let j = 0; j < b.length; j++) { const d = segD(a[i], a[(i + 1) % a.length], b[j], b[(j + 1) % b.length]); if (d < dmin) { dmin = d; if (!d) break; } }
const overlap = dmin <= eps || inside(rp[0][0], pp) || inside(pp[0][0], rp);
if (overlap) problems.push({ kind: 'overlap', remnant: r, part: p });
else if (dmin < spacing - eps) problems.push({ kind: 'close', remnant: r, part: p, d: dmin });
}
}
return problems;
}
In detail
Method
Raster of the occupied area grown by the spacing; morphological opening to drop narrow strips; 4-connected regions; boundary tracing on grid corners; Douglas–Peucker simplification by half a cell; a polygon re-check (checkRemnants).
Number types
64-bit numbers for outlines and areas; Uint8Array and Int32Array grids hold flags, counts and labels.
Tolerances
Cell = min(w, h) ÷ 600, at least 1e-6. Arc sag = min(cell ÷ 8, 0.1). Occupied area grown by ⌈(spacing + 2·sag) ÷ cell⌉ + 1 cells. Strips narrower than min(w, h) ÷ 20 and regions under 2 percent of the plate are scrap by default. Thickness matches within 1e-6. checkRemnants uses 1e-6 for touching. CSV: thickness 3 decimals, width and height 2, area 1.
Checked by
tools/nest/test-stock.mjs calls leftovers with rectangles and a circle on a 1000 × 600 plate and checks the number and area of the remnants; it runs the library copy, which is byte-identical to this file.
Limits
Next to a part the outline stands back by the spacing plus about two cells. Only plates leave remnants; a roll does not.
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.