Today I want to give details on some possible applications of algorithm 3, that I outlined in my last post on tangram puzzles.
The first application is 2D packing, which is a variation on bin packing.
The 2-dimensional packing problem I want to solve is defined as follows:
Given a set of simple polygons S, find the smallest rectangle R and a packing such that the polygons in S are packed inside the rectangle R.
Notice that one of the constraints on problem is that we need to find the smallest rectangle that can be packed with the polygons in S. I don’t know if the algorithm I outline below satisfies this constraint, a later post will revisit this issue. My algorithm also restricts the rectangle R to be a square.
The algorithm for solving the above packing problem is as follows:
0. Set a tolerance ε.
1. Set a step size, dl, of 1.
2. Create a square, R, with sides of length l = 1.
3. Check using algorithm 3 (position_puzzle_pieces) if the polygons in S can be packed into R.
4. If S can be packed into R, then set l = l–dl.
5. If S cannot be packed into R, then set l = l+dl.
6. If steps 3 through 5 have looped more than once, then goto step 7. Otherwise, if for the last two loops of steps 3 through 5:
(1) S couldn’t be packed into R, then set dl = 2dl;
(2) S could be packed into R, then set dl = 2dl;
(3) otherwise dl = dl/2.
7. If, in step 3, S could be packed into R and dl < ε, then stop; otherwise goto step 3.
The above algorithm uses a binary search in combination with position_puzzle_pieces to find the optimal length l. The algorithm does assume that if S cannot be packed into a square with sides of length x, then S cannot be packed into any square with sides of length less than x.
That’s it for today. There are a couple other applications I want to talk about tomorrow and hopefully I’ll also have time to delve more deeply into variations on the position_puzzle_pieces algorithm.