Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

spiffgq

Algorithm to pack items into container

This topic is 5539 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Two-dimensional packing problem. Google it.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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:





Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!