c++ - 帮助这个算法

Question

我有一个算法可以判断一个点是否在多边形内。

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y)
 {
     int i, j, c = 0;
     for (i = 0, j = npts-1; i < npts; 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;
 }

我唯一的问题是它采用奇数缠绕规则。我的意思是，如果多边形是自相交的，它会被认为是“空”的某些部分将返回为假。即使它自相交，我也需要什么，多边形内的任何东西都会返回 true。

谢谢

Answer 1

注意:此答案错误。我现在没有时间修复它，但请参阅评论。

这会从该点向无穷远处转换一条射线，并检查与多边形每条边的交点。每次找到交叉点时，标志 c 都会切换:

c = !c;

所以偶数个交叉点意味着偶数个切换，所以 c 最后将为 0。奇数个交叉点意味着奇数个切换，因此 c 将为 1。

您想要的是在发生任何交集时设置c标志:

c = 1;

为了更好的衡量，您可以完全消除 c，并提前终止:

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y)
 {
     int i, j;
     for (i = 0, j = npts-1; i < npts; 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]))
             return 1;
     }
     return 0;
 }