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

Question

我想要关于一个点的闭合的分段线性路径(例如多边形)的绕组数,但另外,我想检测路径何时通过该点.因此,我将标准绕组数加倍.对于具有CCW方向的非交叉多边形,该值将为:

• 如果该点在多边形之外,则为0
• 如果该点位于多边形的边或顶点上,则为1
• 2如果该点位于多边形的内部

在其他情况下也是如此.(编辑:几个例子的图像)

当点位于边缘或顶点时,我发现的每个算法都会失败.

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

我并不需要处理有两个连续的重合点,或一个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，但这显然是错误的，因为绕数总是一个整数。