Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


Algorithm to pack items into container


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 spiffgq   Members   -  Reputation: 122

Like
Likes
Like

Posted 14 June 2003 - 06:47 PM

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.

Sponsor:

#2 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 14 June 2003 - 07:30 PM

Two-dimensional packing problem. Google it.

#3 Bender77   Members   -  Reputation: 122

Like
Likes
Like

Posted 14 June 2003 - 07:51 PM

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]

#4 spiffgq   Members   -  Reputation: 122

Like
Likes
Like

Posted 14 June 2003 - 07:56 PM

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?

#5 spiffgq   Members   -  Reputation: 122

Like
Likes
Like

Posted 14 June 2003 - 07:58 PM

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.



#6 spiffgq   Members   -  Reputation: 122

Like
Likes
Like

Posted 14 June 2003 - 11:11 PM

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:







#7 pieman   Members   -  Reputation: 122

Like
Likes
Like

Posted 15 June 2003 - 09:59 AM

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





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS