CODEWITHSUNDEEP
algorithmbin-packing
Tom
Tom

Reputation: 7091

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

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

I have n rectangles, each with widths of Wn and heights of Hn 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.

Upvotes: 3

Views: 2473

Answers (4)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27357

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.

Upvotes: 1

moinudin
moinudin

Reputation: 138507

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:

Upvotes: 0

zsalzbank
zsalzbank

Reputation: 9867

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

Upvotes: 1

6502
6502

Reputation: 114599

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.

Upvotes: 2

Related Questions