多边形内的检查点 [英] Check point within polygon

问题描述

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;
}

此功能检查点是否在多边形内.如何处理负数的多边形坐标?例如，

This function checks if a point is within a polygon. How do I deal with a polygon coordinate that is negative? For example,

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

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

I tried checking a valid point within the polygon and it returns 0.

推荐答案

iSurfer中有不错的实现

在大多数情况下(以及我所知道的两种)使用的两种方法是穿越编号和缠绕编号. 它们两者均不受多边形/点坐标的符号的影响.因此，这肯定是您代码中的错误.

The two methods used in most cases (and the two I know of) are crossing number and winding number. Both of them are not affected by the signs of the polygon/point coordinates. So it must be a bug in your code.

为完整起见，我正在放置代码进行穿越次数测试，这似乎就是您要在代码中尝试做的事情

For completeness I'm placing the code for a crossing number test which seems to be what you're trying to do in your code

// 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)

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

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

A special case that can arise with the crossing number number test, is when the ray overlaps an edge of the polygon. In that case it becomes somewhat fuzzy how to count intersections. That's why it's not the actual number of intersections we count, but the number we crossed over semiplanes defined by the ray.

绕组数测试在这方面更可靠

The winding number test is more robust to this respect

这篇关于多边形内的检查点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！