Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
fantastic resources! huge thanks! – Jordan Arseno Oct 20 '12 at 2:25
The PPT lead me to the Bin Packing Problem which describes precisely what I'm looking for. Will definitely check these other links out too though ;) – Jordan Arseno Oct 20 '12 at 2:39
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 ;-) – Ganesh Oct 20 '12 at 2:44
Hehe! Actually, I found a interesting project called Wikihouse. 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! – Jordan Arseno Oct 20 '12 at 2:51
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. – bubba Oct 20 '12 at 4:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.