如何用n个矩形来近似表示一个多边形？

Question

有没有一种算法可以用n个不重叠的矩形近似表示给定的多边形，并使覆盖面积最大化？所谓的最大覆盖是指矩形面积之和最大化。矩形不一定是相等大小。

我处理的多边形是凸的。如果很难/昂贵找到确切的解决方案（我预计会这样），那么简单而好的启发式方法也是可以接受的。

编辑：我一直认为用多边形内部的矩形来近似表示多边形，但是矩形不完全在多边形内的解决方案也是可以的。如果是这种情况，面积最大化变为面积最小化。

编辑2：我忘了提到这些矩形是正交矩形，即与坐标轴对齐。

- nimcap

---

你能提供更多信息吗？我想知道你想获得什么信息（矩形数量，总面积和，浪费空间的百分比）。此外，还有一些需要指定的内容：您是否希望用最少的矩形实现最大的面积覆盖？因为使用许多1mm^2的矩形可以相当精确地近似面积。如果是这样，那么这听起来像http://en.wikipedia.org/wiki/Multi-objective_optimization。也许您可以将问题投影到多重背包问题上。 - Slomo

@Slomo：我会将多边形和矩形数量作为输入提供。这样足够了吗？ - nimcap

好的，谢谢。基于这个，Jens Schauder 的第一个想法似乎是合理的。由于您只有凸多边形，最大矩形将位于中心。因此，您可以递归地查找下一个较小剩余区域的最大矩形。当您达到第 n 个矩形（输入）时，递归将停止。 - Slomo

这里有一个关于“正则”多边形的有趣解决方案：https://dev59.com/5E_Sa4cB1Zd3GeqP-Tax。 - smirkingman

这里有一个非常好的方法，用于寻找最大正交矩形：http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/ - smirkingman

Answer 1

一种方法是为您的多边形创建一个（通常是矩形的）边界框。计算边界框面积与多边形面积之间的差异。如果差异足够小，则完成，否则继续...

将框分成4个相等大小的矩形，2x2。找出其中完全在多边形内部的矩形。计算多边形内部矩形和多边形面积之间的总面积差异。如果差异足够小，则完成，否则继续...

将每个4个矩形分成4个子矩形...如果在任何阶段您发现一个矩形完全在或完全不在多边形内，则可以将其从下一次迭代的矩形列表中删除。

换句话说，使用四叉树将包含多边形的空间划分，并将其扩展到满足精度标准的程度。

- High Performance Mark

Answer 2

1. 创建一个多边形队列 Q，以便处理

2. 将初始多边形添加到 Q 中

3. 从 Q 中删除一个多边形 P

4. 找到 P 的最长边 A
5. 旋转 P，使得 A 在 X 轴上
6. 如果 P 是三角形，则用垂直于 A 的线在中心处分割它：
7. 将两个半部分 G 和 H 添加到 Q 中，并转到第 3 步
8. (现在，P 具有 4 个或更多的边)
9. 如果 X 和/或 Y 是锐角:

10. 取 P 的下一条最长边 A，并转到第 5 步

11. 从 A 向上投射一个红色矩形。找到它与 P 相交的 2 个点 B 和 C：

12. 选择较长的 B 并完成绿色矩形

13. 将剩余的图形（D、E 和 F）添加到 Q 中

14. 转到第 3 步

- smirkingman

Answer 3

我知道这是一个非常老的问题，但最近我遇到了一个类似的问题，我必须尝试用矩形来逼近一个多边形。使用这里和其他地方提出的一些想法，我从内接矩形开始（inscribed rectangle），并在内接矩形周围生成矩形，以提供多边形的大致形状。

这种方法对于凸多边形效果很好，对于某些凹多边形也还可以 - 特别是如果您采用迭代方法（例如将输出矩形作为另一个迭代的输入）。

对于极度凹形状，您可能需要将多边形分解为凸包，然后应用我上面描述的技术。Bayazit 的实现看起来非常有前途。

如果有人感兴趣，我已经发布了我的内接矩形实现：https://github.com/pborissow/Poly2Rect

- Peter

Answer 4

一个想法，也许其他人可以改进它。

• 在多边形内部某个位置放置一个正方形，尽可能远离任何边缘。
• 迭代地 1.) 扩大它， 2.) 移动并旋转它以最大化其与边缘的距离。直到无法再扩大为止
• 从头开始，同时考虑放置矩形的边缘作为多边形的边缘。

- Jens Schauder