时间戳

首页 > 解决方案 > 绕组数算法未产生预期结果

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

问题描述

因此，我实现了一个非常未优化的绕组数和交叉数算法版本，可在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));
    }

我在这里遗漏了一些明显的东西吗？为什么在这种情况下交叉数算法成功而绕组数失败？

标签： algorithmpolygonpoint-in-polygon

解决方案

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

在非零或缠绕规则中，线段的方向很重要。该算法检查线段是从左侧还是从右侧穿过出射光线，并计算每种情况发生的频率。该点仅在以下情况下才被视为外部

交叉数或奇数规则只计算一条线被交叉的频率。每次你越过一条线时，你要么从内到外，反之亦然，所以偶数的交叉点意味着该点在外面。

如果您在示例中从 P1 向右走，则会穿过两条线，因此奇偶规则告诉您 P1 不在多边形中。但是这两条线具有相同的方向：如果您的整体形状以顺时针方式绘制，则两条线都是从上到下绘制的。在您链接的文章中，多边形围绕 P1 绕了两次。根据缠绕规则，P1 是多边形的一部分。您的程序显示正确的行为。

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

推荐阅读