帮助解决这个算法问题。

Question

帮助解决这个算法问题。

3

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

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

我唯一的问题是它假设了奇怪的绕组规则。我的意思是，如果多边形自相交，某些部分被认为是“空的”，将返回false。即使它自相交，我需要的是任何在多边形内部的东西都会返回true。

谢谢

- jmasterx

也许你可以重新排列这些点，以便你绘制它们的顺序不会相交？ - Nick Larsen

不，我的应用程序是一个矢量绘图工具，可以使用不同种类的绕线规则。 - jmasterx

2

该算法基于Jordan曲线定理。有两个与有界对象相关联的空间 - 内部或外部。从所讨论的点投射出一条射线将与边界相交奇数次或偶数次。如果是奇数，则该点在边界内，如果是偶数，则该点在边界外。此外，该算法的特定版本假定基于投射的射线是水平的一个简单的优化。 - Matthieu N.

2个回答

1

将您的原始算法翻译成英语：您需要确定点右侧的多边形线段数量是偶数还是奇数。如果是偶数（包括零），则您的点在外面；如果是奇数，则您的点在内部。这意味着如果右侧有两个线段，左侧也有两个线段，则该点不被认为在多边形内。

您需要做的是更改算法，以便检查点两侧的线段；如果点两侧都有线段，则该点位于多边形内。

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y) 
 { 
     int i, j;
     bool hasSegmentLeft = false;
     bool hasSegmentRight = false;
     for (i = 0, j = npts-1; i < npts; j = i++) { 
         if ((((yp[i] <= y) && (y < yp[j])) || 
             ((yp[j] <= y) && (y < yp[i]))))
         {
             if (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])
             {
                 hasSegmentRight = true;
                 if (hasSegmentLeft)  // short circuit early return
                     return true;
             }
             else
             {
                 hasSegmentLeft = true;
                 if (hasSegmentRight)  // short circuit early return
                     return true;
             }
     } 
     return hasSegmentLeft && hasSegmentRight; 
 }

顺便说一句，那个for语句结构是处理循环列表并回到开头的一种非常聪明的方式；我以前从未见过。

- Mark Ransom

一个U形的多边形，其中点位于U形“碗”内（在多边形外部但在其凸包内），会出现两侧的交点，但该点不在多边形内。 - Thomas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas · Accepted Answer

注意：这个答案是错误的。我现在没有时间去修正它，但请查看评论。

这会从一个点向无穷远处发射一条射线，并检查是否与多边形的每条边相交。每当找到一个交点时，标志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;
 }