如何修改Pnpoly算法以实现C++中十字形区域的点-in-多边形判断

首先得说明：你的Pnpoly代码是针对**简单闭合多边形（不自交、边连续无交叉）**设计的，直接用来判断十字形可能会出问题——如果十字形的顶点列表是随便列的，很容易出现自交边，导致Pnpoly的奇偶规则判断错误。下面给你两种实用的解决方案：

方案1：拆分十字形为两个矩形（推荐，简单高效） #

十字形本质是一个水平矩形条加一个垂直矩形条的组合，只要点落在其中任意一个矩形内，就判定为在十字形里。这种方法比用Pnpoly简单得多，而且计算更快。

首先写一个通用的点在矩形内的判断函数：

// 判断点(x,y)是否在矩形内，矩形由左、上、右、下边界定义（注意坐标系方向，根据你的需求调整）
bool PointInRect(int x, int y, int rectLeft, int rectTop, int rectRight, int rectBottom) {
    return x >= rectLeft && x <= rectRight && y >= rectTop && y <= rectBottom;
}

然后针对十字形写判断函数，你只需要传入十字形的中心坐标、整体尺寸、条的厚度：

// cx,cy：十字形中心坐标；crossWidth：十字水平方向总宽度；crossHeight：十字垂直方向总高度；barThickness：十字条的厚度
bool PointInCross(int x, int y, int cx, int cy, int crossWidth, int crossHeight, int barThickness) {
    // 判断是否在水平条内
    bool inHorizontalBar = PointInRect(
        x, y,
        cx - crossWidth / 2, cy - barThickness / 2,
        cx + crossWidth / 2, cy + barThickness / 2
    );
    // 判断是否在垂直条内
    bool inVerticalBar = PointInRect(
        x, y,
        cx - barThickness / 2, cy - crossHeight / 2,
        cx + barThickness / 2, cy + crossHeight / 2
    );
    // 只要在其中一个条里，就属于十字形区域
    return inHorizontalBar || inVerticalBar;
}

方案2：调整十字形为简单多边形，适配Pnpoly #

如果你一定要用现有的Pnpoly代码，需要先把十字形转换成无自交的简单闭合多边形，也就是按顺时针或逆时针顺序排列顶点，确保边不会交叉。

比如一个中心在(0,0)，水平宽10、垂直高10、条厚2的十字形，顶点可以按这个顺序排列（闭合）：
(-5,-1), (-1,-1), (-1,-5), (1,-5), (1,-1), (5,-1), (5,1), (1,1), (1,5), (-1,5), (-1,1), (-5,1), (-5,-1)

另外注意：你的原Pnpoly代码有个bug——没有返回结果c，必须补上，否则函数行为是未定义的。修正后的代码：

bool PointInPolygon(vector<pair<int,int>> points,int x, int y) {
    int i, j, nvert = points.size();
    bool c = false;
    for(i = 0, j = nvert - 1; i < nvert; j = i++) {
        if( ( (points[i].second >= y) != (points[j].second >= y) ) && 
            (x <= (points[j].first - points[i].first) * (y - points[i].second) / (points[j].second - points[i].second) + points[i].first) )
            c = !c;
    }
    return c; // 补上return语句！
}

之后把整理好的十字形顶点列表传入这个函数，就能正确判断点是否在十字形内了。

两种方案对比 #

• 方案1：代码简洁、计算高效，不需要考虑多边形顶点顺序，适合大多数场景。
• 方案2：适合必须用多边形判断的场景，但需要仔细整理顶点顺序，避免自交。

内容的提问来源于stack exchange，提问作者Tim