如何确定点是否在 2D 凸面内？

此页面：http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html 显示了如何对任何多边形执行此操作。

我有一个Java实现，但它太大了，无法完整地发布在这里。但是，您应该能够解决它：

class Boundary {
    private final Point[] points; // Points making up the boundary
    ...


    /**
     * Return true if the given point is contained inside the boundary.
     * See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     * @param test The point to check
     * @return true if the point is inside the boundary, false otherwise
     *
     */
    public boolean contains(Point test) {
      int i;
      int j;
      boolean result = false;
      for (i = 0, j = points.length - 1; i < points.length; j = i++) {
        if ((points[i].y > test.y) != (points[j].y > test.y) &&
            (test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
          result = !result;
         }
      }
      return result;
    }
}

这是 Point 类的草图

/**
 * Two dimensional cartesian point.
 */
public class Point {
  public final double x;
  public final double y;
  ...
}

对于那些想了解Dean Povey上面写的方法是如何工作的，这里有一个解释：

该方法查看从测试点开始并延伸到X轴右侧的无穷大的“射线”。对于每个多边形线段，它会检查光线是否与它相交。如果线段交叉的总数为奇数，则将测试点视为面内，否则 - 它位于面外。

要了解交叉点的计算方式，请考虑下图：

            v2
            o
           /
          / c (intersection)
o--------x----------------------> to infinity
t       /
       /   
      /
     o
     v1

要发生交集，tested.y 必须介于线段顶点（v1 和 v2）的 y 值之间。这是方法中 if 语句的第一个条件。如果发生这种情况，则水平线必须与线段相交。仅确定交叉点是发生在测试点的右侧还是左侧。这需要找到交点的 x 坐标，即：

              t.y - v1.y
c.x = v1.x + ----------- * (v2.x - v1.x)
             v2.y - v1.y

剩下要做的就是检查其中的微妙之处：

• 如果 v1.y == v2.y，则光线沿着线段移动，因此该线段对结果没有影响。实际上，在这种情况下，if 语句的第一部分返回 false。
• 代码首先相乘，然后才除以。这样做是为了支持 v1.x 和 v2.x 之间非常小的差异，由于四舍五入，这可能会导致除法后为零。
• 最后，应该解决在顶点上完全交叉的问题。请考虑以下两种情况：

         o                    o
         |                     \     o
         | A1                C1 \   /
         |                       \ / C2  
o--------x-----------x------------x--------> to infinity
        /           / \
    A2 /        B1 /   \ B2
      /           /     \ 
     o           /       o
                o

现在，要验证它是否有效，请自行检查方法主体中的 if 条件为 4 个段中的每个段返回的内容。您应该发现射线上方的片段（A1，C1，C2）收到阳性结果，而低于射线的片段（A2，B1，B2）收到负结果。这意味着 A 顶点对交叉计数贡献了一个奇数 （1），而 B 和 C 贡献了一个偶数（分别为 0 和 2），这正是我们想要的。A确实是多边形的真正交叉，而B和C只是“飞越”的两种情况。