如何计算一组精确覆盖矩形板矩形板的矩形板

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中找到邻居要快得多。