Non-optimal solution when rectangles are rotated

secnot / rectpack

Python 2D rectangle packing library

Apache License 2.0

463 stars 104 forks source link

Open harriv opened 6 years ago

harriv commented 6 years ago

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?

secnot commented 6 years ago

Packing is a np-hard problem so the algorithms used are heuristic, this means that they usually won't find the optimal solution.

But you can improve your solution in two ways:

If the number of rectangles is small you can search all the possible combinations using DFS and choose the optimal.
If the number of rectangles is too big, you can use this library and create several packers with different algorithms and options, then choose the best packing between them.

harriv commented 6 years ago

SkylineMwfWm algorithm seems to solve at least this problem ok.