c++ - 帮助解决这个算法

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

 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。

谢谢

最佳答案

当心 :这个答案是 错误 。我现在没有时间修复它，但请参阅评论。

这将一条射线从该点转换到无穷远处，并检查与每个多边形边的交点。每次找到交叉点时，标志 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;
 }

关于c++ - 帮助解决这个算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3442824/