Packing rectangles for compact representation.

Question

I am looking for pointers to the solution of the following problem: I have a set of rectangles, whose height is known and x-positions also and I want to pack them in the more compact form. With a little drawing (where all rectangles are of the same width, but the width may vary in real life), i would like, instead of.

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

something like.

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

All hints will be appreciated. I am not necessarily looking for "the" best solution.

Answer 1

Something like this?

• Sort your collection of rectangles by x-position

• write a method that checks which rectangles are present on a certain interval of the x-axis

  Collection overlaps (int startx, int endx, Collection rects){ ... }

• loop over the collection of rectangles

    Collection toDraw;  
    Collection drawn;  
    foreach (Rectangle r in toDraw){  
    Collection overlapping = overlaps (r.x, r.x+r.width, drawn);  
    int y = 0;  
    foreach(Rectangle overlapRect in overlapping){  
    y += overlapRect.height;  
    }  
    drawRectangle(y, Rectangle);  
    drawn.add(r);  
    }  

Answer 2

Your problem is a simpler variant, but you might get some tips reading about heuristics developed for the "binpacking" problem. There has been a lot written about this, but this page is a good start.

Answer 3

Put a tetris-like game into you website. Generate the blocks that fall and the size of the play area based on your paramters. Award points to players based on the compactness (less free space = more points) of their design. Get your website visitors to perform the work for you.

Answer 4

Are the rectangles all of the same height? If they are, and the problem is just which row to put each rectangle in, then the problem boils down to a series of constraints over all pairs of rectangles (X,Y) of the form "rectangle X cannot be in the same row as rectangle Y" when rectangle X overlaps in the x-direction with rectangle Y.

A 'greedy' algorithm for this sorts the rectangles from left to right, then assigns each rectangle in turn to the lowest-numbered row in which it fits. Because the rectangles are being processed from left to right, one only needs to worry about whether the left hand edge of the current rectangle will overlap any other rectangles, which simplifies the overlap detection algorithm somewhat.

I can't prove that this is gives the optimal solution, but on the other hand can't think of any counterexamples offhand either. Anyone?

Answer 5

Topcoder had a competition to solve the 3D version of this problem. The winner discussed his approach here, it might be an interesting read for you.

Answer 6

I had worked on a problem like this before. The most intuitive picture is probably one where the large rectangles are on the bottom, and the smaller ones are on top, kinda like putting them all in a container and shaking it so the heavy ones fall to the bottom. So to accomplish this, first sort your array in order of decreasing area (or width) -- we will process the large items first and build the picture ground up.

Now the problem is to assign y-coordinates to a set of rectangles whose x-coordinates are given, if I understand you correctly.

Iterate over your array of rectangles. For each rectangle, initialize the rectangle's y-coordinate to 0. Then loop by increasing this rectangle's y-coordinate until it does not intersect with any of the previously placed rectangles (you need to keep track of which rectangles have been previously placed). Commit to the y-coordinate you just found, and continue on to process the next rectangle.