最快的水平线＆lt; - ＆gt;凸多边形交叉算法？

Question

我需要解决一个相对简单的问题 - 我有n个顶点凸2D多边形和水平（！）线有一些'y'坐标。我只需要一件事：检查多边形是否与这条线交叉（即有2个交叉点）。

我能想到的最快的是找到多边形内的最小/最大y坐标（循环用两个比较和两个存储重复n次），然后比较min y <= y＆lt;最大。

不知何故，我觉得这可以通过“数学”更多地解决。但我总是以较慢的代码结束（例如矢量方式 - 我需要计算n [i]和n [i + 1]的差异，然后乘以它们，添加等 - 比2个cmps +存储慢得多）。 / p>

Answer 1

你只需要检查你的多边形是否有一个y1＆lt;的点。 y和y2＆gt;年。一旦你找到了这两点，你就完成了。如果你可以用y坐标索引你的点，那应该是快速查找。

Answer 2

如果它是水平的2d线然后是，你描述的方法可能是最快的。你也可以将它短路，好像你在检查中途，并且最小+最大值是＆gt;和＆lt;你的y值然后你有一个交集。

Answer 3

如果你必须每次都使用原始版本，那么你可能不会找到任何技巧来使它更快。

如果可以使用多边形缓存最小/最大Y值，那么每次进行测试时都不会循环每个顶点，从而节省时间。

如果多边形具有与之关联的对齐边界框，则可以针对框范围而不是多边形对其进行测试，并更快地获得相同的结果。

Answer 4

此处描述了另一种方法： 如果线与凸多边形相交，则为最佳算法。 但是因为你正在处理正交线，你可以稍微简化一下:)。因此，总复杂度是log N而不存储值。