algorithm - 在多边形内查找轴对齐的矩形

Question

我正在寻找一种好的算法来在（不一定是凸的）多边形内找到一个轴对齐的矩形。最大矩形会很好，但不是必需的 - 任何可以找到“相当好的”矩形的算法都可以。

多边形也可能有孔，但任何指向仅适用于凸多边形或简单多边形的算法的指针也会有所帮助。

在我的实现中，边的相交测试相当便宜，但“多边形中的点”测试很昂贵，因此理想情况下应该尽量减少。

Answer 1

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
有一个凸算法，参考资料可能值得一看。
不确定它是否可以扩展到非凸的。

Answer 2

一种解决方案是将凹多边形拆分为凸段，然后使用 cobbal 的链接。

由于您确实有两个不同的基本问题，您是否考虑过命中测试问题的其他替代方案，例如使用 BSP 树？您可以通过在多边形上放置一个网格并为每个网格正方形构建一个 BSP 树来进一步加快速度。还是每片叶子最多有一个边的kd树？

编辑：我将详细介绍 kd-tree（出于无聊，即使它可能对任何人都有用）：

kd-trees 具有以下属性：

1. 它们是二进制的
2. 每个非叶节点沿垂直于轴的平面分割空间，每个子节点一侧。例如 root 将空间分成 x < x0 和 x >= x0
3. 树级别沿不同的轴轮流拆分，例如，级别 0（根）垂直于 X 拆分，级别 1 -> Y 等。

要将其用于多边形命中检测，请按如下方式构建树：

1. 选择一个要分割的顶点。（对于平衡的树，最好靠近中间的地方）。
2. 将其他顶点拆分为两组，一组用于拆分的任一侧。上面的顶点不进入任何一组。
3. 将边缘也放入集合中。与分割线相交的任何边都进入两组。
4. 从上述组中递归地构造孩子。

如果选择合适的分割顶点，树的深度应该接近 log(N)，其中 N 是顶点的数量。每个叶节点最多有一条边通过它。要进行命中检测：

1. 找到该点落入的叶子。
2. 如果叶子中有边缘，请比较指向它。如果不是，则该点是在内部还是外部应该很明显（在构建树时将此信息存储在此类叶子中）。

Answer 3

仅供参考，到目前为止，我所拥有的只是蛮力：制作一个网格，对于网格上的点，如果它们在多边形内，则通过依次扩展每个角或边直到它碰到边来制作一系列矩形。然后只选择最大的。

最简单（并且非常有效）的优化只是在检查网格点是否不包含在已构建的矩形之一中后测试它是否在多边形中，因为“矩形中的点”检查速度非常快。

由于显而易见的原因，这相当缓慢且不准确，更不用说不雅了:)

Answer 4

使用耳夹怎么样？您可以在每个三角形中找到最大的轴对齐矩形。然后你可以尝试加入三角形并重新计算你的矩形。