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


Solving the 2D Packing Problem : Page 3


One Column Heuristic
One problem with the Two Columns heuristic is that two adjacent strips may together contain enough empty space to hold another shape. For example, if you slide the 4x3 rectangle left so it's next to the 4x4 rectangle in Figure 2, then you can fit the 2x3 rectangle next to both of them. Splitting the stock into two vertical columns makes it easier to prove the bound on the optimal solution, but doesn't necessarily give you the best arrangement.

The One Column heuristic begins just like Two Columns, by positioning the rectangles that are more than half the width of the stock. However, instead of dividing the stock into two vertical columns, it then fills the stock in a single column. It positions the next tallest item to make a horizontal strip and then uses subsequent rectangles to fill the strip.

Figure 3. One Column Heuristic: Using one column produces a better result in this case.
The result, shown in Figure 3, is an improvement over the Two Columns heuristic, at least in this example. Even in this solution, however, you can see lots of unused space in the upper parts of the solution and it's easy to see how to improve the solution. The algorithm would produce a better solution if it simply treated the first few extra-wide rectangles like it does all of the others and filled in their horizontal strips as much as possible.

Sort and Fill
The next few heuristics improve on the One Column algorithm by treating every rectangle the same way. They sort the rectangles in some manner and then start laying them out in horizontal strips.

The Sort by Height heuristic sorts the rectangles by height. It places the first in the stock's upper-left corner and starts laying out subsequent rectangles next to it until no more fit. It then starts a new horizontal strip and continues until all of the rectangles are in position.

Figure 4. Sort by Height: This algorithm fits all the rectangles into only 14 units of stock.
Note that this algorithm does not simply try to fit the next rectangle in a strip; when the next rectangle won't fit, this algorithm tries the following rectangles to see if any of them will fit. This approach lets it fill in areas such as the ones to the right of the 8x3 and 6x6 rectangles in Figure 3.

Figure 4 shows the Sort by Height algorithm's result. This version manages to fit all the rectangles into only 14 units of stock, considerably better than the 16 given by One Column and much better than the original height of 18 given by Two Columns.

The following code shows how the main algorithm works. It starts by using the Array.Sort method to sort the rectangles by height. The HeightComparer class provides a Compare method that compares rectangles by their heights and lets Array.Sort sort them properly. (The code also includes WidthComparer, AreaComparer, and SquarenessComparer classes used by other algorithms in the project.) After it sorts the rectangles, the code calls the SubAlgFillOneColumn method.

' Sort rectangles by height. ' Fill in by rows in a single column. Public Sub AlgSortByHeight(ByVal bin_width As Integer, _ ByVal rects() As Rectangle) ' Sort by height. Array.Sort(rects, New HeightComparer) ' Fill in one column. SubAlgFillOneColumn(bin_width, rects) End Sub

The following code shows how subroutine SubAlgFillOneColumn works.

' Fill in by rows in a single column. Public Sub SubAlgFillOneColumn(ByVal bin_width As Integer, _ ByVal rects() As Rectangle) ' Make lists of positioned and not positioned rectangles. Dim not_positioned As New List(Of Rectangle) Dim positioned As New List(Of Rectangle) For i As Integer = 0 To rects.Length - 1 not_positioned.Add(rects(i)) Next i ' Arrange the rectangles. Dim x As Integer = 0 Dim y As Integer = 0 Dim row_hgt As Integer = 0 Do While not_positioned.Count > 0 ' Find the next rectangle that will fit on this row. Dim next_rect As Integer = -1 For i As Integer = 0 To not_positioned.Count - 1 If x + not_positioned.Item(i).Width <= bin_width Then next_rect = i Exit For End If Next i ' If we didn't find a rectangle that fits, ' start a new row. If next_rect < 0 Then y += row_hgt x = 0 row_hgt = 0 next_rect = 0 End If ' Position the selected rectangle. Dim rect As Rectangle = not_positioned.Item(next_rect) rect.X = x rect.Y = y x += rect.Width If row_hgt < rect.Height Then row_hgt = rect.Height ' Move the rectangle into the positioned list. positioned.Add(rect) not_positioned.RemoveAt(next_rect) Loop ' Prepare the results. For i As Integer = 0 To positioned.Count - 1 rects(i) = positioned(i) Next i End Sub

The code starts by building two lists: one holds the rectangles that are positioned, and the other holds those that aren't positioned yet. Initially the not_positioned list holds all of the rectangles and the positioned list is empty.

The code then enters a loop that executes as long as there are rectangles that have not yet been positioned. The code looks through the not_positioned list in its sorted order to find the next rectangle that will fit in the current strip. If the code doesn't find a rectangle that will fit, it starts a new horizontal strip. We know that the first rectangle in the not_positioned list will fit on the new strip because that strip is currently empty.

The code positions the selected rectangle, either in the old strip or in a new one, and moves the rectangle from the not_positioned list to the positioned list.

The loop continues until every rectangle has been positioned. The algorithm then copies the rectangles back into the rects array to return the results to the caller and exits.

Figure 5. Sort by Width: This algorithm uses a one-column arrangement and sorts the rectangles by width.
The Sort by Height heuristic does a pretty good job of filling up empty areas, but there's still potential for improvement. The algorithm is remarkably simple so it's worth taking some extra time to see if other variations will produce useful results.

The Sort by Width, Sort by Area, and Sort by Squareness algorithms work exactly as Sort by Height does except they sort the rectangles differently before moving them into horizontal strips. These algorithms use different Comparer objects to sort the rectangles, but are otherwise identical.

Sort by Width sorts the rectangles by width. The arrangement differs from that produced by Sort by Height, but the total height is the same (see Figure 5).

Sort by Area sorts the rectangles by their area and positions the largest first. The idea is that the largest rectangles create empty areas that are hard to fill completely so it tries to fill them first while there are still smaller rectangles to use. The arrangement (see Figure 6) is again different, but results in the same total height.

Figure 6. Sort by Area: This algorithm produces a different arrangement, but doesn't improve the total stock used.
Figure 7. Sort by Squareness: Yet another arrangement with no improvement.
Sort by Squareness sorts the rectangles by the differences in their heights and widths so those that are most square are considered first. I didn't really have a great motivation for this one—but it was easy and sometimes you need to experiment. Figure 7 shows the result—no improvement in this case.

If you study Figures 4, 5, and 6, you can find simple ways to improve the solution. For example, in Figure 6 you could move the 3x2 rectangle into the space next to the 6x6 rectangle to reduce the total height by one unit. Unfortunately, the algorithms that fill by strips don't consider this type of solution, because it requires rectangles to be stacked within a strip. In this improved solution, the 3x2 rectangle is stacked below the 4x4 rectangle.

Comment and Contribute








