点是否在多边形内的判定方法

有两种算法
1.光线投射算法
2.绕线数算法

我们这次只讲光线投射算法
测试从点开始并沿任何固定方向前进的光线与多边形边缘相交的次数。如果该点位于多边形的外侧，则该光线将与其边缘相交偶数次。如果该点位于多边形的内侧，则它将与该边相交奇数次。当点在多边形的边缘这种方法是行不通的。

该算法有时也被称为交叉数算法或奇偶规则算法，并且早在1962年就已知。

以下是检查点是在内部还是外部的简单想法。
1）在每个点的右侧绘制一条水平线并将其延伸到无穷大
2）计算线与多边形边相交的次数。
3）如果交叉点的数量为奇数，则点在多边形内部。否则，那么点在外面。

代码实现如下（Unity版本）

public static bool IsPointInsidePolygon(Vector3 point, Vector3[] v)
    {
        int nCross = 0;
        int arrayLen = v.Length;
        for (int i=0; i< arrayLen; i++)
        {
            Vector3 v1 = v[i];
            Vector3 v2 = v[(i + 1) % arrayLen];

            if (v1.z == v2.z) continue;

            if (point.z < Mathf.Min(v1.z, v2.z)) continue;
            if (point.z > Mathf.Max(v1.z, v2.z)) continue;

            float x = (point.z - v1.z) * (v2.x - v1.x) / (v2.z - v1.z) + v1.x;
            if (x > point.x)
            {
                ++nCross;
            }
        }
        
        return nCross%2 == 1;
    }