Welcome to rectangle-packer

Primary use: Given a set of rectangles with fixed orientations, find a bounding box of minimum area that contains them all with no overlap.

This project is inspired by Matt Perdeck's blog post Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites.

• The latest documentation is available on Read the Docs.
• The source code is available on GitHub.

Installation

Install the latest version from PyPI:

$ python3 -m pip install rectangle-packer

Or clone the repository and install it with:

$ python3 -m pip install .

Basic usage

# Import the module
>>> import rpack

# Create a bunch of rectangles (width, height)
>>> sizes = [(58, 206), (231, 176), (35, 113), (46, 109)]

# Pack
>>> positions = rpack.pack(sizes)

# The result will be a list of (x, y) positions:
>>> positions
[(0, 0), (58, 0), (289, 0), (289, 113)]

The output positions are the lower-left corner coordinates of each input rectangle.

These positions yield a packing with no overlaps and an enclosing area that is as small as possible (best effort).

rpack.pack also accepts optional max_width and max_height arguments if the packing must fit inside a specific bounding box. When the constraint cannot be satisfied a :py:exc:`rpack.PackingImpossibleError` is raised. For example, the following call forces all rectangles to fit within a width of 300:

>>> rpack.pack(sizes, max_width=300)
[(0, 0), (58, 0), (289, 0), (289, 113)]

If the width constraint is too small, PackingImpossibleError is raised.

Note

• You must use positive integers as rectangle width and height.
• The module name is rpack which is an abbreviation of the package name at PyPI (rectangle-packer).
• The computational time required by rpack.pack increases by the number and size of input rectangles. If this becomes a problem, you might need to implement your own divide-and-conquer algorithm.

Examples

Example A:

Example B:

Example C: Sometimes the input rectangles simply cannot be packed very efficiently. Here's an example that demonstrates a low packing density:

Example D: The image below, contributed by Paul Brodersen, illustrates a solution to a problem discussed at stackoverflow.