Nesting · bin packing under real constraints
Nesting looks like bin packing until the material starts making rules. The roll is a fixed width and unbounded length. Pieces must run along the grain, so most of them get two rotations, not four. Everything needs a gap around it. Each constraint costs metres, and this page shows you how many — turn one off and watch the marker move.
Bottom-left fill with a skyline accelerator, on a raster occupancy grid. Pieces are grown by the spacing first — that gap is a polygon offset, the same operation as a seam allowance — then rasterised and dropped as far left, then as low, as they will go.
Greedy placement depends enormously on the order pieces arrive in, and no single ordering wins on every mix. So it runs four (by area, height, width and half-perimeter) and keeps the shortest marker. Multi-start is the cheapest useful thing you can do to a greedy heuristic before reaching for real search.
NFP is the right answer for a production nester, and it is a large piece of work: exact polygon subtraction, holes, degenerate contacts, numerical tolerance at every step. A raster is honest about its error — half a cell, everywhere — runs in milliseconds, and is what plenty of first passes actually do.
The resolution is a control on this page rather than a constant in the source, so you can see the trade instead of taking my word for it. Watch it at 4 mm and at 16 mm: finer is usually tighter, but not monotonically, because a coarser grid sometimes nudges a piece into a slot the finer one walked past. That non-monotonicity is the greedy showing through, and it is the reason production nesters run search on top.