Algorithm to pack items into container

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

§I'll cal the space wher you must pack your rectangles the main area.

1 - sort all rectangles by decreasing surface/area.
2 - go through the list and try to pack the rectangles, favoriting main area edges


I'm also thinking of another method which could work even if it could be slow (not sure however):

Use genetic algorithm, I once found a GA demo demonstrating you're kind of problem.

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

However, the fact that not all rectangles can fit in a single container could male that more complicate, I don't know ... investigate

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



[edited by - bender77 on June 15, 2003 2:53:37 AM]

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.