penlect / rectangle-packer Goto Github PK

View Code? Open in Web Editor NEW

62.0 62.0 17.0 299 KB

Rectangle packing program

License: MIT License

C 44.43% Python 40.99% Makefile 1.61% Cython 12.97%

rectangle-packer's People

Contributors

Stargazers

Watchers

Forkers

williamyf dawnduan cfandy paulbrodersen dipperside boothby huangshizhi nanding0701 datakira priyonka bzp92 georgetsu chintasunny arcondello titafox gw-dev101

rectangle-packer's Issues

build failure on linux x86-64 / python 3.5 and python 3.6

I attempted to install rectangle-packer on an x86-64 linux system. There don't appear to be any wheels for linux or osx, so pip falls back to building it. Apparently, the gcc on this system is quite pedantic and needs a -std=c99 flag because of a single line. This issue can be resolved by adding that compiler flag on linux builds, or by mending that one line to conform to ANSI-C.

    running install
    running build
    running build_py
    creating build
    creating build/lib.linux-x86_64-3.5
    creating build/lib.linux-x86_64-3.5/rpack
    copying rpack/__init__.py -> build/lib.linux-x86_64-3.5/rpack
    running egg_info
    writing rectangle_packer.egg-info/PKG-INFO
    writing top-level names to rectangle_packer.egg-info/top_level.txt
    writing dependency_links to rectangle_packer.egg-info/dependency_links.txt
    reading manifest file 'rectangle_packer.egg-info/SOURCES.txt'
    reading manifest template 'MANIFEST.in'
    writing manifest file 'rectangle_packer.egg-info/SOURCES.txt'
    running build_ext
    building 'rpack._rpack' extension
    creating build/temp.linux-x86_64-3.5
    creating build/temp.linux-x86_64-3.5/src
    gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -Iinclude -I/usr/local/include/python3.5m -c src/rpack.c -o build/temp.linux-x86_64-3.5/src/rpack.o
    gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -Iinclude -I/usr/local/include/python3.5m -c src/areapack.c -o build/temp.linux-x86_64-3.5/src/areapack.o
    gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -Iinclude -I/usr/local/include/python3.5m -c src/taskpack.c -o build/temp.linux-x86_64-3.5/src/taskpack.o
    src/taskpack.c: In function ‘check’:
    src/taskpack.c:50:9: warning: variable ‘fail’ set but not used [-Wunused-but-set-variable]
         int fail = 1;
             ^
    src/taskpack.c: In function ‘stack_sum’:
    src/taskpack.c:91:5: error: ‘for’ loop initial declarations are only allowed in C99 or C11 mode
         for (size_t i = 0; i < stack->nr_groups; i++){
         ^
    src/taskpack.c:91:5: note: use option -std=c99, -std=gnu99, -std=c11 or -std=gnu11 to compile your code
    src/taskpack.c: At top level:
    src/taskpack.c:45:13: warning: ‘check’ defined but not used [-Wunused-function]
     static void check(StackState *stack, Task *tasks, size_t nr_tasks){
                 ^
    src/taskpack.c:89:15: warning: ‘stack_sum’ defined but not used [-Wunused-function]
     static double stack_sum(StackState *stack){
                   ^
    src/taskpack.c:143:15: warning: ‘get_group_size’ defined but not used [-Wunused-function]
     static size_t get_group_size(Task* tasks, size_t nr_tasks, size_t group){
                   ^
    error: command 'gcc' failed with exit status 1

Sharing a recipe: optimal packing when allowing for rotations

Thanks to your library, I was able to optimize the packing of my library shelves on a wall at home:

Thank you! 👍
(I know, it looks simple enough to solve by hand, but it was fun using your lib and building a web visualization 😊)

In the process I used the following function to find the optimal rectangle packing while allowing for 90° rotations, and thought it could be useful to share it here:

from itertools import chain, combinations
from rpack import pack, packing_density, PackingImpossibleError

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def optimal_pack(sizes, max_width=None, max_height=None):
    best_sizes, best_positions, best_density = (), (), 0
    for rotated_sizes_indices in powerset(range(len(sizes))):
        sizes_with_rotations = [((height, width) if i in rotated_sizes_indices else (width, height))
                                for (i, (width, height)) in enumerate(sizes)]
        try:
            positions = pack(sizes_with_rotations, max_width=max_width, max_height=max_height)
        except PackingImpossibleError:
            continue
        density = packing_density(sizes, positions)
        if not best_density or density > best_density:
            best_sizes, best_positions, best_density = sizes_with_rotations, positions, density
    return best_sizes, best_positions

Add support for positive float numbers

Hi. Thanks for great work.

Can we add support for positive float in rpack.pack method?

importing for use

The documentation does not mention very clearly that this must be imported as "rpack" in python. Both "rectangle-packer" and "_rpack" are mentioned, but it took some digging to find how to correctly import. Maybe it could be added as a line in the "Basic Usage" documentation.

Not compatible with Apple Silicon arm64 macOS

Your package not provide wheels for arm64 macOS at the moment. Please, can you add it?

manylinux `aarch64` wheels missing for py310

Latest version does not ship arm64 wheels for python 3.10 (but it does for python 3.6-3.9).

Any plans to upload to conda-forge?

Hi @Penlect

Do you have any plans to upload rectangle-packer to conda-forge?

I am considering publishing netgraph there as I am slowly starting to use conda/mamba environments more than plain virtualenvs, and someone raised a related issue. However, a package can only be published on conda-forge if all of its dependencies are already published there, and your package is the only dependency still missing. I am happy to make a pull-request with the necessary configuration files (as I need to figure out how to write them for netgraph anyway) but you should submit it for review.

Best,
Paul

Cython.Compiler.Errors.CompileError: rpack/_core.pyx

Trying to build on Arch Linux via https://aur.archlinux.org/packages/python-rectangle-packer

Currently getting:

==> Starting build()...
/usr/lib/python3.11/site-packages/setuptools/__init__.py:84: _DeprecatedInstaller: setuptools.installer and fetch_build_eggs are deprecated.
!!

        ********************************************************************************
        Requirements should be satisfied by a PEP 517 installer.
        If you are using pip, you can try `pip install --use-pep517`.
        ********************************************************************************

!!
  dist.fetch_build_eggs(dist.setup_requires)
running build
running build_py
creating build
creating build/lib.linux-x86_64-cpython-311
creating build/lib.linux-x86_64-cpython-311/rpack
copying rpack/__init__.py -> build/lib.linux-x86_64-cpython-311/rpack
running egg_info
creating rectangle_packer.egg-info
writing rectangle_packer.egg-info/PKG-INFO
writing dependency_links to rectangle_packer.egg-info/dependency_links.txt
writing top-level names to rectangle_packer.egg-info/top_level.txt
writing manifest file 'rectangle_packer.egg-info/SOURCES.txt'
reading manifest file 'rectangle_packer.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
adding license file 'LICENSE.md'
writing manifest file 'rectangle_packer.egg-info/SOURCES.txt'
copying rpack/_core.pxd -> build/lib.linux-x86_64-cpython-311/rpack
copying rpack/_core.pyx -> build/lib.linux-x86_64-cpython-311/rpack
running build_ext
Compiling rpack/_core.pyx because it changed.
[1/1] Cythonizing rpack/_core.pyx
warning: rpack/_core.pyx:15:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310
warning: rpack/_core.pyx:16:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310
warning: rpack/_core.pyx:17:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310
warning: rpack/_core.pyx:18:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310
warning: rpack/_core.pyx:19:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310
warning: rpack/_core.pyx:20:0: The 'DEF' statement is deprecated and will be removed in a future Cython version. Consider using global variables, constants, and in-place literals instead. See https://github.com/cython/cython/issues/4310

Error compiling Cython file:
------------------------------------------------------------
...
        self.sum_width, self.sum_height = self.sum_height, self.sum_width
        self.min_width, self.min_height = self.min_height, self.min_width
        self.max_width, self.max_height = self.max_height, self.max_width

    cdef void sort_by_index(self, size_t length) nogil:
        qsort(<void*>(self.rectangles), length, sizeof(Rectangle), rectangle_index_cmp)
                                                                   ^
------------------------------------------------------------

rpack/_core.pyx:209:67: Cannot assign type 'int (const void *, const void *) except? -1 nogil' to 'int (*)(const void *, const void *) noexcept nogil'. Exception values are incompatible. Suggest adding 'noexcept' to type 'int (const void *, const void *) except? -1 nogil'.

Error compiling Cython file:
------------------------------------------------------------
...

    cdef void sort_by_index(self, size_t length) nogil:
        qsort(<void*>(self.rectangles), length, sizeof(Rectangle), rectangle_index_cmp)

    cdef void sort_by_width(self) nogil:
        qsort(<void*>(self.rectangles), self.length, sizeof(Rectangle), rectangle_width_cmp)
                                                                        ^
------------------------------------------------------------

rpack/_core.pyx:212:72: Cannot assign type 'int (const void *, const void *) except? -1 nogil' to 'int (*)(const void *, const void *) noexcept nogil'. Exception values are incompatible. Suggest adding 'noexcept' to type 'int (const void *, const void *) except? -1 nogil'.

Error compiling Cython file:
------------------------------------------------------------
...

    cdef void sort_by_width(self) nogil:
        qsort(<void*>(self.rectangles), self.length, sizeof(Rectangle), rectangle_width_cmp)

    cdef void sort_by_height(self) nogil:
        qsort(<void*>(self.rectangles), self.length, sizeof(Rectangle), rectangle_height_cmp)
                                                                        ^
------------------------------------------------------------

rpack/_core.pyx:215:72: Cannot assign type 'int (const void *, const void *) except? -1 nogil' to 'int (*)(const void *, const void *) noexcept nogil'. Exception values are incompatible. Suggest adding 'noexcept' to type 'int (const void *, const void *) except? -1 nogil'.

Error compiling Cython file:
------------------------------------------------------------
...

    cdef void sort_by_height(self) nogil:
        qsort(<void*>(self.rectangles), self.length, sizeof(Rectangle), rectangle_height_cmp)

    cdef void sort_by_area(self) nogil:
        qsort(<void*>(self.rectangles), self.length, sizeof(Rectangle), rectangle_area_cmp)
                                                                        ^
------------------------------------------------------------

rpack/_core.pyx:218:72: Cannot assign type 'int (const void *, const void *) except? -1 nogil' to 'int (*)(const void *, const void *) noexcept nogil'. Exception values are incompatible. Suggest adding 'noexcept' to type 'int (const void *, const void *) except? -1 nogil'.
Traceback (most recent call last):
  File "/home/milk/.cache/yay/python-rectangle-packer/src/rectangle-packer-2.0.1/setup.py", line 46, in <module>
    setup(
  File "/usr/lib/python3.11/site-packages/setuptools/__init__.py", line 107, in setup
    return distutils.core.setup(**attrs)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/core.py", line 185, in setup
    return run_commands(dist)
           ^^^^^^^^^^^^^^^^^^
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/core.py", line 201, in run_commands
    dist.run_commands()
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 969, in run_commands
    self.run_command(cmd)
  File "/usr/lib/python3.11/site-packages/setuptools/dist.py", line 1234, in run_command
    super().run_command(command)
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/build.py", line 131, in run
    self.run_command(cmd_name)
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command
    self.distribution.run_command(command)
  File "/usr/lib/python3.11/site-packages/setuptools/dist.py", line 1234, in run_command
    super().run_command(command)
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/usr/lib/python3.11/site-packages/setuptools/command/build_ext.py", line 84, in run
    _build_ext.run(self)
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/build_ext.py", line 345, in run
    self.build_extensions()
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/build_ext.py", line 467, in build_extensions
    self._build_extensions_serial()
  File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/build_ext.py", line 493, in _build_extensions_serial
    self.build_extension(ext)
  File "/usr/lib/python3.11/site-packages/setuptools/command/build_ext.py", line 246, in build_extension
    _build_ext.build_extension(self, ext)
  File "/usr/lib/python3.11/site-packages/Cython/Distutils/build_ext.py", line 122, in build_extension
    new_ext = cythonize(
              ^^^^^^^^^^
  File "/usr/lib/python3.11/site-packages/Cython/Build/Dependencies.py", line 1134, in cythonize
    cythonize_one(*args)
  File "/usr/lib/python3.11/site-packages/Cython/Build/Dependencies.py", line 1301, in cythonize_one
    raise CompileError(None, pyx_file)
Cython.Compiler.Errors.CompileError: rpack/_core.pyx
==> ERROR: A failure occurred in build().
    Aborting...
 -> Failed to install layer, rolling up to next layer.error:error making: python-rectangle-packer - exit status 4

from . import _rpack

Hi, I am having issue with the statement 'from . import _rpack' in init.py module from rpack package. Where is that package so that i can use it?

Possible other goal functions?

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?

how to get size of width, height of container?

Thank you for your great module
algoryth just position of box, how to take size of bin?

Pack not fitting in max_height

I have faced a problem with one concrete sizes list and max_height. After packing the result container's height is bigger than max_height, but its enough width space to make packing the correct height.

Python 3.8.6

rpack.__version__ 2.0.0


import rpack

sizes = [[54, 36], [122, 56], [162, 144], [158, 202], [141, 159], [71, 60], [66, 71], [157, 211], [38, 38], [37, 40], [39, 41], [96, 124], [105, 132], [95, 132], [50, 34], [66, 53], [72, 54], [38, 50], [86, 83], [238, 137], [389, 214], [266, 138], [275, 226], [228, 175], [125, 121], [177, 219], [255, 145], [599, 221], [399, 187], [342, 226]]

max_height = 960
max_width = 3860

positions = rpack.pack(sizes, max_height=max_height, max_width=max_width)

print(rpack.bbox_size(sizes, positions))                                     

### (1017, 1005)  but max_height was 960

python 2 support

Awesome work. Works beautifully only that I couldn't get the package (downloaded from pip) to work in a python 2 environment. Not saying that you should support python 2, but maybe add a warning to the README.

Also, if you want to add some more pretty pictures to stimulate people's imagination of what can be done with this package, I just made this using rpack:
https://stackoverflow.com/a/53156709/2912349

You have a criminally low star/fork count for something so useful.

Memory requirements

Hi Daniel,

I saw that you included some benchmark results with your documentation. Do you also have any insights into how the memory requirements scale with the size of the canvas and the number of boxes? One user of my network visualisation library netgraph (which uses rectangle-packer to arrange disconnected components with respect to each other) ran into a memory issue that traced back to rectangle-packer. I am trying to come up with a divide-and-conquer strategy (as advised in your README) but for that it would be good to know if I need to decrease the search space by reducing the size of the "canvas" or the number of rectangles.

Best,
Paul

Can't build on apple silicon

Hello! I recently switched to a new apple silicon M2 device and could not build this package successfully.

Error compiling Cython file:
      ------------------------------------------------------------
      ...
              self.sum_width, self.sum_height = self.sum_height, self.sum_width
              self.min_width, self.min_height = self.min_height, self.min_width
              self.max_width, self.max_height = self.max_height, self.max_width

          cdef void sort_by_index(self, size_t length) nogil:
              qsort(<void*>(self.rectangles), length, sizeof(Rectangle), rectangle_index_cmp)
                                                                         ^
      ------------------------------------------------------------

      rpack/_core.pyx:209:67: Cannot assign type 'int (const void *, const void *) except? -1 nogil' to 'int (*)(const void *, const void *) noexcept nogil'
[...]

x, y switched when using max_width/max_height

When you specify max_width and max_height and the values are small enough that the algorithm can't build it's preferred shape, the (x, y) values of the resulting positions are switched. If max_width and max_height are big enough so that the algo can build it's preferred shape, all is fine.

import rpack
sizes = [(2736, 3648), (2736, 3648), (3648, 2736), (2736, 3648), (2736, 3648)]

# Max width/height big enough that the algorithm can build its preferred shape:
max_wh = 70650
positions = rpack.pack(sizes, max_width=max_wh, max_height=max_wh)
print(positions)  # [(0, 0), (2736, 0), (10944, 0), (5472, 0), (8208, 0)]
print(rpack.overlapping(sizes, positions))  # None

# Max width/height smaller so that the algorithm need to deviate from its preferred shape:

max_wh = 14130
positions = rpack.pack(sizes, max_width=max_wh, max_height=max_wh)
print(positions)  # [(0, 0), (0, 2736), (3648, 0), (0, 5472), (0, 8208)]
print(rpack.overlapping(sizes, positions))  # (0, 1)
print(rpack.overlapping(sizes, [(p[1], p[0]) for p in positions]))  # None

max_wh = 8478
positions = rpack.pack(sizes, max_width=max_wh, max_height=max_wh)
print(positions)  # [(0, 0), (0, 2736), (3648, 2736), (0, 5472), (3648, 0)]
print(rpack.overlapping(sizes, positions))  # (0, 1)
print(rpack.overlapping(sizes, [(p[1], p[0]) for p in positions]))  # None

There's an easy workaround, if anyone needs this, just apply this to your resulting positions:

if rpack.overlapping(sizes, positions):
    positions = [(p[1], p[0]) for p in positions]

With this, all works like a charm.

Missing wheels for linux and osx

I'd like to use rectangle-packer as a dependency for minorminer and we generally don't require our users to have compilers for supported systems (py3.5-3.8, win / osx / linux). I'd be happy to help building wheels for these systems, if you're interested. Otherwise, I'll need to figure something out involving submodules (very grateful for your MIT-licensed code!)