Introduction

The 2D bin packing problem asks how to place a set of rectangles into the fewest fixed-size bins without overlap. It appears in cutting-stock software, sprite atlas generation, warehouse planning, and manufacturing. The problem is NP-hard, so practical systems usually rely on heuristics rather than exact optimization.

What Makes 2D Packing Hard

Each item has width and height, so packing is not just about total area. Two sets of rectangles can have the same combined area and still behave very differently because geometry matters.

A valid algorithm must ensure:

• every item fits within a bin's boundaries
• no two rectangles overlap
• optional rules such as rotation or guillotine cuts are respected

Because the search space grows quickly, exact methods such as branch-and-bound or mixed-integer programming are usually reserved for small instances.

Common Heuristic Families

Several heuristic families are widely used.

Shelf Algorithms

Items are arranged in horizontal rows called shelves. Each new rectangle is placed on the current shelf if it fits; otherwise a new shelf starts. Shelf methods are simple and fast, though they can waste space when item heights vary a lot.

Guillotine Algorithms

Each placement splits free space with straight cuts. These are useful when the real manufacturing process must cut material edge to edge.

Skyline and MaxRects

These methods maintain a more detailed description of free space and typically achieve better packing density than simple shelves. They are common in texture atlas generators and layout engines.

A Simple First-Fit Decreasing Shelf Algorithm

One practical baseline is:

1. sort rectangles by height or area, largest first
2. try to place each rectangle on the first shelf where it fits
3. if no shelf fits, start a new shelf or open a new bin

Here is a small Python implementation for a single-bin shelf packer. It returns None if an item does not fit in the bin.

1def pack_shelves(bin_width, bin_height, rects):
2    rects = sorted(rects, key=lambda r: (r[1], r[0]), reverse=True)
3    shelves = []
4    placements = []
5
6    for w, h in rects:
7        placed = False
8
9        for shelf in shelves:
10            y = shelf['y']
11            if h <= shelf['height'] and shelf['used_width'] + w <= bin_width:
12                x = shelf['used_width']
13                placements.append((x, y, w, h))
14                shelf['used_width'] += w
15                placed = True
16                break
17
18        if placed:
19            continue
20
21        new_y = sum(s['height'] for s in shelves)
22        if new_y + h > bin_height or w > bin_width:
23            return None
24
25        shelves.append({'y': new_y, 'height': h, 'used_width': w})
26        placements.append((0, new_y, w, h))
27
28    return placements
29
30
31rectangles = [(40, 30), (50, 20), (20, 20), (30, 10)]
32print(pack_shelves(100, 80, rectangles))

This is not state of the art, but it is easy to reason about and often good enough as a starting point.

Extending to Multiple Bins

To handle multiple bins, keep a list of bins and attempt to place each rectangle into the first bin that can accept it. If no existing bin works, open a new bin.

That turns the algorithm into a 2D analog of first-fit decreasing. The quality depends heavily on item ordering and the free-space strategy.

Rotation and Domain Constraints

Some applications allow 90-degree rotation; others do not. Rotation can improve packing density substantially, but it also doubles the placement choices.

Likewise, some manufacturing systems require guillotine cuts, margins between parts, or forbidden orientations. A good implementation treats those as first-class constraints instead of trying to patch them in later.

Choosing the Right Approach

If you need something simple and explainable, start with a shelf heuristic. If packing density matters more, use MaxRects, skyline, or a guillotine heuristic tuned for your real constraints.

If exact optimality is required and the instance size is small, use an optimizer. Otherwise, heuristics are the normal engineering choice.

Common Pitfalls

A common mistake is sorting only by area and assuming that is enough. Height and aspect ratio often matter just as much.

Another pitfall is evaluating a packer only by area utilization. In manufacturing, cut pattern validity and machine constraints can matter more than pure density.

Developers also underestimate the effect of rotation rules. A packer that silently rotates items may look impressive in tests and still be unusable in production.

Summary

• 2D bin packing is NP-hard, so heuristics are the usual practical solution.
• Shelf, guillotine, skyline, and MaxRects are common strategy families.
• First-fit decreasing with shelves is simple and fast, but not optimal.
• Real-world constraints such as rotation and cut rules strongly affect algorithm choice.
• Start with a baseline heuristic, then tune against your actual workload.