Skip to main content
Python Software Foundation 20th Year Anniversary Fundraiser  Donate today!

Pack a set of rectangles into a bounding box with minimum area

Project description

Pack a set of rectangles into a bounding box with minimum area

Welcome to rectangle-packer

PyPI-Versions PyPI-Wheel Build-Status Read-the-Docs GitHub-License

PyPI-Downloads

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 latest version from PyPI:

$ python3 -m pip install rectangle-packer

Or clone the repository and install with:

$ python3 setup.py 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 rectangle in the input.

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

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:

pack10

Example B:

packphi

Example C: Sometimes the input rectangles simply cannot be packed in a good way. Here is an example of low packing density:

pack10bad

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

PaulBrodersenExampleImage

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for rectangle-packer, version 2.0.1
Filename, size File type Python version Upload date Hashes
Filename, size rectangle_packer-2.0.1-cp36-cp36m-macosx_10_9_x86_64.whl (62.9 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-manylinux1_i686.whl (242.2 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-manylinux1_x86_64.whl (248.3 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-manylinux2010_i686.whl (242.2 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-manylinux2010_x86_64.whl (248.3 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-manylinux2014_aarch64.whl (270.8 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-win32.whl (57.4 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp36-cp36m-win_amd64.whl (65.8 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-macosx_10_9_x86_64.whl (62.9 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-manylinux1_i686.whl (241.8 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-manylinux1_x86_64.whl (246.3 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-manylinux2010_i686.whl (241.8 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-manylinux2010_x86_64.whl (246.3 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-manylinux2014_aarch64.whl (269.4 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-win32.whl (57.1 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp37-cp37m-win_amd64.whl (65.4 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-macosx_10_9_x86_64.whl (63.6 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-manylinux1_i686.whl (274.5 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-manylinux1_x86_64.whl (282.3 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-manylinux2010_i686.whl (274.5 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-manylinux2010_x86_64.whl (282.4 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-manylinux2014_aarch64.whl (313.1 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-win32.whl (58.5 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp38-cp38-win_amd64.whl (66.6 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-macosx_10_9_x86_64.whl (65.2 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-manylinux1_i686.whl (265.8 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-manylinux1_x86_64.whl (274.2 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-manylinux2010_i686.whl (265.8 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-manylinux2010_x86_64.whl (274.2 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-manylinux2014_aarch64.whl (305.6 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-win32.whl (58.5 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle_packer-2.0.1-cp39-cp39-win_amd64.whl (66.6 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size rectangle-packer-2.0.1.tar.gz (100.3 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page