如何用n个矩形近似多边形？
nim*_*cap 5 algorithm geometry computational-geometry
是否有任何算法可以近似给定的多边形,其中n个非重叠的矩形可以提供最大的覆盖范围？通过最大覆盖率,我的意思是,矩形区域的总和最大化.矩形不一定大小相等.
我正在处理的多边形是凸的.如果确切的解决方案很难/昂贵(我期待它),也欢迎简单的良好启发式.
编辑我总是想到用多边形内部的矩形近似多边形,但矩形不完全在多边形内的解也很好.如果是这种情况,则区域的最大化变为区域的最小化.
编辑2我忘了提到这些矩形是正交矩形,即与轴对齐.
- 创建要处理的多边形队列 Q
将初始多边形添加到 Q
从 Q 中移除多边形 P
- 求P的最长边A
- 旋转 P 使 A 位于 X 轴上
- 如果 P 是一个三角形，用 A 中心的垂线将其分割：
- 将两半 G 和 H 添加到 Q 中并转到 3
- （现在，P 有 4 个或更多边）
- 如果 X 和/或 Y 是锐角：
10. 取 P、A 的下一个最长边，然后转到 5
11. 从 A 向上投影一个红色矩形。找到它与 P、B 和 C 相交的 2 个点：
12. 选择较长的（B）并最终确定绿色矩形
13. 将剩余的数字（D、E 和 F）添加到 Q 中
14. 转到3
我意识到这是一个非常古老的问题，但我最近偶然发现了一个类似的问题，我不得不尝试用矩形来近似多边形。使用此处和其他地方提出的一些想法，我从一个内切矩形开始，并在内切矩形周围生成矩形以提供多边形的一般形状。
这种方法适用于凸多边形，并且适用于某些凹多边形 - 特别是如果您采用迭代方法（例如，将输出矩形作为另一个迭代的输入）。
对于极其凹的形状，您可以考虑将多边形分解为凸包，然后应用我上面描述的技术。Bayazit的实施看起来非常有前途。
如果有人感兴趣，我在这里发布了使用内切矩形的实现： https: //github.com/pborissow/Poly2Rect
第一个想法，也许其他人可以改进它。
- 在多边形内部的某个位置放置一个正方形，尽可能远离任何边缘。
- 迭代地 1.) 增长它，2.) 移动它并转动它以最大化它与边缘的距离。直到你无法再种植为止
- 从头开始，同时将放置的矩形的边缘视为多边形的边缘。