带有边界情况的整数绕序算法

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

链接到带有评论和单元测试的版本。

我希望能够得到一个正确算法的链接，或者确认我的算法是否正确，或者一个测试用例来检验我的算法是否失败。谢谢！

- Cosmologicon

Answer 1

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

对于轮廓上的点，旋绕数未被定义（积分未被很好地定义，特别是）。如果你走相同的路径两次，你会得到两倍的旋转数。因此，如果你的假设是，如果点位于轮廓上，则该数字将为1，那么这实际上意味着，如果你只走一次，则旋转数为1/2，但这显然是错误的，因为旋转数始终是一个整数。

- Petar Ivanov

---

哦，是的，你说得完全正确，我想要的数字更恰当地说是对绕数的扩展，因为它通常被定义为这样。我认为这是一个相当直观和一致的扩展，但是是的，它不是正常的定义。也许我应该用另一个名称来称呼它。 - Cosmologicon

除此之外，我在这里看不到定义...如果点在轮廓上，则始终为1。这根本不一致。如果曲线通过该点然后绕了10圈，那怎么办。它仍然是1吗...我的意思是，是的，如果不在曲线上，您可以将其定义为绕数，如果在曲线上，则可以定义为其他任何内容-但这对任何方面都没有帮助。 - Petar Ivanov

哦，好的，抱歉，我认为定义是显而易见的，尽管有点难以陈述。如果两个边穿过该点，则该点处的“修改”绕数将为2（假设它没有在其他任何东西内部）。以下是几个不同值的插图：http://imgur.com/cDc6o - Cosmologicon

我仍然不清楚何时将其视为+1，何时视为-1... 关于绕数的问题在于它允许您仅使用本地信息（角度差分）计算它，然后进行积分。我不明白如何仅使用本地信息确定符号+1/-1。 - Petar Ivanov

嗯，我对等高线积分定义并不是很熟悉，但我认为的方式是，如果你沿着路径将一辆火车从你的位置发出，并转向它直到它返回到你，那么如果你向左旋转了180度，就是+1，如果你向右旋转了180度，就是-1。无论如何，如果你认为这个定义不好，那没关系，不必费心。我当然不建议人们采用它，我只是想为自己保留这个定义！ - Cosmologicon

这个定义是正确的。问题在于你不能用它来计算数量......它可以是一个更复杂的曲线，以至于无法确定你是否沿逆时针或顺时针旋转。实际上，CCW与CW的定义是通过绕数的符号。(当点不在曲线上时) - Petar Ivanov