在多边形中查找点

Question

我有一个简单的二维多边形，顶点为 3..n。我需要在这个多边形的内部（而不是边界上）找到一个任意点。我怎样才能找到一个？这个问题对于凸多边形来说是微不足道的：只需取三个不在同一条线上的相邻点（因此它们形成一个三角形）。这个三角形的中点保证位于多边形内。但是这种方法不适用于非凸多边形。

   class Point
   {
      public double X, Y;
   }

   Point GetPointInPolygon(Point[] polygon)
   {
      .....
   }

Answer 1

在极值之间的某个纵坐标处画一条水平线（确保穿过多边形）。计算这条线与多边形轮廓的所有交点。这是在多边形边缘上的一个简单循环中完成的，您可以在其中检测边的变化。

你会发现偶数个交叉点。通过增加横坐标对它们进行排序，并选择偶数和奇数交叉点之间的任意点。

这需要时间 O(N)，这是最优的。

如您所见，通过光线投射进行的多边形点测试报告为真。

勘误表：

在最坏的情况下，可以有O(N) 次交集，排序将进行O(N Log(N)) 次操作。实际上，这种情况很少见。

旁注：

如果您有额外的要求，即内部点应与边缘保持足够的距离，您可以执行 offsetting的多边形（内侧），并使用相同的过程在偏移量内选择一个点。不过，偏移量计算绝非易事。

可能的偏移距离是有限的，但我不知道如何找到这个边界。它将对应"deepest"个点。

Find point in polygon