python - 具有边缘情况的整数绕组数算法

Question

我想要winding number关于一个点的封闭的分段线性路径(例如多边形)，但此外，我想检测路径何时通过该点。出于这个原因，我将标准绕组数加倍。对于逆时针方向的非相交多边形，该值将为:

• 0 如果点在多边形之外
• 1 如果点在多边形的边或顶点上
• 2 如果点在多边形的内部

其他情况也类似。 (编辑:image of a few examples)

当点位于边或顶点上时，我发现的每个算法都会失败。

我的另一个要求是，当所有输入(即点的坐标和路径的顶点)都是整数时，它必须给出完全正确的结果。所以这几乎排除了三角函数或平方根，并且必须小心使用除法。

我不需要处理具有两个连续重合点或 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

Link to a version with comments and unit tests.

我想要一个指向正确算法的链接，或者我的算法正确性的一些确认，或者我的算法失败的测试用例。谢谢!

Answer 1

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

没有为轮廓上的点定义缠绕数。 (积分没有明确定义，特别是)。

如果您沿着相同的路径走两次，您将获得两倍的绕组数。因此，如果你假设如果点在计数器上，数字将为 1，那么这实际上意味着如果你去一次，绕线数是 1/2，但这显然是错误的，因为绕线数总是一个整数。