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

Question

我想要一个闭合的分段线性路径（例如多边形）的缠绕数一个点，但除此之外，我想检测路径何时经过该点。因此，我将标准缠绕数加倍。对于 CCW 方向的非相交多边形，该值将为：

• 如果点在多边形外部，则为 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

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

没有为轮廓上的点定义绕数。 （特别是积分没有明确定义）。

如果你沿着同一条路径走两次，你会得到两倍的缠绕数。因此，如果您假设如果该点位于计数上，则该数字将为 1，那么这实际上意味着如果您走一次，则绕数为 1/2，但这显然是错误的，因为绕数总是一个整数。