algorithm - 布置重叠的矩形

Question

我正在尝试布置一堆像这样开始的重叠矩形:

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

我想到的2-pass算法大致是:

// 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;
   }
}

这(可能)以矩形布局结束，如下所示: alt text http://img685.imageshack.us/img685/9963/picture2bc.png

这在美学上并不令人愉悦，所以我想到了第二遍，将它们从最上面开始再次移动到左边:

// 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;
        }
    }
}

我认为这最终应该如下所示(在实践中看起来完全正确):

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

但是，我对这个算法持谨慎态度，因为我不确定它是否在所有情况下都能正确布局，而且它可能真的很慢。你觉得这个算法行得通吗？你能就更好的算法提出一些建议吗？

Answer 1

我认为这个问题是多项式复杂的。假设您的示例在任何给定点仅重叠两个矩形的限制不是问题的真正限制，您将需要尝试将矩形向右碰撞的所有可能顺序，以产生最佳(最宽)结果。这是空间压缩问题的一种形式，除非您的数据集小到足以暴力破解，否则这些问题很困难。

但是，可以对您的伪代码进行一点小的改进，这将在许多情况下提高其性能。

考虑这个期望的最终结果:

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

(一个字符的所有四个都是一个矩形)

您的第一遍会将除 A 之外的所有内容都向右移动，形成一个楼梯。然后在第二遍中，您的代码将拒绝将 B 移动到左边距，因为第一次尝试移动它会与 E 重叠。您需要做的是从左边距开始并检查您可以移动的最左边的位置矩形到 channel 2。

伪代码:

// 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;
    }