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

c++ algorithm bin-packing
HardCoder picture HardCoder · Jan 16, 2012 · Viewed 11.1k times · Source

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

Answer

Lalaland picture Lalaland · Jan 16, 2012

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.

Related questions

How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More
Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More