查找覆盖给定直线简单多边形的最小矩形集

Question

对于碰撞检测,我想使用尽可能少的矩形将位图转换为一组矩形.标题中描述了对该问题的更正式描述.一个例子:

对于多种解决方案的断路器,如果所有矩形组合所覆盖的总面积最大化,我更喜欢它.例如,上图中的蓝色矩形可能会更小,但这可能是一个不太理想的解决方案.

这个问题有更常见的名称吗？有文献吗？或者是一种提供最佳解决方案的简单算法？

Answer 1

我设法以一种足够好的方式解决了这个问题 - 但它可能不是最佳的。

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

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

3. 创建区域 1 的矩形，将左上角坐标设置为在 2 处找到的坐标，向下和向右延伸 1。

4. 将矩形水平向左和向右延伸，只要它不覆盖任何墙壁。

5. 垂直向上和向下延伸矩形，只要它不覆盖任何墙壁。

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

7. 如果仍然有一个包含 EMPTY_SPACE 的元素，则转到 2，否则就完成了。