Possible other goal functions?

[redhog]

Would it be possible to have other goal functions for the algorithm? In particular I'm interested in the rectangle with the smallest area with a certain aspect ratio that can hold the boxes. My use case is for packing windows on a screen (tiling), where any packing will be padded to the aspect ratio of the screen, and therefore often far from optimal. If not, do you know a python library that does this?

[Penlect]

Sounds like a useful thing. Unfortunately don't know of any python library that can do that. I will add this to the todo-list of future improvements.

[grst]

I would also be interested in this. In particular, I want to optimally arrange rectangles into a square.

[Penlect]

I'm planning to add this feature in July (when I have vacation)

[Penlect]

In the latest version, 2.0.0, two keyword arguments have been added: max_width and max_height. Read more about them here: https://rectangle-packer.readthedocs.io/en/latest/rpack.html#rpack.pack

You can use max_width=x and max_height=y where x and y satisfies the desired aspect ratio x/y. Increase x and y in a for-loop until the packing is successful, @redhog. For the square case, you can use y = x @grst.

[rbreu]

Hi! I think there's an error when using max_width / max_height: If the algorithm runs up against these values, the positions it returns have (x,y) switched. My code (trying to get more of a square bounding box):

  positions = None
  print('sizes:', sizes)
  while not positions:
      print('max_width, max_height:', width)
      try:
      positions = rpack.pack(
          sizes, max_width=width, max_height=width)
      except rpack.PackingImpossibleError:
      print('packing impossible, trying again')
      width = math.ceil(width * 1.2)

  print('positions:', positions)
  print('overlapping:', rpack.overlapping(sizes, positions))

Result:

sizes: [(2736, 3648), (2736, 3648), (2736, 3648), (2736, 3648), (3648, 2736)]
max_width, max_height: 7065
packing impossible, trying again
max_width, max_height: 8478
positions: [(0, 0), (0, 2736), (0, 5472), (3648, 0), (3648, 2736)]
overlapping: (0, 1)

If you switch x and y for each position, the result is fine!

Same set of rectangles but larger max values, same issue:

sizes: [(2736, 3648), (2736, 3648), (3648, 2736), (2736, 3648), (2736, 3648)]
max_width, max_height: 7065
packing impossible, trying again
max_width, max_height: 14130
positions: [(0, 0), (0, 2736), (3648, 0), (0, 5472), (0, 8208)]
overlapping: (0, 1)

And here I let the max values get big enough that the algorithm can put the rectangles in its preferred shape, now x and y are correct:

sizes: [(2736, 3648), (2736, 3648), (3648, 2736), (2736, 3648), (2736, 3648)]
max_width, max_height: 7065
packing impossible, trying again
max_width, max_height: 70650
positions: [(0, 0), (2736, 0), (10944, 0), (5472, 0), (8208, 0)]
overlapping: None

[Penlect]

Thank you @rbreu for reporting this bug. I have released a bugfix release, 2.0.1, and deployed new wheels to PyPI.

• https://rectangle-packer.readthedocs.io/en/latest/changelog.html#version-2-0-1-2021-05-13

[petered]

So here's the function I'm using for the "find the best packing for the given aspect ratio" problem. It just uses binary search to find a good packing. Not sure if that's the most efficient approach but it's working for my purposes. If there's interest I can make a PR into rectangle-packer.

def rpack_from_aspect_ratio(sizes: Sequence[Tuple[int, int]], aspect_ratio = 1., max_iter=8) -> Sequence[Tuple[int, int]]:
    """
    Find box corners of the smallest packing solution that fits in the given aspect ratio.
    This is approximate, and tries up to n_iter iterations.
    """
    upper_bound_width = max(sum(w for w, _ in sizes), sum(h*aspect_ratio for _, h in sizes))
    lower_bound_width = max(max(w for w, _ in sizes), max(h*aspect_ratio for _, h in sizes))
    result = None
    width = upper_bound_width
    for i in range(max_iter):
        height = int(width / aspect_ratio)
        try:
            print(f"Trying packing with {width}x{height}")
            result = rpack.pack(sizes, max_width=width, max_height=height)
        except PackingImpossibleError:
            lower_bound_width = width
        else:
            upper_bound_width = width
        width = int(lower_bound_width + upper_bound_width)//2
    assert result is not None, f"Should have been able to pack with width {upper_bound_width}"
    return result

Passes test:

def test_pack_with_aspect_ratio():
    corners = rpack_from_aspect_ratio(sizes = [(6, 6), (5, 5), (4, 4)], aspect_ratio=1.)
    assert corners == [(0, 0), (6, 0), (6, 5)]
    corners = rpack_from_aspect_ratio(sizes = [(6, 6), (5, 5), (4, 4)], aspect_ratio=10)
    assert corners == [(0, 0), (6, 0), (11, 0)]
    corners = rpack_from_aspect_ratio(sizes = [(6, 6), (5, 5), (4, 4)], aspect_ratio=0.1)
    assert corners == [(0, 0), (0, 6), (0, 11)]