如何計算一組精確覆蓋矩形板矩形板的矩形板

Question

說，我想從矩形板上劃出一些矩形板。例如，

情況1，孔相交：

與孔0,1,2在其中，矩形0和1個相交BORAD X。

xxxxxxxxxxx 
xxxxxx222xx 
x000xx222xx 
x00011222xx 
x00011xxxxx 
xxx111xxxxx 
xxxxxxxxxxx 

或更簡單的，情況2，無孔相交：

xxxxxxxxxxx 
xxxxx2222xx 
x00xx2222xx 
x00xx2222xx 
x00x111xxxx 
xxxx111xxxx 
xxxxxxxxxxx 

後者更像「反轉一組矩形的一個大矩形中」。

我的問題是：如何計算一組精確覆蓋電路板x的子矩形？

Input: a larger rect, and a set of hole rects 
Output: a set of sub rects cover exactly the larger rect with holes 

的RECT結構可以像下面CCRect，協調類型爲浮動：

typedef struct {float x; float y;} CGPoint; 
typedef struct {float width, float height} CGSize; 
typedef struct {CGPoint origin; CGSize size;} CGRect; 

任何偉大的想法？

Answer 1

在你的問題中有一個缺失的約束。您想如何儘可能減少長方形，您如何優化resutlt？

網格上的邊緣？

我會做這樣的：

• 開始與一個大的矩形和兩個方法，一個是分裂矩形，其他FO加入他們
• 一分爲二的主要矩形的每個邊孔矩形。儘可能地擴展邊界，沿着這條線分割飛機。一旦你這樣做了，你最終會有很多小矩形。我想你想有儘可能少的矩形。
• 通過一個 - 刪除孔：對於每個小矩形，如果座標填充在開始時的孔矩形內，請將其丟棄。
• 傳遞兩個 - 加入剩餘的矩形：每個矩形，如果能夠形成與鄰居長方形，加入他們的行列

該通票，二是棘手的，有萬噸優化在那裏做的。 一個簡單的選擇將是垂直連接然後水平連接。這樣你將會得到更大的矩形。

編輯：
可以加速比dramaticaly如果你建立通1.每次分裂時期間BSP樹第2步完成，它創建一個新的節點，在2個葉是孩子矩形。這將使它在通過2中找到鄰居要快得多。