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 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.packincreases 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 input rectangles cannot be packed very efficiently.
Example D: Image contributed by Paul Brodersen for a Stack Overflow discussion at stackoverflow.
Documentation