Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Compute 2x the winding number of a path around a point
- # Exactly correct results with integer inputs
- # orientation of the point (x,y) with respect to the given segment (a0,b0)-(a1,b1)
- # 0: collinear 1: within right half-plane -1: within left half-plane
- # calculated with a simple cross product
- def orient((x,y), (a0,b0), (a1,b1)):
- return cmp((a1-a0)*y + (b0-b1)*x + a0*b1-a1*b0, 0)
- # The double winding number of the given path ps about the given point p0
- def windingnumber(p0, ps):
- # Use the point (x,y) to divide the plane into two half-planes "above" and "below"
- # -1 or 1 depending on which half-plane each point is in. (0 if it's equivalent)
- h = [cmp(p, p0) for p in ps]
- w = 0
- for j in range(len(ps)):
- i, k = (j-1)%len(ps), (j+1)%len(ps) # Previous and next points in the path
- if h[j] * h[k] == 1: # Both points are in the same half-plane, so do nothing
- pass
- elif h[j] * h[k] == -1: # Crossing from one half-plane to the other
- w += orient(p0, ps[j], ps[k])
- elif h[j] == 0: # p[j] == p0
- if h[i] != h[k]: # Cross from one half-plane to the other, don't change w
- pass
- else: # Leave p0 through the same half-plane you entered through
- w += orient(ps[k], ps[i], ps[j])
- else: # this segment is leading either toward or away from p0
- pass
- return w
- # Test #1: normal W-shaped concave path
- path = (1,0), (3,4), (4,1), (6,5), (0,5), (0,1)
- test = "\n".join(" ".join(str(windingnumber((x,y), path)) for x in range(-1,8)) for y in range(6,-2,-1))
- print test
- assert test == """0 0 0 0 0 0 0 0 0
- 0 1 1 1 1 1 1 1 0
- 0 1 2 2 1 2 2 0 0
- 0 1 2 2 0 2 1 0 0
- 0 1 2 1 0 2 0 0 0
- 0 1 2 0 0 1 0 0 0
- 0 0 1 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0"""
- print
- # Test #2: complex path with a double wind and a figure 8
- path = (3,0), (5,3), (3,6), (1,2), (6,2), (6,8), (9,5), (1,4)
- test = "\n".join(" ".join(str(windingnumber((x,y), path)) for x in range(0,11)) for y in range(9,-2,-1))
- print test
- assert test == """0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 -1 0 0 0 0
- 0 0 0 0 0 0 -1 -1 0 0 0
- 0 0 0 1 0 0 -1 -2 -1 0 0
- 0 0 0 2 0 0 -1 -2 -2 -1 0
- 0 1 3 4 4 2 1 0 0 0 0
- 0 0 4 4 4 3 1 0 0 0 0
- 0 1 2 3 3 1 1 0 0 0 0
- 0 0 0 2 0 0 0 0 0 0 0
- 0 0 0 1 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0"""
Advertisement
Add Comment
Please, Sign In to add comment