Re: Help! - rectangle packing problem

In <1182234140.728635.299230@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> snow <rok.sibanc@xxxxxxxxx> writes:

On Jun 19, 5:41 am, ihinayana <edward...@xxxxxxxx> wrote:
Description:
Given a group of rectangles with different integer width and
height,such as 5*4, 2*3,1*7,etc. The total number of rectangles is
like 10 or more.The problem is how to find a bigger rectangle with a
minimal area which can hold all those given ones. To fix them in,those
rectangles can be rotated with 90 degree and the order is regardless.

Did anybody solve a similar problem?

I was a part of circle packing online competition once, which sounds
very similar.
So you have to place your squares somewhere - x,y coordinates of let
say bottom left corner and also determine rotation.
So your genome would be N times (x,y,angle) where N is the number of
rectangles.

Now for your containing rectangle you will have to find: min x, max x,
min y, max y of all rectangles.
And you have to minimize this rectangle area.

Your fitness also has to take into account possible overlapping areas!
Just add some error for overlapping area.

Simple combinatorial problems like these can be solved to obtain
exact solutions with no need for the complexity of GA's, although they
of course present a perfect opportunity for playing around with them.
All that's needed here is backtracking search. As a trivial example,
suppose the blocks are 5*4, 2*3, and 1*7.

Sum the areas of the rectangles to get the the minimum area that could
hold them all if they fitted together with no gaps, namely 33 units,
then round this up to a multiple of the longest side of any of the
component rectangles, namely 7, so start with a 7*5 rectangle. Now
explore the possible packings of the rectangles into this boundary;
in this trivial case they actually fit. Otherwise, expand the
rectangle to consider 7*6, 7*7, 7*8, 7*9, 8*8, 7*10, 8*9, etc.

HTH,
David

.

Relevant Pages

  • Re: Termination of a vertical line
    ... someplace near the top and draw to some place near the bottom. ... Name your rectangles something ... >>> I have a report header, a page header and a page footer. ... Dim intNumLines As Integer ...
    (microsoft.public.access.reports)
  • Re: Termination of a vertical line
    ... I had top and bottom margins of .5" ... Dim intPageHeadHeight As Integer ... How do you get the bottom of the> rectangles ... >>>>> I have a report header, a page header and a page footer. ...
    (microsoft.public.access.reports)
  • Re: iBook + iBook = iBook..
    ... The trick I use is to draw 'maps' - one A4 page has two rectangles ... representing the top and bottom of the inside (ie with CD drive, ... Insufficient system resources exist to complete the API. ...
    (uk.comp.sys.mac)
  • Re: Printing A Serrated Border
    ... The rectangles worked. ... >>bottom of the page and use the text direction function to make it vertical. ... >>> sideways every half inch. ...
    (microsoft.public.powerpoint)
  • Re: Printing A Serrated Border
    ... The rectangles worked. ... >of the rectangles at the bottom of the slide. ... >> rectangles sideways every half inch. ...
    (microsoft.public.powerpoint)