NfpNestingLib

Context

Packing an arbitrary set of polygon shapes into a bounded area with minimal wasted material is the irregular nesting problem — the kind that shows up in sheet-metal cutting, garment layout, and CNC routing, wherever stock material is expensive enough that packing density matters.

What I built

A C++/Qt library built on two techniques: no-fit-polygon computation, which for any pair of shapes yields the exact region where one can be placed without overlapping the other (via the Clipper polygon-clipping library), and a genetic algorithm that searches part rotation, placement order, and bin assignment to minimize wasted material. NFP computation is the dominant cost at realistic part counts, so results are cached and evaluated in parallel with Qt Concurrent. The test Qt app shown in the video drives the library interactively — it imports shapes from SVG, lets you tune the algorithm’s parameters, and shows the layout improve generation after generation; its purpose is to illustrate how the library works.

Notes

I had a hard time communicating the difference between fitting shapes so they touch one another (NFP) and optimizing the occupied area. The latter, packing, is inherently a slow optimization process (one the chosen genetic algorithm can make a bit slower): this isn’t an espresso, it’s a cold brew. The video shows this clearly: just 11 improvements in 8 minutes.

Disclaimer

The genetic algorithm is inspired by what’s shown at https://svgnest.com.