The scenario ：有一个矩形空间，里面有任意放置的任意方向的多边形 . 目的是找到可以安装在矩形空间的空区域内的最大空矩形 . 下面的这些图像说明了多边形为蓝色的情景，虚线表示可以在每个方案中拟合的最大空矩形 .
The problem ：显然，找到最大的空矩形在计算几何中是一个well known problem，但我在这个领域找到的算法涉及在点（CGAL实现了这一点）和线段中找到空矩形 . 有没有办法根据我的场景调整这些现有技术？或者有更简单的方法吗？
The scenario ：有一个矩形空间，里面有任意放置的任意方向的多边形 . 目的是找到可以安装在矩形空间的空区域内的最大空矩形 . 下面的这些图像说明了多边形为蓝色的情景，虚线表示可以在每个方案中拟合的最大空矩形 .
The problem ：显然，找到最大的空矩形在计算几何中是一个well known problem，但我在这个领域找到的算法涉及在点（CGAL实现了这一点）和线段中找到空矩形 . 有没有办法根据我的场景调整这些现有技术？或者有更简单的方法吗？
1 回答
不幸的是，我所熟悉的大多数计算几何文献似乎都生成了很好的算法描述和正确性的证明，而没有实际提供实现 . 也许这是因为实施通常是相当复杂的 .
您没有提到您可以容忍的程度不准确 . 如果你有一些宽容，这个答案适合你 .
我的建议是你 turn this hard problem into an easier problem .
您的多边形集合的
Find the bounding box .
将边界框划分为网格 . 网格越细，准确性越高，但找到解决方案所需的时间越长 .
Find每个网格单元的区域（投射为矩形多边形）与多边形集相交 .
如果重叠足够（大于您指定的某个最小值），请将网格单元标记为零;否则，用一个标记 .
您现在有一个零和一的矩形数组 . 这构成了更容易解决问题的基础： what is the largest rectangular subset of this grid which is composed entirely of ones?
这个更容易解决的问题在互联网上有许多可访问的解决方案（例如1，2，3，4，5，6） .