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


Solving the 2D Packing Problem : Page 4

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.

Fill by Stripes
Algorithm Fill by Stripes is more complicated than the previous algorithms. Again, it starts by sorting the rectangles by height. Then it positions the tallest non-positioned rectangle and uses it to start a new horizontal stripe. The algorithm then calls the FillBoundedArea method to fill that stripe as completely as it can by using the remaining rectangles.

FillBoundedArea is a fairly tricky recursive subroutine. It starts with an area to fill (the stripe) and loops through the non-positioned rectangles, placing each rectangle in the upper-left corner of the area it is filling to see whether that placement produces a good solution.

Figure 8. FillBoundedArea: By dividing empty space into areas determined by the edges of an already-placed rectangle, this method tries to make optimum use of remaining space.
The subroutine then divides the area either vertically or horizontally along an edge of the newly positioned rectangle, which is in the green area labeled 1 in Figure 8. The subroutine first tries dividing the area horizontally, and then divides the remaining area into the piece labeled 2 and the large horizontal area containing the regions labeled 3 and 4 (surrounded by the red lines). Subroutine FillBoundedArea calls itself to see how well it can fill these two new areas 2 and 3 + 4.

After the recursive call to itself returns, FillBoundedArea tries dividing its area vertically. In Figure 8, it now considers the area labeled 3 and the large vertical area that includes the regions 2 and 4 (surrounded by the blue dashed lines). The subroutine calls itself recursively to see how well it can fill these two new areas 3 and 2 + 4.

When that recursive call returns, the method evaluates whether it did a better job filling the total area by using the horizontal division or the vertical division. Finally, if the better of those solutions improves on the best solution found so far for the total area, it saves the new solution.

Figure 9. Fill by Stripes: This heuristic recursively attempts to find the best possible solution after placing each remaining rectangle.
Now the method goes back and tries again, starting with a new rectangle positioned in the upper left corner (area 1 in Figure 8). It iterates over all the rectangles in this manner, placing each, and then recursively filling any remaining empty area until it has tried all the rectangles. When the loop completes, it returns the best solution.

Figure 9 shows the best solution found by the Fill by Stripes algorithm. It's an even better solution than the one found by the Sort and Fill algorithms, having a total height of only 13 units.

Recursive Division
The Recursive Division algorithm uses recursion similarly to Fill by Stripes, but where Fill by Stripes starts by positioning a rectangle and then using the FillBoundedArea subroutine to try to fill its horizontal strip as densely as it can, the Recursive Division algorithm does away with the idea of stripes altogether. Like Fill by Stripes it positions a rectangle and then considers dividing the remaining area vertically and horizontally along the rectangle's edges. Unlike Fill by Stripes, however, the lower areas that it must then fill are not always bounded below.

Look again at Figure 8. Suppose the algorithm has just positioned the very first rectangle. This algorithm doesn't use stripes so the total area to fill includes the entire piece of stock, which does not have a fixed length. Imagine that areas 3 and 4 don't have bottom edges; they extend indefinitely downward. The FillBoundedArea method can fill only bounded areas (hence the name) so it won't work on unbounded areas. However, FillUnboundedArea can fill unbounded areas.

Figure 10. Recursive Division: The Recursive Division algorithm packs rectangles equally as well as Fill by Stripes.
The Recursive Division algorithm starts by calling FillUnboundedArea to fill the entire stock area. That routine positions a rectangle as before, and tries to divide the area horizontally and vertically. For the horizontal division, it calls FillBoundedArea to fill area 2 and calls FillUnboundedArea to fill the combined area 3 + 4. For the vertical division, it calls FillUnboundedArea to fill area 3 and calls FillUnboundedArea to fill the combined area 2 + 4.

When its recursive calls return, the subroutine considers the solutions it found and returns the best one.

Figure 10 shows the result produced by the Recursive Division heuristic. It results in a new arrangement but the same total height as the Fill by Stripes technique.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date