1

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

情况1、孔相交：

一个带有孔 0,1,2 的 borad x，矩形 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

rect 结构可能像下面的 CCRect，协调类型是浮点数：

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

有什么好主意吗？

4

1 回答 1

1

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

边缘是否在网格上？

我会这样做：

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

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

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

于 2012-09-18T15:20:47.267 回答