Algorithm to determine (x,y) coordinates for rectangles so the area of the surrounding rectangle is minimal?

Question

I hope my title makes sense, but here is what I a trying to do:

I have n rectangles, each with widths of W_n and heights of H_n that I need to arrange so on a two dimensional (x,y) plane the rectangle that they all fit in takes up the least area. I also need to be able to establish what (x,y) corresponds to what rectangle.

I would prefer something in psuedo-code, but can work with many languages.

Thanks for helping.

Answer 1

This is a difficult problem to be solved optimally, however there are some solutions that are not too hard to implement and that represent a good approximations for many uses (e.g. for textures). Try googling for "rect(angle) packing" ... you will find a lot of code that solves the problem.

Answer 2

Sounds NP-complete to me. Kinda like the knapsack problem. Which means there is no real solution. Only good approximations.

Answer 3

It's a variant on 2D bin packing. The fact that your container is flexible, allows for more optimization as well making it more challenging (as in difficult). Drools Planner (open source java) can handle this. At least one implementation (see user mailing list) with Drools Planner exists (not open source). If you need an open source example to start from, probably the cloud balance in drools-planner-examples is a good example to start from.

For an overview of the algorithms you can use, see my answer on a similar question.

Answer 4

Your problem is known as the 2D packing problem. Even the 1D problem is NP-hard. See here for a good article on some approaches along with sample C# code.

Also, see the following questions:

• How can I programmatically determine how to fit smaller boxes into a larger package?
• Where can I find open source 2d bin packing algorithms?