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

Question

对于碰撞检测，我想将位图变成一组矩形，使用尽可能少的矩形。标题中描述了更正式的问题描述。一个例子:

对于多个解决方案的决胜局，如果所有矩形组合覆盖的总面积最大化，我会更喜欢它。例如，上图中的蓝色矩形本来可以更小，但这并不是最佳解决方案。

这个问题有更通用的名称吗？有文献吗？还是给出最优解的简单算法？

Answer 1

这个问题可能是 NP-hard 问题，但如果您想要为不是由 NP-hardness 减少创建的实例提供最高质量的解决方案，那么运行 integer programming求解器值得一试。即使运行时间是一个问题，拥有一个黄金标准进行比较可能还是有用的。

本质上，您正在尝试解决一个名为 set cover 的问题的特例.这就是集合覆盖可以被表述为整数规划的方式。

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 是多余的。