Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 Leather sheet

Here is the set of polygons I want to pack: Polyhedron net

share|improve this question
    
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
1  
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
3  
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
show 4 more comments

1 Answer 1

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: http://www2.stetson.edu/~efriedma/packing.html

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.

share|improve this answer
add comment

Your Answer

 
discard

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.