Guest User

winding number

a guest
Dec 9th, 2011
659
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.32 KB | None | 0 0
  1. # Compute 2x the winding number of a path around a point
  2. # Exactly correct results with integer inputs
  3.  
  4. # orientation of the point (x,y) with respect to the given segment (a0,b0)-(a1,b1)
  5. # 0: collinear   1: within right half-plane   -1: within left half-plane
  6. # calculated with a simple cross product
  7. def orient((x,y), (a0,b0), (a1,b1)):
  8.     return cmp((a1-a0)*y + (b0-b1)*x + a0*b1-a1*b0, 0)
  9.  
  10. # The double winding number of the given path ps about the given point p0
  11. def windingnumber(p0, ps):
  12.     # Use the point (x,y) to divide the plane into two half-planes "above" and "below"
  13.     # -1 or 1 depending on which half-plane each point is in. (0 if it's equivalent)
  14.     h = [cmp(p, p0) for p in ps]
  15.     w = 0
  16.     for j in range(len(ps)):
  17.         i, k = (j-1)%len(ps), (j+1)%len(ps)  # Previous and next points in the path
  18.         if h[j] * h[k] == 1:  # Both points are in the same half-plane, so do nothing
  19.             pass
  20.         elif h[j] * h[k] == -1:  # Crossing from one half-plane to the other
  21.             w += orient(p0, ps[j], ps[k])
  22.         elif h[j] == 0:  # p[j] == p0
  23.             if h[i] != h[k]:  # Cross from one half-plane to the other, don't change w
  24.                 pass
  25.             else:  # Leave p0 through the same half-plane you entered through
  26.                 w += orient(ps[k], ps[i], ps[j])
  27.         else:  # this segment is leading either toward or away from p0
  28.             pass
  29.     return w
  30.  
  31. # Test #1: normal W-shaped concave path
  32. path = (1,0), (3,4), (4,1), (6,5), (0,5), (0,1)
  33.  
  34. test = "\n".join(" ".join(str(windingnumber((x,y), path)) for x in range(-1,8)) for y in range(6,-2,-1))
  35. print test
  36.  
  37. assert test == """0 0 0 0 0 0 0 0 0
  38. 0 1 1 1 1 1 1 1 0
  39. 0 1 2 2 1 2 2 0 0
  40. 0 1 2 2 0 2 1 0 0
  41. 0 1 2 1 0 2 0 0 0
  42. 0 1 2 0 0 1 0 0 0
  43. 0 0 1 0 0 0 0 0 0
  44. 0 0 0 0 0 0 0 0 0"""
  45.  
  46.  
  47. print
  48.  
  49. # Test #2: complex path with a double wind and a figure 8
  50. path = (3,0), (5,3), (3,6), (1,2), (6,2), (6,8), (9,5), (1,4)
  51.  
  52. test = "\n".join(" ".join(str(windingnumber((x,y), path)) for x in range(0,11)) for y in range(9,-2,-1))
  53. print test
  54.  
  55. assert test == """0 0 0 0 0 0 0 0 0 0 0
  56. 0 0 0 0 0 0 -1 0 0 0 0
  57. 0 0 0 0 0 0 -1 -1 0 0 0
  58. 0 0 0 1 0 0 -1 -2 -1 0 0
  59. 0 0 0 2 0 0 -1 -2 -2 -1 0
  60. 0 1 3 4 4 2 1 0 0 0 0
  61. 0 0 4 4 4 3 1 0 0 0 0
  62. 0 1 2 3 3 1 1 0 0 0 0
  63. 0 0 0 2 0 0 0 0 0 0 0
  64. 0 0 0 1 0 0 0 0 0 0 0
  65. 0 0 0 0 0 0 0 0 0 0 0"""
  66.  
  67.  
Advertisement
Add Comment
Please, Sign In to add comment