6

Is there any algorithm that can approximate the given polygon with n non overlapping rectangles that gives the maximum coverage? By maximum coverage I mean, the sum of the rectangle areas are maximized. Rectangles are not necessarily equal sized.

The polygons I am dealing are convex. If exact solution is hard/expensive to find (which I am expecting it to be), simple good heuristics are welcome too.

Edit I always thought of approximating the polygon with rectangles inside polygon, but solutions with rectangles not totally inside polygons are also fine. If that is the case, maximization of the area becomes minimization of the area.

Edit 2 I forgot to mention that these rectangles are orthogonal rectangles, i.e. aligned with axises.

4

4 回答 4

8

一种方法是为您的多边形创建一个（在一般情况下为矩形）边界框。计算边界框面积与多边形面积之差。如果差异足够小，您就完成了，如果没有，请继续...

将盒子分成 4 个大小相等的矩形，2x2。找出这些矩形中的哪个完全在多边形内。计算多边形内矩形总面积与多边形总面积之差。如果差异足够小，你就完成了，如果没有继续......

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

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

于 2012-06-06T14:47:39.577 回答
4
  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、B 和 C 相交的 2 个点： 在此处输入图像描述

12. 选择较长的（B）并最终确定绿色矩形

13. 将剩余的数字（D、E 和 F）添加到 Q

14. 转到 3

于 2012-06-06T15:50:46.457 回答
2

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

  • 在多边形内的某处放置一个正方形，尽可能远离任何边缘。
  • 迭代地 1.) 增长它，2.) 移动它并转动它以最大化它与边缘的距离。直到你不能再种植它
  • 从头开始，同时将放置的矩形的边缘视为多边形的边缘。
于 2012-06-06T14:43:34.400 回答
2

我意识到这是一个非常古老的问题，但我最近偶然发现了一个类似的问题，我不得不尝试用矩形来近似多边形。使用这里和其他地方提出的一些想法，我从一个内接矩形开始，并在内接矩形周围生成矩形，以提供多边形的一般形状。

这种方法适用于凸多边形，也适用于某些凹多边形——特别是如果您采用迭代方法（例如，将输出矩形作为输入提供给另一个迭代）。

对于非常凹的形状，您可以考虑将多边形分解为凸包，然后应用我上面描述的技术。Bayazit的实现看起来很有希望。

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

Poly2Rect

于 2019-11-23T23:08:37.250 回答