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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ fantastic resources! huge thanks! $\endgroup$
    – Jordan Arsenault
    Commented Oct 20, 2012 at 2:25
  • $\begingroup$ 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 ;) $\endgroup$
    – Jordan Arsenault
    Commented Oct 20, 2012 at 2:39
  • $\begingroup$ 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 ;-) $\endgroup$
    – Ganesh
    Commented Oct 20, 2012 at 2:44
  • $\begingroup$ 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! $\endgroup$
    – Jordan Arsenault
    Commented Oct 20, 2012 at 2:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – bubba
    Commented Oct 20, 2012 at 4:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .