Are there any popular algorithms that can be used to pack a number of items into a container. I need to fit a bunch of 2D rectangular objects into the smallest amount of space possible such that no object overlaps another object. The algorithm doesn''t need to be very fast. Any ideas or links? Thanks for your help.

Thanks for the idea, but I have been googling it. All I get are discussions about the various algorithms and heuristics, never the actual algorithms and heuristics themselves. Does anyone know the name of an algorithm or heuristic that solves the 2d bin packing problem?

quote:Original post by Bender77
Are those rectangle allowed to rotate (by increment of 90°)Intuitively I would:

no, they cannot.

quote:
In your case, the goal of the GA is to minimize the empty space in the container.

I found a lot of talk about GAs, too.

quote:
I can''t remember the link, maybe I found that on AIDepot ...

I''ll check it out, thanks.

Alright, I can''t seem to find anything definitive on the web. Everything I read talks about the pros/cons of an algorithm or heuristic, but they never tell you what the actual steps are! So, I''ve devised my own based on something I think is called the "guillotine method" (I don''t know if that is write, but who really cares).

The algorithm goes something like this:

1) Sort rectangles into descending order by height
2) Place the rectangles into the container in a row
3) When you reach the end of the row, drop down to the next line and continue.
4) Repeat until you run out of rectangles.

This algorithm works very well since my rectangles are all very close in size. If you have a more varying array of sizes, this may not work so well. Anyway, unless someone comes along with a better solution, I think my question is answered and the problem is solved.

Here are some images that demonstrate how well this method works for my situation:

The first few results from Googling for "texture packing" look pretty good to me.