最快水平线<->凸多边形交点算法？

Question

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

我能想到的最快的是找到多边形内的最小/最大y坐标（循环重复n次，两个比较和两个存储），然后比较是否最大y。不知何故，我觉得这可能是更“数学”的解决，但我总是以较慢的代码结束（例如矢量方式 - 我需要计算n [i]和n [i + 1]的差异，然后将它们相乘，添加等 - 比2 cmps +商店慢得多）。

Answer 1

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

Answer 2

如果这是一个水平的二维线，那么是的，你所描述的方法可能是最快的。你也可以短路，就好像你在中途通过支票，并且有一个最小值+最大值>和你的y值，然后你有一个交叉点。

Answer 3

如果你每次都必须对原始数据进行处理，那么你可能不会找到任何诀窍让它更快。

如果您可以使用多边形缓存最小/最大Y值，那么您可以通过在每次执行测试时不循环每个顶点节省时间。

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

Answer 4

另一种方法，这里描述： optimal algorithm if line intersects convex polygon。 但是，因为你正在处理正交线，你可以简化它一点:)。因此总的复杂性是log N而不存储值。