Updated

nest

A true-shape nesting engine: it lays out parts on a sheet for laser and CNC cutting so that as little material as possible goes to waste.

Less scrap

A nesting engine that packs irregular parts onto sheets for cutting, written in functional TypeScript on a WebAssembly geometry core. It runs in Node, in the browser and across worker pools.

  1. SVG
  2. Offset
  3. No-fit polygons
  4. Place
  5. Evolve

The problem

Before a laser, CNC router or plasma cutter cuts parts from a sheet, someone has to lay them out. Every gap between parts is material that ends up in the bin, so the goal is to fit the parts as tightly as possible, on as few sheets as possible.

a part inside another part's hole
True-shape nesting: parts keep their real outlines, rotate, and fill each other's holes.

Rectangles are easy. Real parts are not: they have curves, notches and holes, a small part can sit inside a big part's cutout, and every part can turn. The number of possible layouts explodes with each part added, so no program can try them all. A nester has to answer two questions fast, over and over: where can this part legally go, and which order and rotation of parts gives the tightest layout?

What I built

nest is an engine you call from code. It takes an SVG of parts and sheets, returns a layout as SVG or JSON, and checks it for overlaps before handing it back. The whole engine is a pure state machine: a run can be paused, saved as plain data and continued later, and the same seed always gives the same layout.

Shapes

  • Curves, holes and parts nested inside other parts' holes.
  • Several sheet sizes in one job, and exact-fit tiles that touch edge to edge.
  • Spacing for the cutter's kerf, applied to every part and sheet.

Shop floor

  • Resume a job after a partial cut: parts already cut stay exactly where they are.
  • Lock parts in place, or close a sheet so nothing more goes on it.
  • A browser demo and a documentation site.
360tests in 35 files, run in about 6 seconds
4,941lines of engine code in 44 modules, no classes
2runtime dependencies: Clipper2 WASM and an XML parser
81 KBgzipped WebAssembly geometry core
50,000no-fit polygons kept in a cache shared between runs
120research papers surveyed, 33 CAD/CAM tools compared

The no-fit polygon

The first question, where a part can go, rests on one shape. Slide part B around fixed part A, keeping them touching, and trace where B's reference point goes. Inside that outline B overlaps A; on it, they touch. nest computes it directly as a Minkowski sum instead of simulating the slide.

A B touching A B's reference point ● no-fit polygon inside: overlap on the line: touching outside: free NFP = A ⊕ (−B)
Every place B can legally go is a vertex of the sheet's free region: the inner-fit area minus the union of these outlines.

The second question, which order and rotation, is answered by a genetic algorithm that keeps breeding better orderings and placing them with the no-fit polygons.

The engine

  1. Read the SVG

    Paths, polygons, rects, circles and ellipses, transforms flattened, curves split into segments by a flatness test. A ring inside a ring is a hole; a ring inside a hole is a new part.

    • @rgrove/parse-xml
    • adaptive curve flattening

  2. Offset for the kerf

    Parts grow and sheets shrink by half the spacing, on Clipper2's integer grid at six decimal places.

    • Clipper2 InflatePaths64
    • WebAssembly

  3. No-fit polygons cached

    A Minkowski sum per pair of parts and rotation, stored as one signed region: blocked area positive, pockets negative, so a single subtraction gives the free space, holes included. A small contact tolerance lets exact-fit parts touch.

    • Clipper2 MinkowskiSum64
    • signed regions

  4. Place

    Parts go down one at a time. Each vertex of the free region is a candidate, scored by gravity (keep the layout narrow and low), bounding box or convex hull.

    • gravity scoring
    • locked parts
    • closed sheets

  5. Evolve

    A genetic algorithm searches the order and rotation of the parts: population 10, 10% mutation, rank selection, and the best layout always survives. The random seed is part of the state, so the same seed gives the same layout.

    • seeded RNG
    • island model
    • worker pools

  6. Score and check

    Fitness is sheets used, plus how compact the last sheet is, plus a penalty for every part left out. A validator checks the final layout for overlaps and containment.

    • SVG or JSON out
    • validateLayout

Benchmark

Thirteen standard sets from ESICUP, the shared benchmark of the cutting-and-packing research community. Each set is packed into a strip, and the score is density: how much of the used strip the parts cover. nest is measured against the two strongest open-source solvers, PackingSolver and sparrow.

  • nest
  • PackingSolver
  • sparrow
  1. albano 84.3%
  2. blaz1 77.2%
  3. dagli 81.0%
  4. fu 89.7%
  5. jakobs1 85.2%
  6. jakobs2 74.2%
  7. mao 79.5%
  8. marques 85.4%
  9. shapes0 61.4%
  10. shapes1 66.5%
  11. shirts 85.3%
  12. swim 68.2%
  13. trousers 87.8%
  14. Mean 78.9%
Density per benchmark set; the number on the right is nest's. nest: one seed, 120 seconds on one thread. sparrow: the expected result of 20-minute runs on three threads. Giving nest five times longer adds 0.3–1.1 points.
78.9%nest's mean density, from 61% on shapes0 to 90% on fu
2 of 13sets where nest beats PackingSolver: jakobs1 and mao
2.6 ptclosest to sparrow, on fu; 6.5 points behind on average

Speed

Layouts are evaluated in parallel on a pool of workers, in Node or in the browser, and the result is the same for any number of workers.

  • 1 worker1×
  • 4 Node workers3.1×
  • 10 browser workers4.1×

All measurements come from one heavily loaded laptop, so read them as ratios rather than absolute figures.

Built with

  • TypeScript
  • Clipper2
  • WebAssembly
  • Web Workers
  • Vitest
  • Vite
  • VitePress

Started