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
    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