secnot / rectpack Goto Github PK
View Code? Open in Web Editor NEWPython 2D rectangle packing library
License: Apache License 2.0
Python 2D rectangle packing library
License: Apache License 2.0
Do you have a contact with the developer?
I have a set of bins, some of them have the same size as some rectangles, and I need to use the same size bins, but the default algorithm chooses a bigger bin for that rectangle. Is it a feature? Is there a parameter to avoid that?
I am using the online packer and calling add_rect()
when needed. However, the return value is inconsitent and never complete. The only way to get the full solution seems to be to iterate all bins which is O(n) for n rects packed so far. The solution is available and could be returned, but...
bool
indicating whether packing succeeded.None
otherwise - but not the bin ID it was packed into.I would suggest changing the return value for all three to a tuple of the form (bin_id, rect)
.
How do I get the output to be a plot as shown in the introduction page?
When I pack the rectangles it returns a list of rectangles ordered in order of where they are placed in, but because I'm using this for a texture atlas I still need to know which file name is for each rectangle. Is there a way to return the list in the order I entered the rectangles details in?
rectangles = [(200, 100), (400, 100), (300, 100)]
instead of [[0, 0, 400, 100], [400, 0, 300, 100], [700, 0, 200, 100]]
I want it in the order I put it in [[700, 0, 200, 100], [0, 0, 400, 100], [400, 0, 300, 100]]
so I can compare them with my list of file paths.
So I am using this library to try and pack rectangles (go figure) into a single bin. It works completely fine for my test of 25% coverage as well as my test for 50% coverage. However, it runs into issues when I try to use my 75% and 95% tests. At the moment I am assuming that I am somehow using this package wrong, but I would like to have some input. I am using python 3 for this if that makes any difference.
It would be very useful to somehow report whether all the rectangles were fitted into available bins or not (there were some rectangles left out).
I would like to use this is an iOS app, there are ways to embed python library in OSX app but I don't find any complete solution to embed in iOS app. It would be great if you provide me a solution.
Hi,
It would be great if you could insert rectangles at fixed, user-specified positions prior to packing (equivalently, impose placement constraints on some of rectangles you wish to pack).
e.g. "I have some rectangles I want to pack, but one of them has to be at (x,y) and another has to be at (x', y')"
Cheers,
Alex
How to specify which rectangles can rotate for best packing, and what cant?
Hi,
Thank you for sharing us this work, this is very helpfull for my needs.
I want to add a weight contraint, that needs to modify your code:
But I can't find where I should implant that.. if you can give me some clues I could work on it.
Thank you in advance
HI Team, Could you please let me know How we can pack rectangles from Right to Left?
Hi,
I am trying to visualize the result that we obtain as you demonstrate in project page. How can I do it? I guess you use matplotlib but I am not experienced enough in coding environment. Thx.
From time to time, I have a number of STL files that I would like to 3D print. It was simple enough to read a bill of materials and pack objects into a bin the size of my printer's bed. However, my printer's software is limited to about a million triangles in an object description, and my bins are regularly containing five times that many. I need to tweak the packing algorithms to account for this. Any advice would be appreciated.
I am using this to help our CNC process of cutting plywood sheets into parts. For my normal use case this is working great. One edge case i have is that sometimes parts are longer than length of sheet and so parts need to be joined. There could be up to 2 joins / 3 sub parts needed for a part.
How would you handle this so it gets nested? The only idea i have is to manually split the part into sub parts at sheet length, sheet length and remainder. Any other better ideas?
Example:
My use case involves large numbers of rectangles (e.g., 10k) which I want to pack as quickly as possible, even if the packing isn't optimal.
I've taken the advice in the documentation to use one of the faster algorithms, and that was an improvement from the one I started with, but I'm looking for something at least 10x faster (my application is interactive).
So my questions are: is this a feature anyone else would use? And if so, is there some guidance available as to how to plug an additional algorithm into this library? I would be happy to contribute if this would be useful to others, otherwise I'll roll my own.
anyone willing to share an example snippet for plotting the resulting layouts or quick tip of library (new to python). if i'm correct i don't seem to find the snippet that generated the documentation drawings for example. thanks.
Is there a way to know if a rectangle was rotated other than looking at it's width height and calculating on my own?
I have n types of bins and I add x quantity of each bin to the packer. The algorithm always does a great job but it usually uses the bins in the order it receives them, therefore it sometimes doesn't output a good solution. I've tried every one of the options for the bin_algo
parameter and also every one of the packing algorithms but in any case it chooses the bins according to the fitness.
I will use a pretty simple example to illustrate this problem, if I have 2 2x2 bins and 2 3x2 bins, and I try to fit 3 1x2 rectangles, the best solution is to put the 3 rectangles inside 1 3x2 bin. But if I don't provide the 3x2 bins first, the output will tell me to use 2 2x2 bins.
When I read the documentation, I thought the PackingBin.BBF
(Bin Best Fit) option would do the job, but maybe I'm missing something.
By the way, thanks for rectpack
, it's a great library.
Hi, I would like to ask, if it is possible to apply rectpack for 3D bin packing problem?
Or if anyone knows about any solution for 3D bin packing problem, please, write :)
Is there a way to count splits and track them so the can be drawn? I am interested in optimizing fewer bins and fewer splits. Thoughts?
Inside the setup.py the library listed there is GPLv2. A bit of a nit but our OSS scanner picked it up.
In my case I really don't worry about performance time so I would like to use different sort order and algorithm to find out the best result. Can you please guide me based on what or how can I compare one result with other to find the best?
I have download and installed this package but found that I could not change bin_algo and sort_algo. I did get sort_algo to work (able to change it) by moving the lamba functions to the main program; but have been uable to access/change bin_algo.
Hello,
first of all thank you very much for this awesome code.
I probably found a small bug and wanted to report it.
In your method geometry::Rectangle::intersects is probably an indention level missing to discard the corner intersects too.
Original code:
def intersects(self, rect, edges=False):
"""
Detect intersections between this rectangle and rect.
Args:
rect (Rectangle): Rectangle to test for intersections.
edges (bool): Accept edge touching rectangles as intersects or not
Returns:
bool: True if the rectangles intersect, False otherwise
"""
# Not even touching
if (self.bottom > rect.top or \
self.top < rect.bottom or \
self.left > rect.right or \
self.right < rect.left):
return False
# Discard edge intersects
if not edges:
if (self.bottom == rect.top or \
self.top == rect.bottom or \
self.left == rect.right or \
self.right == rect.left):
return False
# Discard corner intersects
if (self.left == rect.right and self.bottom == rect.top or \
self.left == rect.right and rect.bottom == self.top or \
rect.left == self.right and self.bottom == rect.top or \
rect.left == self.right and rect.bottom == self.top):
return False
return True
I did the following test on the code:
r = Rectangle(0, 0, 10, 20)
s = Rectangle(10, 20, 10, 20)
print(r.corner_top_r)
print(s.corner_bot_l)
print(r.corner_top_r == s.corner_bot_l)
print(r.intersects(s, edges=True))
print(r.intersection(s, edges=True))
Leading to a result:
P(10, 20)
P(10, 20)
True
False
None
With corrected indention level of the method
def intersects(self, rect, edges=False):
"""
Detect intersections between this rectangle and rect.
Args:
rect (Rectangle): Rectangle to test for intersections.
edges (bool): Accept edge touching rectangles as intersects or not
Returns:
bool: True if the rectangles intersect, False otherwise
"""
# Not even touching
if (self.bottom > rect.top or \
self.top < rect.bottom or \
self.left > rect.right or \
self.right < rect.left):
return False
# Discard edge intersects
if not edges:
if (self.bottom == rect.top or \
self.top == rect.bottom or \
self.left == rect.right or \
self.right == rect.left):
return False
# Discard corner intersects
if (self.left == rect.right and self.bottom == rect.top or \
self.left == rect.right and rect.bottom == self.top or \
rect.left == self.right and self.bottom == rect.top or \
rect.left == self.right and rect.bottom == self.top):
return False
return True
I got the expected result:
P(10, 20)
P(10, 20)
True
True
R(10, 20, 0, 0)
Hope this helps, didn't know if i reported the potential bug correctly.
Best regards
Andreas
Hello,
i would like to discuss the following piece of code.
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from rectpack import newPacker, PackingMode, MaxRectsBl, PackingBin, SORT_NONE, SORT_AREA
def LPack():
packer = newPacker(mode=PackingMode.Offline, bin_algo=PackingBin.BFF, pack_algo=MaxRectsBl, sort_algo=SORT_NONE)
width = 700
height = 500
packer.add_bin(width=width, height=height)
packer.add_bin(width=width, height=height)
packer.add_rect(700, 300)
packer.add_rect(100, 200)
packer.add_rect(300, 300)
packer.add_rect(100, 200)
packer.add_rect(200, 300)
packer.add_rect(200, 300)
packer.add_rect(100, 200)
packer.pack()
fig = plt.figure(figsize=(20, 20))
ax = [fig.add_subplot(2, 2, 1, aspect='equal'),
fig.add_subplot(2, 2, 2, aspect='equal'),
fig.add_subplot(2, 2, 3, aspect='equal'),
fig.add_subplot(2, 2, 4, aspect='equal'),
]
for ix, a in enumerate(ax):
a.set_xlim(0, width)
a.set_ylim(0, height)
a.add_patch(patches.Rectangle((0, 0), width=width, height=height, color='white', fill=False))
if ix in [0, 1]:
a.title.set_text('Implemented BinBestFit')
else:
a.title.set_text('Expected BinBestFit')
for ix, rect in enumerate(packer.rect_list()):
b, x, y, w, h, rid = rect
rect = patches.Rectangle((float(x), float(y)), width=float(w), height=float(h))
ax[b].add_patch(rect)
ax[b].plot(float(x), float(y), 'o', color='red', mew=3, ms=3)
expected = [
(2, 0, 0, 700, 300),
(2, 0, 300, 200, 100),
(3, 0, 0, 200, 100),
(3, 200, 0, 300, 300),
(3, 500, 0, 200, 100),
(3, 0, 100, 200, 300),
(3, 500, 100, 200, 300),
]
for e in expected:
b, x, y, w, h = e
rect = patches.Rectangle((float(x), float(y)), width=float(w), height=float(h), color="red")
ax[b].add_patch(rect)
ax[b].plot(float(x), float(y), 'x', color='black', mew=3, ms=3)
plt.show()
LPack()
As you can see I use the bin_algo=PackingBin.BBF. Looking at the resulting plots from BFF and BBF I was confused because they are the same. This made me curious, so i debugged a bit and it seems like you are just using the open_bins to evaluate the BinBestFit. Is this intended?
I expected with a BinBestFit approach that the packing would consider all bins right away for placing a rect. In the code fragment above I also inserted the packing I'd expected and added a plot.
What do you think about this?
Have a good weekend and thank you for your work.
I hava serval rectangles: [[95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262], [95, 412], [136, 262], [136, 262]]
bin size: [(889,1194),]
I use SORT_AREA,
I do a loop for all the Guillotine,
the result is , it can not pack all the rect, but in photoshop, I can pack it manually
in ps :
in python:
https://imgur.com/vqW4SCw
Is there any way to have this pack starting at a different origin corner, say the bottom left? Or is the only solution to pack normally and then mirror the coordinates?
is it possible to add gap between two rectangles, if it is possible please give a solution thank you.
It would be great to add an optional parameter in Packer.add_rect to control either if each rectangle allow to be rotated or not.
As the title says. Nose hasn't seen an update since Jun 2, 2015.
The official nose
homepage says:
Note to Users
Nose has been in maintenance mode for the past several years and will likely cease without a new person/team to take over maintainership. New projects should consider using Nose2, py.test, or just plain unittest/unittest2.
Pytest is a drop in replacement that requires no changes to the tests and has widespread adoption and ongoing support.
Output from running this on my machine:
❯ pytest tests
================================== test session starts ==================================
platform darwin -- Python 3.8.2, pytest-6.0.1, py-1.9.0, pluggy-0.13.1
rootdir: /Users/work/PycharmProjects/rectpack
collected 167 items
tests/test_collisions.py ................ [ 9%]
tests/test_decimal.py ....... [ 13%]
tests/test_enclose.py .... [ 16%]
tests/test_factory.py ........ [ 20%]
tests/test_geometry.py ....................... [ 34%]
tests/test_guillotine.py .......... [ 40%]
tests/test_maxrects.py ............. [ 48%]
tests/test_packer.py .............................................. [ 76%]
tests/test_skyline.py ................................. [ 95%]
tests/test_stats.py .. [ 97%]
tests/test_waste.py ..... [100%]
===================================167 passed in 19.50s ===================================
I believe it would just be a matter of replacing install_requires = ['nose', 'unittest2'],
with install_requires = ['pytest'],
in the setup.py
Thoughts?
Hi thank you for your work.
In my case could you please tell me is there a way in this library, to pack rectangles to a bin that has already packed rectangles..
I have a number of STL files that I would like to 3D print. It is simple enough to read a bill of materials and pack the bounding boxes of the objects into a bin the size of my printer's base. However, I need to guess the number of bins that will be produced. I'd like a way to produce unlimited bins of a size, instead having to know ahead of time.
While using SkylineBlWm I had an issue with guillotine.py
In function self._add_rect we can see the following lines (187-189) :
# Remove section, split and store results
self._sections.remove(section)
self._split(section, width, height)
Which remove the concerned section and then execute the split.
However, self._split function can sometimes call self._split_horizontal which has the following lines of code (66-69) :
# First remove the section we are splitting so it doesn't
# interfere when later we try to merge the resulting split
# rectangles, with the rest of free sections.
self._sections.remove(section)
When this situation occurs, self._section tries to remove a section that has already ben removed earlier and we get an error.
This line should probably be deleted from self._split_horizontal
Thank you!
Given the example (run with python3):
from rectpack import newPacker
rectangles = [(100, 30, 'aaa'), (40, 60, 'bbb'), (30, 30, 'ccc'),(70, 70, 'ddd'), (100, 50, 'eee'), (30, 30, 'fff')]
bins = [(100, 100), (80, 40), (80, 150)]
packer = newPacker()
# Add the rectangles to packing queue
for r in rectangles:
packer.add_rect(*r)
# Add the bins where the rectangles will be placed
for b in bins:
packer.add_bin(*b)
# Start packing
packer.pack()
# Full rectangle list
all_rects = packer.rect_list()
for rect in all_rects:
b, x, y, w, h, rid = rect
print(rect)
and the output:
(0, 0, 0, 100, 50, 'eee')
(0, 0, 50, 100, 30, 'aaa')
(1, 0, 0, 70, 70, 'ddd')
(1, 0, 70, 40, 60, 'bbb')
(1, 40, 70, 30, 30, 'ccc')
(1, 40, 100, 30, 30, 'fff')
It would seem that the solution is not possible. Bin 0 is nicely packed, no issue there. Bin 1 (80x40) is quite over-packed, and Bin 2 is never used.
Am I misinterpreting the bin indexes returned from rect_list
?... meaning is bin index 1 actually Bin 2 and not Bin 1? Or is there an issue here?
Hi,
Firstly, thanks for the amazing code, it helped me a lot during my thesis project!
However, I have a question regarding the sorting method.
What is the difference between sorting by RATIO or sorting by DIFFERENCE?
In practise, items with the largest difference between sides, will also have the highest ratio, right? Or is this a stupid question where I miss something very obvious?
However, I compared all sorting methods with each other, and saw a major difference in performance
Thank again for the code. I am looking forward to your answer.
Regards,
Timo
I saw an open issue #12
But my question is different. Is it possible to define the space between adjacent rectangles, but the distance between the rectangle and the edge of the bin must be 0?
is it possible to use this without setting bin sizes? In my scenario I just want all my rectangles to fit in the smallest space possible, whatever that shape may be
I would like to add some constraints that will let me ensure some rectangles are guaranteed to be in the same bin.
bundled_rid = [["100023","100024","100142"],["73732","73785"]] packer.pack(groups=bundled_rid)
This would result in each bundle in the array of bundles being in the same bin.
Do you have any recommendations on how I might accomplish this using the existing code? Does this seem like a valid use case?
Issue:
In some cases of inputs, the algorithms(tried all the listed algos in the official README.md) are not able to evaluate a fully optimized solution.
Input Case:
Bin Size: 114 X 120
Rectangle Size: 24 X 18
Expected/Optimized output:
Total number of rectangles that can be placed are: 31
PS: These results have been collected from kwickfitonline PCB optimization software
Actual Output:
The maximum rectangles placed provided by rectpack algorithms is: 30
The detailed results are as follows:
Kindly help us with a solution that can be implemented to generate the desired output.
Looks like solution is to add "wheel" to the requirements.txt (or setup.py)
Is it possible to define a space between adjacent rectangles?
Is there an elegant way to find out if a packed rectangle is rotated? This might be a handy feature instead of comparing width or height manually, but I could not find anything.
I need to print the image with the rectangles that are gonna be placed in the bin.
I'm a beginner with python, that's why I dont know how to print what I need.
I would like to use this for an optimization case to see how many boxes fit on one pallet.
Is there a way to have a fixed number of bins (in my case 1) and to get a result if the packed boxes fit?
Or simpler: I have pack items of the same size and I would like to get a packing schema and an answer how many boxes will fit in 1 bin.
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.