c++ - 多边形内的检查点

Question

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
   int i, j, c = 0;
   for (i = 0, j = npol-1; i < npol; j = i++) {
     if ((((yp[i] <= y) && (y < yp[j])) ||
        ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
       c = !c;
   }
   return c;
}

此函数检查点是否在多边形内。如何处理负的多边形坐标？例如，

float x[3] = { 0.16, 1.2, -10 };
float y[3] = { 1.8, 10, -5.5 };

我尝试检查多边形内的有效点，但它返回 0。

Answer 1

iSurfer 中有相当不错的实现

大多数情况下使用的两种方法(也是我所知道的两种)是交叉数和缠绕数。 两者都不受多边形/点坐标符号的影响。所以它一定是你的代码中的错误。

为了完整起见，我放置了一个交叉数测试的代码，这似乎是您在代码中尝试做的事情

// a Point is defined by its coordinates {int x, y;}

// isLeft(): tests if a point is Left|On|Right of an infinite line.
//    Input:  three points P0, P1, and P2
//    Return: >0 for P2 left of the line through P0 and P1
//            =0 for P2  on the line
//            <0 for P2  right of the line
//    See: Algorithm 1 "Area of Triangles and Polygons"
inline int isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x -  P0.x) * (P1.y - P0.y) );
}
//===================================================================

// cn_PnPoly(): crossing number test for a point in a polygon
//      Input:   P = a point,
//               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
//      Return:  0 = outside, 1 = inside
// This code is patterned after [Franklin, 2000]
int cn_PnPoly( Point P, Point* V, int n )
{
    int    cn = 0;    // the  crossing number counter

    // loop through all edges of the polygon
    for (int i=0; i<n; i++) {    // edge from V[i]  to V[i+1]
       if (((V[i].y <= P.y) && (V[i+1].y > P.y))     // an upward crossing
        || ((V[i].y > P.y) && (V[i+1].y <=  P.y))) { // a downward crossing
            // compute  the actual edge-ray intersect x-coordinate
            float vt = (float)(P.y  - V[i].y) / (V[i+1].y - V[i].y);
            if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
                 ++cn;   // a valid crossing of y=P.y right of P.x
        }
    }
    return (cn&1);    // 0 if even (out), and 1 if  odd (in)

}
//===================================================================

交叉数测试可能出现的一种特殊情况是，射线与多边形的一条边重叠。在那种情况下，如何计算交叉点就变得有些模糊了。这就是为什么它不是我们计算的实际交叉点数量，而是我们穿过射线定义的半平面的数量。

绕数测试在这方面更稳健