2D與障礙

Question

任何人都知道一個高效的算法，其中包含障礙物的正方形移動矩形的包裝？

矩形：

• 可以旋轉
• 可以移動/瞬移
• 不得有障礙物（黑方塊）

障礙碰撞：

• 不能被移動
• 可以添加到任何地方

目標：當添加障礙物時，嘗試移動矩形，使它們不與任何障礙物碰撞。

State 1 http://img440.imageshack.us/img440/6995/59737192.png

State 2 http://img87.imageshack.us/img87/2336/28560269.png

State 3 http://img406.imageshack.us/img406/5469/30594959.png

State 4 http://img683.imageshack.us/img683/81/88927554.png

State 5 http://img25.imageshack.us/img25/3657/83405570.png

Answer 1

看看這個：Dynamic programming - Largest square block
基本上，考慮到REC纏結，你添加一個障礙，並刪除障礙干擾的廣場。
然後，運行連接算法（用「限制器」是所述障礙和現有正方形），並且如果一個地方發現，可以適合的N×N大小的方形（N是矩形的大部分），並添加長方形）。
這可以優化遠一點，我委託你這樣做。 （基本上 - 矩形不會總是被擺在最優化的地方這可以補救，至少在一定程度上）
此解決方案讓您O（n）的時間和空間，每個障礙增加。
可能修改你還應該考慮：不要重建對每個障礙物陣列，但構建它的空隙中，障礙物陣列，和你一起去修改它。這將節省通過整個陣列的每一個障礙。