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: