Best-Fit Area Problem (Rectangle Fitting Problem)

[telstar1]

I'm trying to come up with an algorithm that will allow me to optimize the area used by a set of rectanges.
I have a fixed number of rectanges, each one has a fixed area, and I'm trying to fit them into a 2D space.
Their length, width, and orientation can be modified as long as their area remains constant.
I've searched the web, and come back with some references, but nothing that completely nails the problem I'm looking to solve.

Anybody have any good ideas or references?

Thanks,
Telstar

 

[Armitage]

Not sure how much this will help, but I've seen references for what you describe in manufacturing fields. Specifically, to minimize the waste in cutting pieces from sheet-stock (plywood, fabric, etc.).
Probably doesn't help to much, but maybe a start on some new search terms!

 

[br0wn]

Try
this site. It has many packing algorithm links.

Packing a non-convex polygon into a 2D space is a NP-hard problem (it's difficult to compute exact solution). However, since your case involves convex polygons, I would assume it would be much simpler and easier.

 

[telstar1]

Thanks both for the information.
The site in the second post is very interesting.
I actually found a pretty detailed analysis on a site called www.cybergeography.org.
Thanks again.

Telstar

 

[Turkey]

So you want to fit these rectangles into another rectangle of minimum area? I don't see what the problem is. If the length and width are variable but the area is constant, then the minimum area will be the sum of the areas of the rectangles, and you can just line the rectangles up in a big stack (for instance). So if your areas were, say 24 in^2, 36 in^2, and 18 in^2, you could just make a rectangle 18" x ((24/18) + (36/18) + (18/18))" (for example) and you will have made a minimum area rectangle composed of the rectangles in question.

This is generally true for rectangles of area A1, A2, ... An and desired side length L.
A rectangle can be formed of size L x ((A1/L) + (A2/L) + ... + (An/L)).

 

[VTHodge]

Take the sum of the Areas: A1 + A2 + . . . An
- This is the area of the final rectangle

The optimum total area will be a square. This is the area with the least perimeter.
- Take the square root of the total area.
- This is the length of each edge of the final area.

Make each of your small rectangles have one edge length be the length you just calculated.
- The total of all the other edges will also equal the calculated length.

Is this what you wanted?