鋪設了重疊的矩形

我想佈局一堆重疊的開出這樣的矩形：鋪設了重疊的矩形

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

鋪設了重疊的矩形

回答

相關問題