Laying out overlapping rectangles

Question

I am trying to layout a bunch of overlapping rectangles that start out like this:

alt text http://img690.imageshack.us/img690/209/picture1bp.png

The 2-pass algorithm I thought up is roughly:

// Pass 1 - Move all rectangles to the right until they do not overlap any other rectangles
rects = getRectsSortedOnTopLeft(); // topmost first, all rects same size
foreach(rect in rects)
{
   while(rect.collidingRects().size() != 0)
   {
       rect.x += RECT_SIZE;
   }
}

This (probably) ends up with rectangles laid out like: alt text http://img685.imageshack.us/img685/9963/picture2bc.png

This is not aesthetically pleasing so I thought of a second pass which would move them all left starting again from the topmost:

// Pass 2
foreach(rect in rects)
{
    while(rect.x >= LEFT_MARGIN)
    {
        assert(rect.collidingRects().size() == 0);
        rect.x -= RECT_WIDTH;
        if(rect.collidingRects().size() != 0)
        {
           rect.x += RECT_WIDTH;
           break;
        }
    }
}

I think this should end up looking like below (looks exactly correct in practice):

alt text http://img511.imageshack.us/img511/7059/picture3za.png

However, I am wary of this algorithm because I am not sure if it will lay out correctly in all cases and it may be really slow. Do you think this algorithm can work? Can you make some suggestions on a better algorithm?

Answer 1

I think that this problem is of polynomial complexity. Assuming your example's limitation of only two rectangles overlapping at any given point is not a true limitation of the problem, you would need to try every possible order of bumping the rectangles to the right in order to produce the optimal (least wide) result. This is a form of space packing problem, and those are Hard unless your data set is small enough to brute force.

However, one small improvement to your pseudocode is possible, which would improve its performance in many cases.

Consider this desired final result:

A
A C
A C E
A C E
B C E
B D E
B D F
B D F
  D F
    F

(where all four of one character are a single rectangle)

Your first pass would move everything except A to the right, forming a staircase. Then in the second pass your code would decline to move B to the left margin, because the first attempt to move it would overlap with E. What you need to do is start at the left margin and check for the leftmost position you can move each rectangle to in pass 2.

Pseudocode:

// Pass 1 - Move all rectangles to the right until they do not overlap any other rectangles
rects = getRectsSortedOnTopLeft(); // topmost first, all rects same width
foreach(rect in rects)
    while(rect.collidingRects())
        rect.x += RECT_WIDTH;
// Pass 2 - Move all rectangles to the leftmost position in which they don't overlap any other rectangles
foreach(rect in rects)
    for(i=LEFT_MARGIN; i+=RECT_WIDTH; i<rect.x)
    {
        o = rect.x;
        rect.x = i;
        if(rect.collidingRects())
            rect.x = o;
    }