# How to pack polygons inside another polygon?

I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.

I can scan the leather sheets and generate a polygon that approximates the shape of the leather sheet (as you know, it's animal skin, and it doesn't come in rectangles).

So now, I would like to maximize the size of my juggling ball.

In my example, the polygons are regular ones, but I'm looking for a solution with simple polygons.

What is the largest scale factor that I can apply to my polygons so that they all fit inside the sheet ?

I am trying to minimize the waste by using as much as material as possible.

Obviously, cutting the polyhedron net into individual polygon will increase the space of possible combination, but also decrease the quality of the final geometry, because there is more sewing involved and accumulated errors. But this question is not about enumerating the different ways of unfolding a polyhedron. They can be considered independently. So the polygons are simple polygons.

Formally:

Input:

• $P$ : a simple polygon (the target)
• $S$ : the set of polygons I want to place
• $G$ : a graph of $n$ simple polygons - each node represents a simple polygon in $S$, and there is one edge edge between each pair of polygons that share a common edge
• $\alpha >= 0, \beta >= 0$ (usage of material and connectivity)

Output:

• a scale factor $f$
• $H$, a subgraph of $G$
• $Loc$: a location and an angle for each polygon in $V(G)$
• a measure of the quality $m$ of the solution: $m = \alpha.f + \beta. {|E(H)|\over|E(G)|}$

Maximize $m$ subject to these conditions:

• $| V(H) | = |V(G)|$ (1)
• $| E(H) | <= |E(G)|$ (2)
• for every polygon $S_i$ in $S$, $S_i$ scaled by a factor $f$ at location $Loc(S_i)$ is inside $P$ (3)
• polygons in $V(H)$ don't overlap (4)

( V(G) are the vertices in the graph, and S is the set of polygons, but they describe the same set of objects. Maybe there is a more compact way to do this.)

Explanation of the conditions:

• (1) I want all the polygons to be in the final layout
• (2) Some connections may be broken if necessary
• (3) (4) the ball is made of leather

Here is the target polygon

Here is the set of polygons I want to pack:

-
Are you talking about convex polygons you want to cut out? –  A.Schulz Nov 21 '12 at 8:31
In my case polygons are regular, because they are the faces of Platonic solids. But packing simple polygons should work too. Why do you want to know if the polygons I want to pack are convex ? –  Antoine Lecaille Nov 21 '12 at 8:39
If the polygons are non-convex, you could always place a single non-convex polygon inside the original polygon with no cut. So this question would not make sense for general polygons. –  A.Schulz Nov 21 '12 at 8:44
I don't know if this is important or not, but is the bounding polygon (leather) convex or can it be concave too? –  Paresh Nov 21 '12 at 10:48
Even the much simpler problem of packing the maximal number of squares in a square turns out to be hard (sorry, haven't got a link handy, but stumbled upon a discussion of this a few months back). Just juggle the polygons around by hand, you'd probably not be too far from the optimum. –  vonbrand Jan 28 '13 at 22:55