Is there a c++ source/lib to solve 2D Bin Packing with a rectangular bin (not square) and rotation? [closed]

Question

As the title already says I need C/C++ sourcecode or a library that I can use to solve the Bin Packing problem with 2D rectangular shapes where the bin is also rectangular and the rectangles are also being rotated by 90° angles to fit better. I already have all required values, so I need no online packing algorithm.

I only found a lib that deals with a square bin and without rotation which is not really efficient enough for my needs.

I would really appreciate anything C/C++ handling a rectangular bin and rotation.

Thanks.

PS: The required time for the calculation is not important, only the result is.

PPS: It has to be C or C++, and I didn't find anything useful searching stackoverflow...

Busywork

Almost repeat question: #8638285 – Lainelainey

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf is key. That is the reference on 2d bin packing.

You might be able to modify one of the algorithms in there to satisfy your need. I doubt the rotation is needed, the algorithms are pretty advanced as they are.

This (https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp) is an example of how to implement the MaxRects algorithm.

The modification you would probably have to make is at the top of the algorithm, when selecting the next rectangle to use. Simply have it also look at the different orientation of the rectangles along with cycling through the whole list.

Lainelainey

Hi, thanks for your reply. could you please elaborate a little more on where and what changes are necessary to implement the check for rotation ? – Busywork

You can also find the author's code here: github.com/juj/RectangleBinPack – Hardan

Answer 2

I found this thread a few weeks ago, after skim reading the PDF in the answer, and toying around with the authors code, I did a re-write which more suited my needs ( texture atlas packing )

If anyone else is interested... https://github.com/chris-stones/BinPack2D

• Allow user to bundle a data-structure with submitted rectangles ( orig file name, etc )
• Pack multiple bins ( for 2d texture atlas array - GL_EXT_texture_array )

Also, Instead of tracking splitting and joining free rectangles, I track and sort free top left corners. I found it much simpler to implement, with equally good results.

There is no documentation, See ExampleProgram() at the top of the header file.

Bulletproof

Nice implementation, Chris. Code is pretty clean and the packing is of high quality. The brute force intersection test is a considerable performance hog, though. It might be beneficial to have some kind of Kd-tree to reduce the number of tests. Another way to improve performance would be to simply use smaller canvas sizes to reduce the number of rectangles per canvas. – Retaliate