铺设了重叠的矩形

我想布局一堆重叠的开出这样的矩形：铺设了重叠的矩形

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

我想了两遍算法大致是：

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

但是，我对这种算法很谨慎，因为我不确定它是否会在所有情况下正确布局，并且可能会非常慢。你认为这个算法可以工作吗？你能提出一些更好的算法的建议吗？

来源

2010-01-01 cheez

你的伪代码需要一点工作... “rect.size - = RECT_SIZE;”应该是“rect.x - = RECT_SIZE;”，并且如果导致冲突，则需要在最后一次左移之后将其右移一次。 – Sparr 2010-01-02 01:12:54

是的，你是对的。我注意到在执行伪代码之后。我会在问题中解决它。执行后，它的表现通常非常糟糕： -/ – cheez 2010-01-02 01:22:15

嗯，我撒谎，它实际上工作得很好（一些小的边界矩形问题）。x排序不会保留，但我需要x排序尽可能保留 – cheez 2010-01-02 01:33:05

我认为这个问题具有多项式复杂性。假设您的示例仅限于在任意给定点处重叠的两个矩形并不是问题的真正限制，则需要尝试将矩形向右碰撞以产生最佳（最小）结果的每个可能顺序。这是一种空间打包问题，除非你的数据集小到可以暴力破解，否则这些问题很难解决。

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

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

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重叠。您需要做的是从左边距开始并检查可以移动的最左边位置在通矩形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; 
    }

来源

2010-01-02 01:31:20 Sparr

嗯，我认为这实际上修复了我在测试原始代码时发现的错误...它仍然有一些我想修复的奇怪行为。我要去U/L一个我想修复的运行时行为的屏幕截图。 – cheez 2010-01-02 01:50:45

这里是截屏视频。我认为算法本身就是在做正确的事情，但我想要做的是能够尽可能地保持所有矩形的x位置： http：// screencast .com/t/MzYxYmI1Yjg 任何想法？ – cheez 2010-01-02 02:14:41

好的，为了避免选定的矩形重新定位在x轴上，我只是忽略了这个算法。似乎工作。当然，我仍然对创意持开放态度。 – cheez 2010-01-02 02:51:54

你可以使用一个基于物理的方法，其中块是刚体的秋天到左：

不，这不会始终产生最佳结果，但观看过你的视频录像我认为在交互式程序中使用它会非常直观， t合适:)

来源

2010-01-03 12:33:10 James

这是一个非常好的主意。我要为这个原型制作原型，并感谢您抽出宝贵时间查看屏幕录像。 – cheez 2010-01-04 04:43:37

铺设了重叠的矩形

回答

相关问题