如何确定一个点是否在一个2D凸多边形内部比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)

另一种可视化想法的方法是,您可以将多边形视为三角形扇形.然后,您首先测试您的点与中间内边缘的对比.这将消除风扇中一半可能的三角形.由于半个三角扇仍然是三角扇,你可以递归地执行此操作,直到你的扇子中只剩下一个三角形,然后你可以明确地测试它.

一个真正的实现需要一些索引杂耍,但在其他方面是简单而强大的.