Source Code for Module MeatEngine.Math.Voronoi.subdivision

  1  """Voronoi/Delaunay Subdivision code 
  2   
  3  transcribed from Graphics Gems IV""" 
  4   
  5   
  6  import quadedge 
  7  import predicates 
  8   
  9  EPSILON=0.01 
 10   
 11 -class Subdivision: 
 12 -    def __init__(self, a, b, c): 
 13          ea = quadedge.makeEdge() 
 14          ea.endPoints(a,b) 
 15   
 16          eb = quadedge.makeEdge() 
 17          quadedge.splice(ea.sym, eb) 
 18          eb.endPoints(b,c) 
 19   
 20          ec = quadedge.makeEdge() 
 21          quadedge.splice(eb.sym, ec) 
 22          ec.endPoints(c,a) 
 23   
 24          quadedge.splice(ec.sym, ea) 
 25          self.startingEdge = ea 
 26   
 27   
 28 -    def debugPrint(self): 
 29          e=self.dumpEdges() 
 30   
 31          print "subdivision edges" 
 32          print "="*40 
 33          for edge in e: 
 34              print edge 
 35          print "="*40 
 36   
 37          for edge in e: 
 38              print edge 
 39              print "oNext",edge.oNext() 
 40              print "oPrev",edge.oPrev() 
 41              print "dNext",edge.dNext() 
 42              print "dPrev",edge.dPrev() 
 43              print "lNext",edge.lNext() 
 44              print "lPrev",edge.lPrev() 
 45              print "rNext",edge.rNext() 
 46              print "rPrev",edge.rPrev() 
 47              print "-"*20 
 48       
 49           
 50   
 51 -    def insertSite(self, x): 
 52          e = self.locate(x) 
 53   
 54          if (x.samePoint(e.org(), EPSILON) or 
 55              x.samePoint(e.dest(), EPSILON)): 
 56              # already there 
 57              return 
 58          elif predicates.onEdge(x,e): 
 59              e = e.oNext() 
 60              quadedge.deleteEdge(e.oNext()) 
 61   
 62   
 63          base = quadedge.makeEdge() 
 64   
 65          base.endPoints(e.org(), x) 
 66          quadedge.splice(base, e) 
 67          self.startingEdge = base 
 68   
 69          while 1: 
 70              base = connect(e, base.sym) 
 71              e = base.oPrev() 
 72   
 73              if e.lNext() is self.startingEdge: 
 74                  break 
 75   
 76          while 1: 
 77              t = e.oPrev() 
 78              if (predicates.rightOf(t.dest(), e) and 
 79                  predicates.inCircle(e.org(), t.dest(), e.dest(), x)): 
 80                  swap(e) 
 81                  e = e.oPrev() 
 82              elif e.oNext() is self.startingEdge: 
 83                  return 
 84              else: 
 85                  e = e.oNext().lPrev() 
 86   
 87 -    def draw(self): 
 88          print 
 89          for d in self.dumpEdges(): 
 90              print d 
 91   
 92 -    def dumpEdges(self): 
 93          drawnEdges=[] 
 94          openEdges=[self.startingEdge] 
 95          self.startingEdge.tag=1 
 96   
 97          while openEdges: 
 98              e=openEdges.pop() 
 99              drawnEdges.append(e) 
100              neighbors=[e.sym, 
101                         e.oNext(), 
102                         e.oPrev(), 
103                         e.dNext(), 
104                         e.dPrev()] 
105              for n in neighbors: 
106                  if not n.tag: 
107                      n.tag=1 
108                      openEdges.append(n) 
109   
110          for d in drawnEdges: 
111              d.tag=0 
112          return drawnEdges 
113   
114 -    def locate(self, x): 
115          """returns an edge e, st either x is on e or e is an edge of a 
116          triangle containing x. The search starts from the startingEdge 
117          and proceeds in the general direction of x. Based on the 
118          pseudocode in Guibas and Stolfi (1985, p. 121).""" 
119   
120   
121          e=self.startingEdge 
122   
123          while 1: 
124              if (x.samePoint(e.org(), EPSILON) or 
125                  x.samePoint(e.dest(), EPSILON)): 
126                  return e 
127              elif predicates.rightOf(x,e): 
128                  e = e.sym 
129              elif not predicates.rightOf(x, e.oNext()): 
130                  e = e.oNext() 
131              elif not predicates.rightOf(x, e.dPrev()): 
132                  e = e.dPrev() 
133              else: 
134                  return e 
135               
136           
137   
138   
139 -def connect(a, b): 
140      e=quadedge.makeEdge() 
141      quadedge.splice(e, a.lNext()) 
142      quadedge.splice(e.sym, b) 
143      e.endPoints(a.dest(), b.org()) 
144      return e 
145   
146   
147 -def swap(e): 
148      a = e.oPrev() 
149      b = e.sym.oPrev() 
150      quadedge.splice(e, a) 
151      quadedge.splice(e.sym, b) 
152      quadedge.splice(e, a.lNext()) 
153      quadedge.splice(e.sym, b.lNext()) 
154      e.endPoints(a.dest(), b.dest()) 
155