algorithm - 如何快速判断一个点是否在二维凸多边形内 N 次

Question

我知道用于查找点是否在任何多边形内部的标准光线转换算法。但是，如果您仅限于凸多边形，是否有更快的方法？

Answer 1

是的，您可以使用二进制搜索。您可以通过递归地将多边形切割为其大小的一小部分(即一半)并检查您在哪一侧来执行此操作。例如，您可以首先检查您是在通过顶点 0 和顶点 n/2 的直线的正侧还是负侧。一旦你有 3 个顶点，你只需测试剩下的两条边，完成与那个三角形的测试。

这里有一些伪代码，希望能使这更容易理解:

function TestConvexPolygon(point, polygon)
  if polygon.size == 3 then
    return TestTriangle(point, polygon) // constant time

  if (TestLine(point, polygon[0], polygon[polygon.size/2]) > 0)
    return TestConvexPolygon(point, new polygon from polygon.size/2 to polygon.size-1 and 0)
  else
    return TestConvexPolygon(point, new polygon from 0 to polygon.size/2)

另一种可视化方法是，您可以将多边形视为三角形扇形。然后，您首先测试您的点与中值内部边缘。这将从扇形中消除一半可能的三角形。由于半个三角形扇仍然是三角形扇，您可以递归地执行此操作，直到您的扇中只剩下一个三角形，然后您可以显式测试它。

真正的实现需要一些索引处理，但在其他方面很简单且健壮。