Module Reference

Functions

rpack.pack(sizes: Iterable[Tuple[int, int]], max_width=None, max_height=None) → List[Tuple[int, int]][source]

Pack rectangles into a bounding box with minimal area.

The result is returned as a list of coordinates “(x, y)”, which specifices the location of each corresponding input rectangle’s lower left corner.

The helper function bbox_size() can be used to compute the width and height of the resulting bounding box. And packing_density() can be used to evaluate the packing quality.

The algorithm will sort the input in different ways internally so there is no need to sort sizes in advance.

The GIL is released when C-intensive code is running. Execution time 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.

Very large Python integers are supported through a fallback path: first exact axis-wise gcd reduction is attempted, and if the instance still does not fit C long bookkeeping, a conservative power-of-two scaling approximation is used. This approximation is safe (no overlaps when scaled back) but can produce false negatives under strict max_width/max_height constraints.

Example:

# 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)]

Parameters:

sizes (Iterable[Tuple[int, int]]) – “(width, height)” of the rectangles to pack. Note: integer values only!
max_width (Union[None, int]) – Force the enclosing rectangle to not exceed a maximum width. If not possible, rpack.PackingImpossibleError will be raised.
max_height (Union[None, int]) – Force the enclosing rectangle to not exceed a maximum height. If not possible, rpack.PackingImpossibleError will be raised.

Returns:

List of positions (x, y) of the input rectangles.

Return type:

List[Tuple[int, int]]

Exceptions

class rpack.PackingImpossibleError

Packing rectangles is impossible with imposed restrictions.

This can happen, for example, if max_width is strictly less than the widest rectangle given to rpack.pack().

If possible, a partial result will be given in the second argument, with the positions of packed rectangles up till the point of failure.

Helper functions

rpack.bbox_size(sizes, positions) → Tuple[int, int][source]

Return bounding box size (width, height) of packed rectangles.

Useful for evaluating the result of rpack.pack().

Example:

>>> import rpack

>>> sizes = [(58, 206), (231, 176), (35, 113), (46, 109)]
>>> positions = rpack.pack(sizes)

>>> bbox_size(sizes, positions)
(335, 222)

Parameters:

sizes (List[Tuple[int, int]]) – List of rectangle sizes (width, height).
positions (List[Tuple[int, int]]) – List of rectangle positions (x, y).

Returns:

Size (width, height) of bounding box covering rectangles having sizes and positions.

Return type:

Tuple[int, int]

rpack.packing_density(sizes, positions) → float[source]

Return packing density of packed rectangles.

Useful for evaluating the result of rpack.pack().

Example:

>>> import rpack

>>> sizes = [(58, 206), (231, 176), (35, 113), (46, 109)]
>>> positions = rpack.pack(sizes)

>>> packing_density(sizes, positions)
0.8279279279279279

Parameters:

sizes (List[Tuple[int, int]]) – List of rectangle sizes (width, height).
positions (List[Tuple[int, int]]) – List of rectangle positions (x, y).

Returns:

Packing density as a fraction in the interval [0, 1], where 1 means that the bounding box area equals the sum of the areas of the rectangles packed, i.e. perfect packing.

Return type:

float

rpack.overlapping(sizes, positions)[source]

Return indices of overlapping rectangles, else None.

Mainly used for test cases.

Example:

>>> sizes = [(10, 10), (10, 10)]

>>> positions = [(0, 0), (10, 10)]
>>> overlapping(sizes, positions) is None
True

>>> positions = [(0, 0), (5, 5)]
>>> overlapping(sizes, positions)
(0, 1)

Parameters:

sizes (List[Tuple[int, int]]) – List of rectangle sizes (width, height).
positions (List[Tuple[int, int]]) – List of rectangle positions (x, y).

Returns:

Return indices (i, j) if i-th and j-th rectangle overlap (first case found). Return None if no rectangles overlap.

Return type:

Union[None, Tuple[int, int]]

Index

View Index.