我希望能够计算一个封闭的、分段线性路径(例如一个多边形)围绕一个点的卷绕数,但是除此之外,我还想检测路径何时穿过该点。因此,我将标准卷绕数加倍。对于一个方向为逆时针的非相交多边形,其值将为:
- 如果点在多边形外部,则值为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
我希望能够得到一个正确算法的链接,或者确认我的算法是否正确,或者一个测试用例来检验我的算法是否失败。谢谢!