RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Solving the 2D Packing Problem : Page 5

In 2D packing the goal is to fit as many items as possible into a specified area, without overlapping. Discover some packing problem variants, and explore some approaches you can use to solve one variation.

Exhaustive Search
The solutions in Figures 9 and 10 are pretty good. But can you do better?

If you look closely, you'll see that each solution has a row with 6 used squares. Each solution also has 11 unused squares on other rows. In theory at least, if you could rearrange things to move those 6 used squares onto other unused squares, then you could eliminate the six-used-squares row and shorten the solution by another unit to a height of 12.

That result shows that we cannot prove there is no better solution, but it doesn't tell you whether a better solution is actually possible. In fact, you can achieve a better solution. You might want to spend a few minutes trying to find it before you read further.

For a relatively small problem such as this one, you can resort to exhaustive search. The heart of the sample program's exhaustive search is the FillExhaustive subroutine shown in the following code:

   Private Sub FillExhaustive(ByRef best_rects() As Rectangle, _
    ByRef best_max_y As Integer, ByVal rects() As Rectangle, _
    ByVal next_i As Integer, ByVal used(,) As Boolean)
       ' See if we're at a leaf node.
       If next_i >= rects.Length Then
           ' We're at a leaf node.
           ' See if this solution is an improvement.
           Dim max_y As Integer = MaxY(rects)
           If best_max_y > max_y Then
               best_max_y = max_y
               best_rects = DirectCast(rects.Clone(), Rectangle())
           End If
           Dim rect As Rectangle = rects(next_i)
           For y As Integer = 0 To _
            used.GetUpperBound(1) - rect.Height + 1
               For x As Integer = 0 To _
                used.GetUpperBound(0) - rect.Width + 1
                   ' See if we can put the rectangle here.
                   Dim can_fit As Boolean = True
                   For i As Integer = 0 To rect.Width - 1
                       For j As Integer = 0 To rect.Height - 1
                           If used(x + i, y + j) Then
                               can_fit = False
                               Exit For
                           End If
                       Next j
                       If Not can_fit Then Exit For
                   Next i
                   ' Give it a try.
                   If can_fit Then
                       ' Put the rectangle here.
                       rects(next_i).X = x
                       rects(next_i).Y = y
                       For i As Integer = 0 To rect.Width - 1
                           For j As Integer = 0 To rect.Height - 1
                               used(x + i, y + j) = True
                           Next j
                       Next i
                       ' Recurse.
                       FillExhaustive(best_rects, best_max_y, _
                           rects, next_i + 1, used)
                       ' Un-put the rectangle here.
                       For i As Integer = 0 To rect.Width - 1
                           For j As Integer = 0 To rect.Height - 1
                               used(x + i, y + j) = False
                           Next j
                       Next i
                   End If
               Next x
           Next y
       End If
   End Sub
The best_rects parameter is an array containing the current best solution, while best_max_y is the height of that solution. The rects array contains all the rectangles; next_i is the index of the next rectangle that the algorithm must position. The used array holds one entry for each square in the stock and contains true if a square is in use by a rectangle.

The code starts by checking whether every rectangle has been positioned. If so, it's reached a possible solution. The code compares this solution's best_max_y value to others and saves this solution if it improves on the previous best solution.

If all the rectangles have not yet been positioned, then the code tries placing rectangle number next_i in every possible position. The code loops through each possible X and Y position, skipping coordinates where the rectangle would fall partly off of the stock's right or bottom edge. For each possible position, the code tests the used array to see if the rectangle can fit without overlapping another previously positioned rectangle.

When a rectangle can fit at a position, the subroutine puts it there, updates the used array, and recursively calls itself to position the remaining rectangles.

Figure 11. Exhaustive Solution: By testing every possible arrangement, the exhaustive solution finds the best possible answer.
After the recursive call returns, the subroutine removes the rectangle from its position and continues its loop, trying to place the rectangle in other locations.

When the original call to position the first rectangle finishes, the program has tried every possible arrangement of the rectangles and has found the best possible solution. Figure 11 shows the result—with a total height of only 12 units. This solution contains only 5 unused squares and the emptiest row contains 7 used squares so I'm fairly confident that you won't be able to find a better solution than this one. Table 1 summarizes the results of the heuristics you've seen.

Table 1. Heuristics Summary: Sorting by the total height of stock used, here are the results of the various heuristics evaluated in this article.
Heuristic Total Height
Two Columns 18
One Column 16
Sort by Height 14
Sort by Width 14
Sort by Area 14
Sort by Squareness 15
Fill by Stripes 13
Recursive Division 13
Exhaustive 12

The first several, Two Columns through Sort by Squareness, are relatively straightforward and produce fairly good results, but their main advantage is that they're also extremely fast, so your best bet is to try them all and pick the best result.

The Fill by Stripes algorithm is much more complicated and requires some fairly tricky recursion, so it takes longer than the previous algorithms, but it's fast enough that speed isn't much of an issue. In one test, the first few algorithms took no noticeable time to arrange 50 rectangles, while Fill by Stripes took about 0.30 seconds.

Recursive Division uses a much more complete recursion, so it takes some serious time. One test took 38 seconds to position only 10 rectangles.

Finally exhaustive search takes the longest. In one test this algorithm took 45 seconds to position a mere eight rectangles. You can see that it's probably not possible to use an exhaustive method to position more than nine or ten rectangles in a reasonable amount of time.

Other heuristics are certainly possible, and you may be able to come up with some that beat these algorithms at least some of the time.

For any given stock width and collection of rectangles, different heuristics will produce different results. To get the best results, try the fastest algorithms first, and pick the best solution they produce. Then if you have time, rewrite the Recursive Division and Exhaustive algorithms so they display good solutions as they find them—and let the programs rip. Then, at any point during execution, you can decide whether the current best solution is good enough, or whether you want to wait and give these slower algorithms a chance to find even better solutions.

It's also possible that other heuristics will find better solutions for certain arrangements of shapes. If you discover any that work well, let me know and I'll make them available on the VB Helper web site.

Rod Stephens is a consultant and author who has written more than a dozen books and two hundred magazine articles, mostly about Visual Basic. During his career he has worked on an eclectic assortment of applications for repair dispatch, fuel tax tracking, professional football training, wastewater treatment, geographic mapping, and ticket sales. His VB Helper web site receives more than 7 million hits per month and provides three newsletters and thousands of tips, tricks, and examples for Visual Basic programmers.
Email AuthorEmail Author
Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date