NfpNestingLib

Contesto

Disporre un insieme arbitrario di forme poligonali in un’area delimitata con il minimo scarto di materiale (packing) è il problema del nesting irregolare — quello che si incontra nel taglio della lamiera, nella disposizione di capi di abbigliamento e nella fresatura CNC, ovunque il materiale grezzo sia abbastanza costoso da rendere la densità di “impacchettamento” importante.

Cosa ho costruito

Una libreria C++/Qt costruita su due tecniche: il calcolo del no-fit-polygon, che per ogni coppia di forme restituisce la regione esatta in cui una può essere posizionata senza sovrapporsi all’altra (tramite la libreria di polygon clipping Clipper), e un algoritmo genetico che esplora rotazione dei pezzi, ordine di posizionamento e assegnazione ai contenitori per minimizzare lo scarto. Il calcolo dei NFP è il costo dominante con un numero realistico di pezzi, quindi i risultati vengono messi in cache e valutati in parallelo con Qt Concurrent. L’applicazione Qt di test mostrata nel video guida la libreria in modo interattivo — importa forme da SVG, permette di regolare i parametri dell’algoritmo e mostra il layout migliorare generazione dopo generazione; il suo scopo è quello di illustrare il funzionamento della libreira.

Notes

Ho avuto difficoltà nel comunicare la differenza tra affiancare le forme, in modo che siano a contatto l’una con l’altra (NFP) e l’ottimizzazione dell’area occupata. Questa ultima, il packing, è un processo di ottimizzazione di per sé lento (che l’algoritmo genetico scelto può rendere un po’ più lento): questo non è un caffé espresso, piuttosto un cold brew. Nel filmato questo è mostrato chiaramente: solo 11 miglioramenti in 8 minuti.

Disclaimer

L’algoritmo genetico è ispirato da quanto mostrato in https://svgnest.com.