정수부 와인딩 수 알고리즘의 경우

Question

winding number 점에 대해 닫혀진 조각 별 선형 경로 (예 : 다각형)를 원하지만 그 지점을 통과 할 때를 감지하고 싶습니다. 이런 이유로 표준 권선 수를 두 배로 늘립니다. CCW 방향으로 비 - 교차 다각형, 값이됩니다

• 0 점이 다각형의 모서리 또는 정점에있는 경우 점이 다각형 외부
• 1이면
• 2하다면 그 점은 다각형의 내부에 있습니다.

그리고 다른 경우에도 마찬가지입니다. (편집 : image of a few examples)

내가 찾은 모든 알고리즘은 포인트가 가장자리 또는 정점에있을 때 실패합니다.

필자의 다른 요구 사항은 모든 입력 (즉, 점의 좌표와 경로의 정점)이 정수인 경우 정확히 정확한 결과를 제공해야한다는 것입니다. 그래서 이것은 trig 함수 나 제곱근을 거의 배제하고 div는주의 깊게 사용해야합니다.

나는 이 아니며은 두 개의 연속 된 일치 점 또는 180도 회전이있는 퇴화 된 경로를 처리해야합니다.

어쨌든 해결책이 있다고 생각합니다. 그러나, 그것은 약간 우아하고, 나는 그것이 옳다고 확신하지 않습니다. (. 난 정말 포인트가 정점에있을 때 일어나는 일에 대해 자신을 혼동) 여기 파이썬에 : 나는 올바른 알고리즘에 대한 링크, 또는 확인을 부탁

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

문제는 가정이 잘못되었다는 것입니다.

권선 번호는 형상의 점에 대해 정의되지 않습니다. (적분은 특히 잘 정의되어 있지 않습니다.)

동일한 경로를 두 번 따라 가면 감기 횟수가 두 배가됩니다. 그러므로 만약 그 지점이 countour에 있다면 숫자가 1이된다고 가정하면, 그것은 실제로 한 번 감기 횟수가 1/2이라면 실제로 나타납니다. 그러나 감기 횟수는 항상이기 때문에 이것은 분명히 틀립니다. 정수.