c++ 判断一个点是否落入一个给定的凹多边形

可以使用射线法来判断一个点是否在一个凹多边形内部。

具体做法如下：

1. 从该点向任意方向（一般选择向右的水平方向）发射一条射线，统计与该射线相交的边的数量。

2. 如果该点在多边形内部，那么与该射线相交的边的数量必须为奇数。

3. 如果该点在多边形外部，那么与该射线相交的边的数量必须为偶数。

4. 特殊情况：如果射线与多边形的一个顶点重合，那么将该顶点看做是与其相邻的两条边的交点。

代码实现如下（假设点P的坐标为(x,y)，多边形的边存储在vector<Edge> edges中）：

struct Point {
    double x, y;
};

struct Edge {
    Point a, b;
};

// 计算叉积 (P1-P0)x(P2-P0)
double cross(const Point &p0, const Point &p1, const Point &p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

// 判断点P是否在多边形内部
bool isInsidePolygon(const Point &p, const vector<Edge> &edges) {
    int cnt = 0;
    int n = edges.size();
    for (int i = 0; i < n; i++) {
        const Point &a = edges[i].a, &b = edges[i].b;
        // 如果点P在边上，返回true
        if ((a.x == p.x && a.y == p.y) || (b.x == p.x && b.y == p.y)) {
            return true;
        }
        // 如果点P在边的下方，不考虑
        if (a.y > p.y && b.y > p.y) {
            continue;
        }
        // 如果点P在边的上方，不考虑
        if (a.y <= p.y && b.y <= p.y) {
            continue;
        }
        // 计算交点的x坐标
        double x = a.x + (b.x - a.x) * (p.y - a.y) / (b.y - a.y);
        // 如果交点在P的左侧，增加计数器
        if (x < p.x) {
            cnt++;
        }
    }
    return (cnt % 2 == 1);
}

需要说明的是，如果多边形有重复的点，或者相邻的边重合，则需要特殊处理。