寻找覆盖给定直角简单多边形的最小矩形集合。

Question

为了进行碰撞检测，我希望将位图转换为尽可能少的矩形集合。问题的更正式描述在标题中已说明。以下是一个例子： 对于多个解决方案的抉择，我更倾向于最大化所有矩形组合覆盖的总面积。例如，上图中的蓝色矩形可以更小，但那不是最优的解决方案。

这个问题有更常见的名称吗？有哪些文献资料？或者有简单的算法可以给出最优解吗？

- orlp

---

你的问题虽然和使用卡诺图进行布尔逻辑最小化的技术不太一样，但看起来非常相似。有一种自动化算法可用于逻辑最小化，称为Quine-McCluskey算法。我想知道如果你尝试以某种方式扩展它，你可能会有所收获。话虽如此，我可能在说一些废话... :D - stormCloud

@NiklasB。这是将图形分解为矩形，而不是用矩形覆盖图形。我没有完全阅读解决方案，但它听起来像是一个明显不同的问题。 - Aaron Dufour

例如，一个简单的十字形状可以由两个重叠的矩形覆盖，但需要切割成3个矩形。 - Aaron Dufour

@nightcracker 我明白了，我的参考确实不适用于你的问题。 - Niklas B.

在这种情况下，问题似乎是NP难的，因此您可能需要寻找一个好的近似解。 - Niklas B.

Answer 1

这个问题可能是NP-hard的，但如果您想要在未经过NP难度约简创建的情况下获得最高质量的解决方案，那么运行整数规划求解器是值得一试的。即使运行时间是个问题，与标准答案进行比较也可能很有用。

实质上，您正在尝试解决称为集合覆盖的问题的一个特殊情况。这是如何将集合覆盖制定为整数规划的。

minimize sum_{white rectangles R} x_R
subject to
for all white points p, sum_{white rectangles R such that p in R} x_R >= 1
for all white rectangles R, x_R in {0, 1}

你只需要编写代码来构建与其输入相应的整数规划实例，调用求解器并获取结果，然后在已知最佳矩形数量 (k) 的情况下进行一次优化即可。

maximize sum_{white rectangles R} area(R) x_R
subject to
for all white points p, sum_{white rectangles R such that p in R} x_R >= 1
for all white rectangles R, x_R in {0, 1}
sum_{white rectangles R} x_R <= k

如果实例很大，那么您可能需要进行一些预处理（求解器通常也可以做到这一点，但是它们必须使用更一般的算法，这可能不如有效）。首先，只使用最大的白色矩形，即不包含在更大白色矩形中的矩形。可能有聪明的枚举算法，但您应该先实现朴素的算法并对整个系统进行基准测试。其次，仅使用某些点。特别地，如果p和q是不同的点，并且p属于q所属的每个最大矩形，则跟踪p是多余的。

- David Eisenstat

---

整数规划的真正好处在于，如果您决定要权衡覆盖一些黑色像素和减少矩形之间的关系，那么与修改自定义算法相比，调整程序会更容易。 - David Eisenstat

Answer 2

我建议从尚未被矩形覆盖的外部角落开始，贪心地扩展该矩形。重复此过程直到覆盖所有内容。我认为这并不能在全局范围内给你所需的决策优先权（因为你可能有多个选项来贪婪地扩展每个矩形），但在局部范围内是可以的。

- Sneftel

---

@nightcracker 当然可以。只需确保您在整个图像中搜索未覆盖的点即可。 - Mark Ransom

@MarkRansom 这是一个反例。 X不会被覆盖，因为无论从哪个角落开始，算法都会贪心地选择长边。 - orlp

在我的前一个反例中，即使你从洞的角落之一开始，你仍然无法覆盖X，因为它会沿着长边增长（因为它更大）。 - orlp

@NiklasB. 首先，仅沿一个轴增长不是更糟吗？http://i.imgur.com/oFw64Ve.png - orlp

@nightcracker 好的，在这种情况下，甚至是最优的（不要忘记沿着另一个轴增长），但样本并不是非常困难。此外，我指的是选择在角落处未覆盖的“像素”，而不是未覆盖的角落。 - Niklas B.

Answer 3

我以一种足够好的方式解决了这个问题——虽然可能不是最优解。

1. 创建一个尺寸与位图相同的二维数组。对于位图中的每个黑色像素，将相应的元素设置为WALL，否则为空的空间EMPTY_SPACE。

2. 从左到右、从上到下扫描数组，找到第一个EMPTY_SPACE，保存该坐标。

3. 创建一个面积为1的矩形，其左上角坐标设置为在步骤2中找到的坐标，向下和向右各延伸1个单位。

4. 水平扩展矩形向左和向右，只要不覆盖任何 WALL。

5. 垂直扩展矩形向上和向下，只要不覆盖任何 WALL。

6. 标记矩形覆盖的任何元素为COVERED_SPACE，并将矩形添加到矩形集合中。

7. 如果仍有包含 EMPTY_SPACE 的元素，请转到步骤2，否则完成。

- orlp