判断点是否在有序的点组成的多边形内的算法（C++版本）

admin1

float  min1(float a, float b) {

        if (a > b) {
                return b;
        }
        else {
                return a;
        }
}

float  max1(float a, float b) {

        if (a < b) {
                return b;
        }
        else {
                return a;
        }
}

bool PtInPolygon(FVector2D p, TArray<FVector2D> ptPolygon)
{
        int nCross = 0;
        int nCount = ptPolygon.Num();
        for (int i = 0; i < nCount; i++)
        {
                FVector2D p1 = ptPolygon[i];
                FVector2D p2 = ptPolygon[(i + 1) % nCount];

                // 求解 y=p.y 与 p1p2 的交点

                if (p1.Y == p2.Y) // p1p2 与 y=p0.y平行
                        continue;

                if (p.Y < min1(p1.Y, p2.Y)) // 交点在p1p2延长线上
                        continue;

                if (p.Y >= max1(p1.Y, p2.Y)) // 交点在p1p2延长线上
                        continue;

                // 求交点的 X 坐标 --------------------------------------------------------------
                double x = (double)(p.Y - p1.Y) * (double)(p2.X - p1.X) / (double)(p2.Y - p1.Y) + p1.X;

                if (x > p.X)
                        nCross++; // 只统计单边交点
        }

        // 单边交点为偶数，点在多边形之外 ---
        return (nCross % 2 == 1);
}