Source Code for Module MeatEngine.Math.Voronoi.predicates

 1  """ Voronoi/Delaunay predicates 
 2   
 3  transcribed from Graphics Gems IV""" 
 4   
 5  import quadedge 
 6   
 7  EPSILON=0.01 
 8   
 9 -def triArea(a, b, c): 
10      return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x) 
11   
12 -def inCircle(a, b, c, d): 
13      return ((a.x*a.x + a.y*a.y) * triArea(b, c, d) - 
14              (b.x*b.x + b.y*b.y) * triArea(a, c, d) + 
15              (c.x*c.x + c.y*c.y) * triArea(a, b, d) - 
16              (d.x*d.x + d.y*d.y) * triArea(a, b, c)) > 0 
17   
18   
19 -def ccw(a, b, c): 
20      ta=triArea(a, b, c) 
21      return ta>0 
22   
23 -def rightOf(x, e): 
24      return ccw(x, e.dest(), e.org()) 
25   
26 -def leftOf(x, e): 
27      return ccw(x, e.org(), e.dest()) 
28   
29 -def onEdge(x, e): 
30      t1 = x.sub(e.org()).mag() 
31      t2 = x.sub(e.dest()).mag() 
32      if (t1 < EPSILON) or (t2 < EPSILON): 
33          return True 
34   
35      t3 = e.org().sub(e.dest()).norm() 
36      if (t1 > t3) or (t2>t3): 
37          return False 
38   
39      #line = vect2d.Line(e.org(), e.dest()) 
40      #return abs(line.eval(x))<EPSILON 
41   
42      return False 
43