3
$\begingroup$

Consider a machine that cuts many oddly shaped polygons out of sheets of plywood. How best to orient these polygons on the plywood to minimize waste?

As an added note: The polygons can have holes. The area of these holes should be reused if possible.

What is this field called? Are there any papers? Are there open-source algorithms?

1 Answers 1

2

If by minimize waste you mean minimize area of rectangle circumscribing the polygons, you're looking at a polygon packing problem. This seems to be NP-hard as given in the link; see a proof for a variant here. Also see this PPT .

So people have devised genetic algorithms and simulated annealing for solving this problem. Also, there are special cases, like rectilinear packing and rectangular packing. Interestingly, there seems to be a contest problem based on this. A slight variant of this problem is open. See here for a detailed discussion of packing irregular objects.

I don't know of any implementation, but if you want to write your own, I suggest using LEDA primitives.

In short, your question seems to be of current research interest; all I can give are pointers and not a complete answer.

  • 0
    fantastic resources! huge thanks!2012-10-20
  • 0
    The PPT lead me to the [Bin Packing Problem](http://en.wikipedia.org/wiki/Bin_packing_problem) which describes precisely what I'm looking for. Will definitely check these other links out too though ;)2012-10-20
  • 0
    Great, enjoy the deep dive into Computational Geometry. And I hope to see some of this implemented in the latest CodeIgniter GUI if there's one ;-)2012-10-20
  • 0
    Hehe! Actually, I found a interesting project called [Wikihouse](http://www.wikihouse.cc/). They're current algos for parts placement are pretty primitive, so, just trying my hand at something new in hopes that I may contribute some help!2012-10-20
  • 0
    Maybe even save a few trees.2012-10-20
  • 1
    In the world of engineering/manufacturing (as opposed to mathematics), this is known as a "nesting" problem. There are many commerical packages for nesting sheet metal parts. The problem is different with cloth because rotations might not be allowable (because of the pattern of the cloth). Glass is interesting, too, since every cut has to go all the way across the remaining piece.2012-10-20
  • 0
    thx @bubba: it's interesting you note the cloth issue. I was pondering something similar with my case... I figure you could incorporate the _mirror image_ of the polys in the algos along with positional and rotational shifts. The mirror image could not be applied to cloth (imagine wearing your pants inside-out), it could be applied to some glass (for instance, non-tainted), but seems to work well for this case. (provided one side is not finished)2012-10-20