具有边缘情况的整数缠绕数算法

Question

我想计算一个闭合的、由直线段组成的路径（比如多边形）围绕某个点的绕数，另外，我还想知道路径是否经过这个点。为此，我把标准的绕数翻倍。对于一个不相交、逆时针方向的多边形，结果会是：

• 如果点在多边形外面，结果是0
• 如果点在多边形的边上或顶点上，结果是1
• 如果点在多边形内部，结果是2

其他情况下也是类似的。（编辑：这里有一些例子的图片）

我找到的每个算法在点位于边上或顶点时都不管用。

我还有一个要求，就是当所有输入（也就是点的坐标和路径的顶点坐标）都是整数时，结果必须完全正确。所以这基本上排除了三角函数或平方根的使用，除法也必须小心处理。

我不需要处理那些有两个连续重合点或180度转弯的特殊路径。

总之，我觉得我有一个解决方案。不过，这个方案看起来有点不优雅，我对它的正确性没有信心。（我真的搞糊涂了，当点在顶点时会发生什么。）以下是我的Python代码：

def orient((x,y), (a0,b0), (a1,b1)):
    return cmp((a1-a0)*y + (b0-b1)*x + a0*b1-a1*b0, 0)
def windingnumber(p0, ps):
    w, h = 0, [cmp(p, p0) for p in ps]
    for j in range(len(ps)):
        i, k = (j-1)%len(ps), (j+1)%len(ps)
        if h[j] * h[k] == -1:
            w += orient(p0, ps[j], ps[k])
        elif h[j] == 0 and h[i] == h[k]:
            w += orient(ps[k], ps[i], ps[j])
    return w

这里有一个带注释和单元测试的版本链接。

我希望能找到一个正确的算法链接，或者确认我的算法是正确的，或者提供一个我的算法失败的测试案例。谢谢！

Answer 1

问题在于你的假设是错误的。

绕数（winding number）并不适用于轮廓上的点。（特别是，积分在这里并没有明确的定义。）

如果你沿着同一条路径走两次，得到的绕数就会是两倍。所以，如果你认为如果点在轮廓上，绕数就是1，那这实际上会意味着如果你只走一次，绕数是1/2，但这显然是错误的，因为绕数总是一个整数。