我需要解决一个相对简单的问题——我有 n 个顶点凸 2D 多边形和一条带有一些“y”坐标的水平（！）线。我只需要一件事：检查多边形是否与这条线相交（即有2个交叉点）。
我能想到的最快的方法是在多边形内找到最小/最大 y 坐标（循环重复 n 次，两次比较和两次存储），然后比较最小 y <= y < max y。
不知何故，我觉得这可以更“数学”地解决，但我总是以较慢的代码结束（例如矢量方式——我需要计算 n[i] 和 n[i+1] 的差异，然后将它们相乘、相加等 - - 比 2 cmps+stores 慢得多）。
你只需要检查你的多边形是否有一个 y1 < y 和一个 y2 > y 的点。一旦你找到了这两点，你就完成了。如果您可以通过 y 坐标索引您的点，那应该是一个快速查找。
如果它是水平二维线，那么是的，您描述的方法可能是最快的。您也可以将其短路，就好像您在检查中途并且有一个 > 和 < 您的 y 值的最小值 + 最大值，那么您就有一个交叉点。
如果您每次都必须在原始状态下进行，那么您可能不会找到任何技巧来使其更快。
如果您可以使用多边形缓存最小/最大 Y 值，那么您可以通过在每次进行测试时不循环每个顶点来节省时间。
如果您的多边形具有与之关联的对齐边界框，您可以根据框范围而不是多边形对其进行测试，并更快地获得相同的结果。
此处描述了另一种方法： 最佳算法，如果线与凸多边形相交。但是因为您正在处理正交线，所以您可以稍微简化一下:)。因此，在不存储值的情况下，总复杂度为 log N。