Joe*_* Gö 16 algorithm geometry polygon rectangles
我正在寻找一个好的算法来找到一个(不一定是凸面)多边形内的轴对齐矩形.最大的矩形会很好,但不是必需的 - 任何可以找到"相当好"的矩形的算法都可以.
多边形也可能有孔,但任何只适用于凸多边形或简单多边形的算法指针也会有所帮助.
在我的实现中,对于边的交叉测试相当便宜,但是"多边形点"测试是昂贵的,因此理想情况下应该最小化.
仅供参考，到目前为止，我所拥有的只是蛮力：制作一个网格，对于网格上的点，如果它们位于多边形内部，则通过依次扩展每个角或边直到碰到边来制作一系列矩形。然后只选择最大的。
最简单（也是非常有效）的优化只是在检查网格点是否不包含在已构造的矩形之一中后测试网格点是否在多边形中，因为“矩形中的点”检查速度非常快。
由于显而易见的原因，这相当缓慢且不精确，更不用说不优雅了:)