algorithm - 如何计算精确覆盖带有矩形孔的矩形板的一组子矩形

Question

比如说，我想从一 block 矩形板上刮掉一些矩形孔。例如，

情况1，孔相交:

一个板 x，其中有孔 0,1,2，矩形 0 和 1 相交。

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  

矩形结构可能像下面的CCRect，协调类型是float:

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

有什么好主意吗？

Answer 1

您的问题缺少约束条件。您想如何优化结果。您是否正在寻求尽可能减少生成的矩形？

边缘是在网格上吗？

我会这样做:

• 从一个大矩形和两种方法开始，一种用于分割矩形，另一种用于连接它们
• 将主矩形分成两部分，作为孔矩形的每一侧。尽可能地延长它们的边界，并沿着这条线分割平面。一旦你这样做了，你最终会得到很多小矩形。我猜你想要尽可能少的矩形。
• 传递一个 - 删除孔:对于每个小矩形，如果坐标填充在开始时的孔矩形内，请将其丢弃。
• 传递两个 - 连接剩余的矩形:对于每个矩形，如果它可以与邻居形成一个矩形，则连接它们

第二遍很棘手，有大量的优化要做。 一个简单的选择是先垂直连接，然后水平连接。这样你最终会得到更大的矩形。

编辑:
如果您在第 1 遍期间构建 BSP 树，则可以显着加快第 2 遍的速度。每次分割时，它都会创建一个新节点，其中 2 个叶子是子矩形。这将使在第 2 遍中找到邻居的速度更快。