在其他多边形中找到最大的空矩形的算法

Question

场景:有一个矩形空间，里面有任意方向任意放置的多边形。目的是找到可以容纳在矩形空间的空白区域内的最大的空白矩形。下面的这些图片说明了场景，其中蓝色的多边形和虚线表示每个场景中可以容纳的最大空矩形。

问题:显然，找到最大的空矩形是一个 well known problem在计算几何中，但我在这个领域找到的算法处理在点(CGAL 已经实现了这个)和线段之间寻找空矩形。有没有办法针对我的场景调整这些现有技术？或者有更简单的方法吗？

Answer 1

不幸的是，我所熟悉的大多数计算几何文献似乎都生成了对算法的漂亮描述和它们正确性的证明，而没有实际提供实现。也许这是因为实现通常相当复杂。

你没有提到你可以容忍多大程度的不准确。如果您有一定的容忍度，这个答案适合您。

我的建议是您将这个困难的问题变成一个更简单的问题。

1. Find the bounding box您的多边形集合。
2. 将边界框划分为网格。网格越精细，您的准确性就越高，但找到解决方案所需的时间就越长。
3. Find每个网格单元(转换为矩形多边形)有多少面积与多边形集相交。
4. 如果重叠足够大(大于您指定的某个最小值)，则用零标记网格单元；否则，用一个标记。
5. 您现在有了一个由 0 和 1 组成的矩形数组。这构成了更简单的问题的基础:这个完全由 1 组成的网格的最大矩形子集是什么？

这个更简单的问题在互联网上有许多可用的解决方案(例如 1、2、3、4、5、6)。