secnot / rectpack Goto Github PK

How do I get the output to be a plot as shown in the introduction page?

Is there a way to know if a rectangle was rotated other than looking at it's width height and calculating on my own?

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.

code.txt

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

The placement is as follows

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:

• Algo: MaxRectsBl
  29
• Algo: GuillotineBssfSas
  27
• Algo: GuillotineBssfLas
  29
• Algo: GuillotineBssfSlas
  27
• Algo: GuillotineBssfLlas
  29
• Algo: GuillotineBssfMaxas
  29
• Algo: GuillotineBssfMinas
  27
• Algo: GuillotineBlsfSas
  25
• Algo: GuillotineBlsfLas
  30
• Algo: GuillotineBlsfSlas
  26
• Algo: GuillotineBlsfLlas
  28
• Algo: GuillotineBlsfMaxas
  24
• Algo: GuillotineBlsfMinas
  29
• Algo: GuillotineBafSas
  29
• Algo: GuillotineBafLas
  29
• Algo: GuillotineBafSlas
  29
• Algo: GuillotineBafLlas
  29
• Algo: GuillotineBafMaxas
  29
• Algo: GuillotineBafMinas
  29
• Algo: SkylineBl
  29
• Algo: SkylineBlWm
  29
• Algo: SkylineMwf
  29
• Algo: SkylineMwfl
  29
• Algo: SkylineMwfWm
  29
• Algo: SkylineMwflWm
  29
• Algo: MaxRectsBl
  29
• Algo: MaxRectsBssf
  28
• Algo: MaxRectsBaf
  29
• Algo: MaxRectsBlsf
  29

Kindly help us with a solution that can be implemented to generate the desired output.

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

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.

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?

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 :

https://imgur.com/HLH9TcV

in python:
https://imgur.com/vqW4SCw

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.

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?

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.

Hi,

I tried to pack 2 by 3 rectangles to bin sized 4 by 6. If I enable rotation, I get 3 packed rectangles instead 4:

With rotation disabled I get 4 packed rectangles as expected.

I'm running with default settings:

packer = newPacker(rotation=False)
How to fix this?

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

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).

How to specify which rectangles can rotate for best packing, and what cant?

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?

HI Team, Could you please let me know How we can pack rectangles from Right to Left?

Is it possible to define a space between adjacent rectangles?

Looks like solution is to add "wheel" to the requirements.txt (or setup.py)

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?

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?

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:

1. sheet is 2400mm long
2. part is 6000mm
3. for this discussion, we can ignore width as it will be specified and part width is way less than sheet width. when nesting i will use the part width.

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.

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?

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

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.

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.

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.

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 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.

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

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?

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...

• BBF returns bool indicating whether packing succeeded.
• BNF and BBF return a rect if successful or 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).

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:

• add a weight argument to class Rectangle
• add a maxWeight or remainingWeight argument to Bins
• Before adding a Rect to a bin check if weight < maxWeight (or > remainingWeight)
• if Ok add the rect to the bin and modify the maxWeight or remainingWeight arg
• if not ok continue to the next bin of the second one that fit the best.

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

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.

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.

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 :)

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!

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.

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.

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..

is it possible to add gap between two rectangles, if it is possible please give a solution thank you.

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.

Do you have a contact with the developer?

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?

Inside the setup.py the library listed there is GPLv2. A bit of a nit but our OSS scanner picked it up.