在多边形内寻找一个轴对齐的矩形

Question

我正在寻找一个好的算法来在一个（不一定是凸多边形）中找到一个轴对齐的矩形。最大矩形比较好，但并非必须——任何能够找到“相当不错”的矩形的算法都可以。

多边形也可能有洞，但任何只适用于凸或简单多边形的算法的指针也将很有帮助。

在我的实现中，边缘的相交测试比较便宜，但点在多边形内的测试比较昂贵，因此最好将其最小化。

- Joel in Gö

---

你认为“点在多边形内”测试很重吗？大多数情况下，它只是对构成多边形的所有点进行“大于”和/或“小于”测试，只有在某些情况下才会进行线段相交测试。或者...？ - Dan Byström

我不确定你的意思...在检查了边界矩形之后，我使用偶数奇数交叉测试来测试半线。这最终会测试很多边，如果多边形有很多边，那么速度就会变得相当慢。 - Joel in Gö

你能提供一些数据集的链接吗？这听起来很有趣，我想试试。 - Jeremy French

抱歉，我这里只有数据库。 - Joel in Gö

我还需要它用于另一个任务：找到一个可以在钢板上刻写零件号的空间，该钢板可能是任何形状，有钻孔等。 - Joel in Gö

Answer 1

这里有一个凸优化算法，参考文献值得一看。不确定是否可以扩展到非凸情况。

- cobbal

---

哇，不错的链接，谢谢。 - anhoppe

Answer 2

一种解决方法是将凹多边形分割成凸多边形，然后使用cobbal的链接。

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

编辑：我会详细说明kd-tree（即使这可能对任何人都没有用处，因为我感到无聊）：

kd树具有以下属性：

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

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

1.选择要沿其分割的顶点。（最好在中间附近，以获得平衡的树）。 2.将其他顶点分成两组，一组在分割的一侧，另一组在另一侧。上述顶点不进入任何一组。 3.将边缘也放入集合中。与分割线相交的任何边都将进入两个集合。 4.从上述组递归构造子代。

如果选择了适当的分裂顶点，则该树的深度应接近log（N），其中N是顶点数。每个叶子节点最多只有一条边通过它。要进行命中检测：

1.找到点所在的叶子。 2.如果叶子中有一条边，请将点与其进行比较。如果没有，则显然可以确定该点是内部还是外部（在构建树时将此信息存储在这样的叶子中）。

- TrayMan

---

一直在避免它...你知道一个好的入门介绍吗？谢谢 :) - Joel in Gö

我不能提供任何东西，但你可以轻松地在谷歌上搜索到很多相关的内容，而我刚刚写的应该能够给你一个大致的想法。 - TrayMan

Answer 3

仅供参考，目前我所拥有的是暴力破解：制作一个网格，在网格上的点如果在多边形内部，则通过逐个扩展每个角落或边缘直到触碰边缘来制作一系列矩形。然后选择最大的矩形。

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

由于明显的原因，这种方法相当缓慢和不精确，更不用说不雅观了 :)

- Joel in G&#246;

---

就我个人来说，建立经过每个顶点的水平和垂直线，而不是一个均匀的网格。 - Agnel Kurian

假设多边形没有很多近似曲线的小边。 - Joel in Gö

我使用了这个方法的一个变种，效果很好。基本上，我将多边形切成了16个测试点（根据边界矩形的尺寸，每行4个，共4行）。由于样本列表非常有限，我只需要通过检查新点是否产生完全位于几何图形内部的矩形来扩展我的矩形。对于我的目的来说，它运作得非常好。 - Berin Loritsch

Answer 4

使用剪耳算法如何？您可以在每个三角形中找到最大的轴对齐矩形。然后，您可以尝试连接三角形并重新计算矩形。

- Josh C.