绕组数算法未产生预期结果

Question

因此，我实现了绕组数和交叉数算法的一个非常未优化的版本，可以在http://geomalgorithms.com/a03-_inclusion.html，但我遇到过一个案例，绕组数算法无法产生预期结果。

我已经创建了一个多边形和三个点，如图所示。对于P0和P2，两种算法的行为都是可预测的。然而，对于点P1(由多边形边界内的"空空间"包含的点(，交叉数算法成功，而缠绕数算法未能将该点识别为不包含在多边形中。

这是实现的算法：

int wn_PnPoly(Vector2 P, Vector2[] V)
{
int n = V.Length - 1;
int wn = 0;    // the  winding 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)
{          // start y <= P.y
if (V[i + 1].y > P.y)      // an upward crossing
if (isLeft(V[i], V[i + 1], P) > 0)  // P left of  edge
++wn;            // have  a valid up intersect
}
else
{                        // start y > P.y (no test needed)
if (V[i + 1].y <= P.y)     // a downward crossing
if (isLeft(V[i], V[i + 1], P) < 0)  // P right of  edge
--wn;            // have  a valid down intersect
}
}
return wn;
}
float isLeft(Vector2 P0, Vector2 P1, Vector2 P2)
{
return ((P1.x - P0.x) * (P2.y - P0.y)
- (P2.x - P0.x) * (P1.y - P0.y));
}

我是不是遗漏了一些显而易见的东西？为什么交叉数算法在这种情况下成功，而绕组数却失败了？

Answer 1

这两种方法不是同一个标准。

在非零或缠绕规则中，线段的方向很重要。该算法检查线段是从左边还是从右边穿过出射光线，并计算每种情况发生的频率。只有当

交叉数或奇偶规则只计算一条线的交叉频率。每次你过一条线，你要么从内到外，要么从内向外，所以偶数个交叉点意味着该点在外。

如果在示例中从P1向右移动，则会穿过两条线，因此偶数规则告诉P1不在多边形中。但这两条线的方向是相同的：如果你的整体形状是按顺时针方向绘制的，那么两条线都是从上到下绘制的。用你链接的文章的话来说，多边形绕P1两次。根据缠绕规则，P1是多边形的一部分。你的程序显示了正确的行为。

矢量图形程序和格式区别于这两种规则。例如，SVG有一个fill-rule属性，您可以在其中设置行为。Postscript有fill和eofill运算符，分别用缠绕规则和奇偶规则填充路径。默认规则通常是缠绕规则，因此设计者必须注意正确确定路径的方向。