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

• 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

This belongs to an optimization class of problems called Packing problems. In your case, instead of a regular polygon as container, you've got an irregular one, but the idea remains the same.

These optimization problems are usually NP-hard, so I don't think there is an easy way to get the exact solution and trying all the combinations would be too too expensive.

There are some people interested in this kind of problems; I've found this link of some solved specific packing problems: https://erich-friedman.github.io/packing/

The easiest way I see, is to define an approximate center of the leather sheet, to move the set of polygons to there and, by scaling up and down and checking if the set of polygons is or not inside the target polygon, to get a closer and closer scale factor 'f' for your desired set of polygons.

But, unless you are going to use this factor for a large scale juggling balls production, probably doing it by hand would be fairly enough.

StackExchange Computer Science Q#6800, answer score: 3