penlect / rectangle-packer Goto Github PK
View Code? Open in Web Editor NEWRectangle packing program
License: MIT License
Rectangle packing program
License: MIT License
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
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
Hi. Thanks for great work.
Can we add support for positive float in rpack.pack
method?
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.
Your package not provide wheels for arm64 macOS at the moment. Please, can you add it?
Latest version does not ship arm64 wheels for python 3.10 (but it does for python 3.6-3.9).
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
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
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?
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?
Thank you for your great module
algoryth just position of box, how to take size of bin?
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
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.
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
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'
[...]
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.
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!)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.