i’m trying to optimize the fitting of a collection of shapes onto sheets of material.
the shapes cannot be rotated (except 180 degrees) but should be placed to optimally fill sheets for manufacture. material sheets have fixed dimensions.
the current algorithm sorts by area, then fills sheets with the largest piece it can fit into the available space.
any ideas?
this is an Np-complete problem…
this much i’d realised…
Is there any restriction on how the shapes can look like? Are they arbitrary polygons, or worse do they have holes?
For the really general case I don’t know any better deterministic algorithm, but you could try something along the lines of a genetic algorithm. Another idea would be to approximate the shapes with an axis alinged block structure (think Tetris 
), and solve this problem instead. It’s still NP-complete, but it’s a lot easier to find optimizing heuristics.
thanks.
the “parts” are all solid polygons, mostly convex but could easily be concave. holes will not occur.
the pieces can’t be rotated, so i guess that should reduce the possibilities…