Source Code for Module MeatEngine.Math.Voronoi.quadedge

  1  """ Quadedge data structure, after Guibas and Stolfi 
  2   
  3  Transcribed from Graphics Gems IV 
  4   
  5  sym: "symmetric" of edge, the edge that points in the opposite 
  6  direction (when viewed from the same orientation of the manifold). 
  7   
  8  vertices are also represented as "edges", because a quadEdge object 
  9  has four edge sub-structures to represent an edge - two substructures 
 10  for there and back, and the vertices at the ends form a circular 
 11  linked list. 
 12   
 13   
 14  """ 
 15   
 16   
 17   
 18 -class QuadEdge: 
 19 -    def __init__(self): 
 20          self.edges=(Edge(), Edge(), Edge(), Edge()) 
 21          e=self.edges 
 22          e[0].num=0 
 23          e[1].num=1 
 24          e[2].num=2 
 25          e[3].num=3 
 26          e[0].next=e[0] 
 27          e[1].next=e[3] 
 28          e[2].next=e[2] 
 29          e[3].next=e[1] 
 30           
 31          e[0].sym=e[2] 
 32          e[1].sym=e[3] 
 33          e[2].sym=e[0] 
 34          e[3].sym=e[1] 
 35           
 36          e[0].rot=e[1] 
 37          e[1].rot=e[2] 
 38          e[2].rot=e[3] 
 39          e[3].rot=e[0] 
 40   
 41          e[0].invRot=e[3] 
 42          e[1].invRot=e[0] 
 43          e[2].invRot=e[1] 
 44          e[3].invRot=e[2] 
 45           
 46 -class Edge: 
 47 -    def __init__(self): 
 48          self.num=0 
 49          self.next=None 
 50          self.data=None 
 51          self.sym=None 
 52          self.tag=0 
 53   
 54 -    def oNext(self): 
 55          """next edge ccw with same origin""" 
 56          return self.next 
 57   
 58 -    def oPrev(self): 
 59          """prev edge ccw with same origin""" 
 60          return self.rot.oNext().rot 
 61   
 62 -    def dNext(self): 
 63          """next edge ccw with the same destination""" 
 64          return self.sym.oNext().sym 
 65   
 66 -    def dPrev(self): 
 67          """prev edge with the same destination""" 
 68          return self.invRot.oNext().invRot 
 69   
 70 -    def lNext(self): 
 71          """next edge around left face of current edge""" 
 72          return self.invRot.oNext().rot 
 73   
 74 -    def lPrev(self): 
 75          """prev edge around left face of current edge""" 
 76          return self.oNext().sym 
 77   
 78 -    def rNext(self): 
 79          """next edge around right face of current edge""" 
 80          return self.rot.oNext().invRot 
 81   
 82 -    def rPrev(self): 
 83          """prev edge around right face of current edge""" 
 84          return self.sym.oNext() 
 85   
 86 -    def org(self): 
 87          """origin of edge""" 
 88          return self.data 
 89   
 90 -    def dest(self): 
 91          """destination of edge""" 
 92          return self.sym.data 
 93   
 94 -    def endPoints(self, org, dst): 
 95          """set endpoints""" 
 96          self.data=org 
 97          self.sym.data=dst 
 98   
 99 -    def __str__(self): 
100          return str(self.org())+" -> "+str(self.dest()) 
101   
102 -def makeEdge(): 
103      q1 = QuadEdge() 
104      return q1.edges[0] 
105   
106 -def splice(a, b): 
107      alpha = a.oNext().rot 
108      beta  = b.oNext().rot 
109      t1 = b.oNext() 
110      t2 = a.oNext() 
111      t3 = beta.oNext() 
112      t4 = alpha.oNext() 
113      a.next=t1 
114      b.next=t2 
115      alpha.next=t3 
116      beta.next=t4 
117   
118 -def deleteEdge(e): 
119      splice(e, e.oPrev()) 
120      splice(e.sym,e.sym.oPrev()) 
121