Voronoi diagrams

3214 days ago by JAVIER

Voronoi diagrams

Yuhua Lin

Javier Ruiz Ramirez

1644


File:Frans Hals - Portret van René Descartes.jpg

 

1854

File:John Snow.jpg

File:Snow-cholera-map-1.jpg

1908

File:Voronoy.jpg

File:AAMarkov.jpg

Def.

Consider $(X,d)$ a metric space and $S = \left\{x_i\right\}^n_{i=1}\subset X$, then we define the Voronoi cell of $x_i$ as:

$V(x_i) = \left\{z\in X:d(z,x_i)\leq d(z,x_k)\forall k \neq i\right\}$

Ex.

Let

$d(x,y) = \left\{\begin{array}{cc}1,&x\neq y\\ 0,& x=y\end{array}\right.$

then


$V(x_i) = X\setminus\bigcup_{k\neq i}\left\{ x_k\right\}$

 
       
#the following program initial a set of vertics and plot them on a 10*10 region global points global g L=[] L_all=[] g=Graphics() g += line([[-5,5],[-5,-5]],color='purple') g += line([[-5,-5],[5,-5]],color='purple') g += line([[5,5],[5,-5]],color='purple') g += line([[5,5],[-5,5]],color='purple') #show(g) L.append(g) points=[[-0.2,1],[2.33,-1],[1,1],[2,1],[0,0.5],[-0.3,-2],[0.5,3],[3,2.5],[-1.7,1.9],[0.8,-0.6]] for po in points: g+=point2d(po,rgbcolor=(0,0,1),size=25) L.append(g) #a = animate(L, xmin=-5, ymin=-5, xmax=5, ymax=5) #a.show(delay=20,iterations=1) #a.show(delay=20) show(g) 
       
#class point define the coordination of an vertex class point: def __init__(self, x=0.0, y=0.0): self.X = x + 0.0 self.Y = y + 0.0 def __repr__(self): return '[X Y:%s,%s]' % (self.X, self.Y) def PointOfIntersection(self, Line1, Line2): self.X = (Line1.C * Line2.B - Line2.C * Line1.B) / (Line2.A * Line1.B - Line1.A * Line2.B) self.Y = (Line1.C * Line2.A - Line1.A * Line2.C) / (Line1.A * Line2.B - Line1.B * Line2.A) return (self.X, self.Y) #class line define the function of a line generated from two vertices, the line function is: Ax+By+C=0 class Line: def __init__(self, a=0.0, b=0.0, c=0.0): self.A = a + 0.0 self.B = b + 0.0 self.C = c + 0.0 def __repr__(self): return '[Line:(%s)x + (%s)y + (%s)=0]' % (self.A, self.B, self.C) def Line(self, point1, point2): self.A = point2.Y - point1.Y self.B = -(point2.X - point1.X) self.C = (point2.X - point1.X) * point1.Y - point1.X * (point2.Y - point1.Y) if self.A < 0: self.A = -self.A self.B = -self.B self.C = -self.C return (self.A, self.B, self.C) #this function calculate the function of perpendicalar line def PerpendicularBisector(self, point1, point2): self.A = -(point2.X - point1.X) / (point2.Y - point1.Y) self.B = -1.0 self.C = (point2.Y + point1.Y) / 2 - self.A * (point2.X + point1.X) / 2 return (self.A, self.B, self.C) 
       
#define the line functions of the boarder. pt1 = point(-5, 5) pt2 = point(-5, -5) pt3 = point(5, -5) pt4 = point(5, 5) L1 = Line() L1.Line(pt1, pt2) print L1 L2 = Line() L2.Line(pt2, pt3) print L2 L3 = Line() L3.Line(pt3, pt4) print L3 L4 = Line() L4.Line(pt4, pt1) print L4 
       
[Line:(10.0000000000000)x + (0.000000000000000)y + (50.0000000000000)=0]
[Line:(0.000000000000000)x + (-10.0000000000000)y +
(-50.0000000000000)=0]
[Line:(10.0000000000000)x + (-0.000000000000000)y +
(-50.0000000000000)=0]
[Line:(0.000000000000000)x + (10.0000000000000)y +
(-50.0000000000000)=0]
[Line:(10.0000000000000)x + (0.000000000000000)y + (50.0000000000000)=0]
[Line:(0.000000000000000)x + (-10.0000000000000)y + (-50.0000000000000)=0]
[Line:(10.0000000000000)x + (-0.000000000000000)y + (-50.0000000000000)=0]
[Line:(0.000000000000000)x + (10.0000000000000)y + (-50.0000000000000)=0]
#generate the delaunay triangles for the set of vertices import numpy as np from scipy.spatial import Delaunay tri = Delaunay(points) #p stores the information of each delaunay triangles p = tri.points[tri.vertices] edge_points = [] edges = set() def add_edge(i, j): """Add a line between the i-th and j-th points, if not in the list already""" if (i, j) in edges or (j, i) in edges: # already added return edges.add( (i, j) ) # ia, ib, ic = indices of corner points of the triangle for ia, ib, ic in tri.vertices: add_edge(ia, ib) add_edge(ib, ic) add_edge(ic, ia) g2=g for ed in edges: i,j=ed g2 += line([points[i],points[j]],color='black') L.append(g2) show(g2) a = animate(L, xmin=-5, ymin=-5, xmax=5, ymax=5) a.show(delay=30) L_all.extend(L) 
       
# http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles # Find the centers of the delaunay triangles #print "a",a #print "b",b def dot2(u, v): return u[0]*v[0] + u[1]*v[1] def cross2(u, v, w): """u x (v x w)""" return dot2(u, w)*v - dot2(u, v)*w def ncross2(u, v): """|| u x v ||^2""" return sq2(u)*sq2(v) - dot2(u,v)**2 def sq2(u): return dot2(u, u) def circle_ceter(p): A = p[:,0,:].T B = p[:,1,:].T C = p[:,2,:].T matrix_a = A - C matrix_b = B - C cc = cross2(sq2( matrix_a) * matrix_b - sq2( matrix_b) * matrix_a, matrix_a, matrix_b) / (2*ncross2( matrix_a, matrix_b)) + C return cc cc=circle_ceter(p) g2 += point2d(cc.T,rgbcolor=(1,0,1),size=15) show(g2) L_all.append(g2) 
       
# the function connect_center connects the centers of two delaunay triangles which share a common edge def connect_center(cc,vc,g,L): for p1,p2 in zip(cc.T, vc[:,:,0].T): #i,j=ed g += line([p1,p2]) L.append(g) for p1,p2 in zip(cc.T, vc[:,:,1].T): #i,j=ed g += line([p1,p2]) L.append(g) for p1,p2 in zip(cc.T, vc[:,:,2].T): #i,j=ed g += line([p1,p2]) L.append(g) return g,L L=[] g += point2d(cc.T,rgbcolor=(1,0,1),size=15) L.append(g) vc = cc[:,tri.neighbors] #print "neighbor",tri.neighbors vc[:,tri.neighbors == -1] = np.nan g,L=connect_center(cc,vc,g,L) show(g) a = animate(L, xmin=-5, ymin=-5, xmax=5, ymax=5) a.show(delay=30) L_all.extend(L) 
       
#boarder_point extend the voronoi edge to the boarder of the display region # there are def boarder_point(point_1, point_2, point_3): x1, y1 = point_1 point1 = point(x1, y1) x2, y2 = point_2 point2 = point(x2, y2) x3, y3 = point_3 L_base = Line() L_base.Line(point1, point2) cross_p = 1 cross_p1 = point() cross_p2 = point() A = point2.Y - point1.Y B = -(point2.X - point1.X) C = (point2.X - point1.X) * point1.Y - point1.X * (point2.Y - point1.Y) if A < 0: A = -A B = -B C = -C test_value = 0 for test_point in points: test_x, test_y = test_point test_value = A * test_x + B * test_y + C if test_value != 0: break L_base.PerpendicularBisector(point1, point2) if point2.X == point1.X: if test_value < 0: cross_p1.PointOfIntersection(L_base, L3) else: cross_p1.PointOfIntersection(L_base, L1) else: rate = (point2.Y - point1.Y) / (point2.X - point1.X) if rate > 0: if test_value < 0: cross_p1.PointOfIntersection(L_base, L2) distance1 = (x3 - cross_p1.X) * (x3 - cross_p1.X) + (y3 - cross_p1.Y) * (y3 - cross_p1.Y) cross_p2.PointOfIntersection(L_base, L3) distance2 = (x3 - cross_p2.X) * (x3 - cross_p2.X) + (y3 - cross_p2.Y) * (y3 - cross_p2.Y) if distance1 > distance2: cross_p = 2 else: cross_p1.PointOfIntersection(L_base, L4) distance1 = (x3 - cross_p1.X) * (x3 - cross_p1.X) + (y3 - cross_p1.Y) * (y3 - cross_p1.Y) cross_p2.PointOfIntersection(L_base, L1) distance2 = (x3 - cross_p2.X) * (x3 - cross_p2.X) + (y3 - cross_p2.Y) * (y3 - cross_p2.Y) if distance1 > distance2: cross_p = 2 elif rate < 0: if test_value < 0: cross_p1.PointOfIntersection(L_base, L3) distance1 = (x3 - cross_p1.X) * (x3 - cross_p1.X) + (y3 - cross_p1.Y) * (y3 - cross_p1.Y) cross_p2.PointOfIntersection(L_base, L4) distance2 = (x3 - cross_p2.X) * (x3 - cross_p2.X) + (y3 - cross_p2.Y) * (y3 - cross_p2.Y) if distance1 > distance2: cross_p = 2 else: cross_p1.PointOfIntersection(L_base, L2) distance1 = (x3 - cross_p1.X) * (x3 - cross_p1.X) + (y3 - cross_p1.Y) * (y3 - cross_p1.Y) cross_p2.PointOfIntersection(L_base, L1) distance2 = (x3 - cross_p2.X) * (x3 - cross_p2.X) + (y3 - cross_p2.Y) * (y3 - cross_p2.Y) if distance1 > distance2: cross_p = 2 else: if test_value < 0: cross_p1.PointOfIntersection(L_base, L4) else: cross_p1.PointOfIntersection(L_base, L2) if cross_p == 1: return cross_p1 print "cross_p1", cross_p1 else: return cross_p2 print "cross_p2", cross_p2 #cross_p1 = boarder_point([ 3., 2.], [ 2.5, 2.5], [ 2.35714286 , 1.85714286]) #g1=g+line([[ 2.35714286 , 1.85714286],[cross_p1.X,cross_p1.Y]]) #show(g1) #print cross_p1 
       
L=[] L.append(g) def extend_boarder(g,L): centerNode=0 for nei in tri.neighbors: if nei[0]==-1: #print cc.T[nei[1]],cc.T[nei[2]],cc.T[centerNode] xc,yc=cc.T[centerNode] #print xc,yc cross_p = point() xa,ya=p[centerNode,1] xb,yb=p[centerNode,2] cross_p=boarder_point(p[centerNode,1],p[centerNode,2],cc.T[centerNode]) g += line([[cross_p.X,cross_p.Y],[xc,yc]]) L.append(g) centerNode+=1 return g,L g,L=extend_boarder(g,L) show(g) a = animate(L, xmin=-5, ymin=-5, xmax=5, ymax=5) a.show(delay=30) L_all.extend(L) 
       
a = animate(L_all, xmin=-5, ymin=-5, xmax=5, ymax=5) a.show(delay=30) 
       
import itertools import random import collections import numpy as npy 
       
def dist(p,q): return sqrt((p[0]-q[0])^2 + (p[1] - q[1])^2) 
       
class PQ(): def __init__(self): self._pq = [] self._counter = itertools.count(1) def is_empty(self): if len(self._pq) == 0: return True else: return False def _parent(self,n): return (n-1)//2 def _leftchild(self,n): return 2*n + 1 def _rightchild(self,n): return 2*n + 2 def push(self,pri,obj): if 1 < len(self._pq): item = self._pq[0][2] if obj.point == item.point: print 'Event discarded: I already have it' return None count = next(self._counter) self._pq.append((pri,count,obj)) n = len(self._pq) self._bubble_up(n-1) def _bubble_up(self,c): while 0 < c: p = self._parent(c) p_item = self._pq[p] c_item = self._pq[c] if p_item < c_item: self._pq[p] = c_item self._pq[c] = p_item c = p else: break def erase(self,po): print '>I want to erase:',po n = len(self._pq)-1 print 'max index:',n print 'An event is about to be erased' for k,item in enumerate(self._pq): pri,cont,obj = item if dist(po,obj.point) < 1e-3: print 'index:',k self.pop(k) break else: print '*** Object not found ***' def pop(self,p=0): n = len(self._pq) if n == 0: obj = None elif n == 1 or p == n-1: pri,cont,obj = self._pq.pop() else: pri,cont,obj = self._pq[p] self._pq[p] = self._pq.pop() self._sift_down(p) return obj def _sift_down(self,p): n = len(self._pq) while p < n: p_item = self._pq[p] lc = self._leftchild(p) if n <= lc: break c_item = self._pq[lc] c = lc rc = self._rightchild(p) if rc < n: rc_item = self._pq[rc] if c_item < rc_item: c_item = rc_item c = rc if c_item < p_item: break self._pq[c] = p_item self._pq[p] = c_item p = c 
       
class Event(object): def __init__(self,p): self.point = p self.x = p[0] self.y = p[1] self.site = True self.obj = None self.vertex = None self.time = False 
       
class BeachLine(object): def __init__(self): self.data = [] def is_below(self,po,ly): print 'just entered' print 'size:',len(self.data) for k,item in enumerate(self.data): if item.what() == 'Parabola': if item.left <= po[0] <= item.right: print 'Focus:',item.focus,'at',k, if dist(po,item.focus) > abs(po[1]-ly): print True return True else: print False return False def find_parabola(self,po): global MG global GO global SL global Delta Delta = (1,0) tcont = 0 lb = -10 ly = po[1] for k,item in enumerate(self.data): if item.what() == 'Parabola': print k,item.focus if len(self.data) == 1: self.data[0].left = 0 self.data[0].right = 1 GO += self.data[0].draw(ly) return 0 k = 0 lock = False while k < len(self.data)-1: #print lb # tcont += 1 print 'I going to graph a line' print 'I am the',tcont,' parabola' if self.data[k].event: print 'I have an event at:',self.data[k].event.point else: print 'I have no events' ipts = self.data[k].interp(self.data[k+2],ly) print 'basis_inter_parab:',ipts MG += self.data[k+1].draw(ipts,lb) print '->Left bound:',lb print tcont print 'My priority point is:',self.data[k+1].point print 'I am a:',self.data[k+1].what() # rb = self.data[k].inter(self.data[k+1],ly,lb) rb = rb[0] print '++The right bound:',rb if 1 < rb and False: rb = self.data[k].inter(self.data[k+1],ly) rb = rb[0] print '++The new right bound:',rb aux = abs(rb-lb) if aux < Delta[0]: Delta = (aux,k) if 1 < rb and not SL: SL = True print 'I am here' self.data.pop() self.data.pop() rb = 1 self.data[k].left = lb self.data[k].right = rb GO += self.data[k].draw(ly) print 'Belongs to:',k return k # self.data[k].left = lb self.data[k].right = rb GO += self.data[k].draw(ly) if lb < po[0] and po[0] <= rb: ans = k print 'Belongs to:',k lock = True lb = rb k += 2 else: self.data[k].left = rb self.data[k].right = 2 aux = abs(1-rb) if aux < Delta[0]: Delta = (aux,k) print '++The right bound:',rb print '1' GO += self.data[k].draw(ly) if not lock: ans = k print 'Belongs to:',k return ans 
       
def quadroots(a,b,c,param = -infinity): global gcont epsilon = 1e-6 vareps = 1e-10 delta = b^2-4*a*c if delta < 0: return None r1 = (-b - sqrt(delta))/(2*a) r2 = (-b + sqrt(delta))/(2*a) print 'roots are:',(RDF(r1),RDF(r2)) if param + epsilon < r1: return r1 else: return r2 
       
def quadfroots(a,b,c): d = b^2 - 4*a*c if d < 0: print 'No intersection' return None d = sqrt(d) x = (-b - d)/(2*a) y = (-b + d)/(2*a) return (x,y) 
       
z = quadroots(1,7,3) print RDF(z) 
       
roots are: (-6.54138126515, -0.458618734851)
-6.54138126515
roots are: (-6.54138126515, -0.458618734851)
-6.54138126515
class Parabola(object): def __init__(self,pt,rx,ry): self.focus = pt self.x = pt[0] self.y = pt[1] self.left = rx self.right = ry self.event = None def interp(self,cpar,w): c1 = self.y - w c2 = cpar.y - w c1s = self.y^2 - w^2 c2s = cpar.y^2 - w^2 a = c2 - c1 b = 2*(cpar.x*c1 - self.x*c2) c = c2*(self.x^2 + c1s) - c1*(cpar.x^2 + c2s) r1,r2 = quadfroots(a,b,c) return self.eval([r1,r2],w) def is_inside(x): if self.left <= x and x <= self.right: return True else: return False def inter(self,lin,c,param = -infinity): c1 = self.y^2 - c^2 c2 = 0.5/(self.y - c) b = -(2*c2*self.x + lin.slope) w = c2*(self.x^2 + c1) - lin.yint z = quadroots(c2,b,w,param) if z: return self.eval([z],c) else: return None def eval(self,xv,c): if self.y == c: return (self.x,self.y) c1 = self.y^2 - c^2 c2 = 0.5/(self.y - c) points = [] for x in xv: y = c2*((x-self.x)^2 + c1) points.append((x,y)) if 1 < len(points): return points else: return points[0] def draw(self,c): mesh = npy.linspace(self.left,self.right,500) pv = self.eval(mesh,c) #color = (random.random(),random.random(),random.random()) color = npy.random.rand(3) color = color.tolist() g = line(pv,thickness = 1.5,rgbcolor = color) g += point((self.x,self.y),rgbcolor = color) return g def what(self): return type(self).__name__ 
       
class Line(object): def __init__(self,p1,p2): self.mid = (0.5*(p1[0]+p2[0]),0.5*(p1[1]+p2[1])) self.a = p1 self.b = p2 self.point = [] self.sibling = None if p1[1] == p2[1]: self.slope = infinity self.yint = None else: self.slope = -(p2[0]-p1[0])/(p2[1]-p1[1]) #print self.slope self.yint = -self.slope*self.mid[0]+self.mid[1] #print self.yint #def poset(self): # global W # W += line([(1,2),(2,2)]) def insert(self,po): self.point.append(po) if self.sibling: self.sibling.point.append(po) def eval(self,x): return self.slope*x + self.yint def inter(self,nlin): if self.slope == nlin.slope: return None if self.slope == infinity: aux = nlin.eval(self.mid[0]) return (self.mid[0],aux) if nlin.slope == infinity: aux = self.eval(nlin.mid[0]) return (nlin.mid[0],aux) x = (nlin.yint - self.yint)/(self.slope - nlin.slope) y = self.eval(x) return (x,y) def draw(self,ips,param = -infinity): v = ips[0] w = ips[1] if w[0] < v[0]: v = ips[1] w = ips[0] if 0 < len(self.point): if param < v[0]: w = v v = self.point[0] print 'Bones:',(v,w) #y1 = self.eval(left) #y2 = self.eval(right) #color = (random.random(),random.random(),random.random()) color = npy.random.rand(3) color = color.tolist() g = line((v,w),rgbcolor = color) #g = line([(left,y1),(right,y2)],rgbcolor = color) #g += point([self.a,self.b]) return g def destroy(self): if self.sibling: self.sibling.sibling = None def what(self): return type(self).__name__ 
       
x_min = 0 x_max = 1 y_min = 0 y_max = 1 
       
points = [(2.9,5.04),(4.47,5.70),(6.10,4.77),(5.38,4.32),(4.56,2.97),(3.64,2.50)] cpo = [(y,x) for x,y in points] cpo = sorted(cpo) points = [(y,x) for x,y in cpo] tags = [] x_fac = 9.72 y_fac = 8.90 for i in range(len(points)): x,y = points[i] x = x/x_fac y = (y_fac-y)/y_fac points[i] = (x,y) tags.append(chr(65+i)) G = Graphics() G += point(points,rgbcolor = (0,0,0),size = 10) for k,c in enumerate(tags): G += text(c,(points[k][0]*1.03,points[k][1]*1.03)) G.axes_range(x_min,x_max,y_min,y_max) G.show() print points 
       
Traceback (click to the left of this block for traceback)
...
NameError: name 'x_min' is not defined
Traceback (most recent call last):    y_fac = 8.90
  File "", line 1, in <module>
    
  File "/tmp/tmpEc0pZa/___code___.py", line 20, in <module>
    G.axes_range(x_min,x_max,y_min,y_max)
NameError: name 'x_min' is not defined
def newsite(p): y = p[1] idx = BL.find_parabola(p) obj = BL.data[idx] nline1 = Line(obj.focus,p) nline2 = deepcopy(nline1) nline1.sibling = nline2 nline2.sibling = nline1 BL.data.insert(idx,nline2) BL.data.insert(idx,Parabola(p,p[0],p[0])) BL.data.insert(idx,nline1) BL.data.insert(idx,deepcopy(obj)) print 'this is the idx',idx circle_event(idx,y) #if aux: # print 'left ok' # GR += aux print 'this is the idx',idx circle_event(idx+4,y) #if aux: # print 'right ok' # GR += aux #return GR 
       
def terminate(event): global MG global Delta tol = 1e-3 #color = (random.random(),random.random(),random.random()) color = npy.random.rand(3) color = color.tolist() #MG += point(event.vertex,rgbcolor = color) vtx = event.vertex ly = event.y obj = event.obj if obj.event: #xtra EQ.erase(obj.event.point) try: idx = BL.data.index(obj) except: return None print '>>Could not find the object' idx = 0 MG += point(event.vertex,rgbcolor = color) print 'Expected index:',idx BL.find_parabola((0.5,ly)) print 'Delta:',Delta if Delta[0] < tol: print 'Real index:',Delta[1] BL.data[idx].event = None idx = Delta[1] # #c1 = BL.data[idx-2].what() == 'Parabola' #c2 = BL.data[idx+2].what() == 'Parabola' # if BL.data[idx-2].event: evt = BL.data[idx-2].event EQ.erase(evt.point) # if BL.data[idx+2].event: evt = BL.data[idx+2].event EQ.erase(event.point) # #if c1 and c2: L = Line(BL.data[idx-2].focus,BL.data[idx+2].focus) L.insert(event.vertex) pos = idx-1 BL.data[idx-1].insert(event.vertex) BL.data[idx+1].insert(event.vertex) # BL.data[pos].destroy() BL.data.pop(pos) #Attic.append(BL.data.pop(pos)) BL.data.pop(pos) #Attic.append(BL.data.pop(pos)) BL.data[pos].destroy() BL.data.pop(pos) # BL.data.insert(pos,L) circle_event(pos-1,ly,vtx) circle_event(pos+1,ly,vtx) 
       
def circle_event(idx,ly,xtra = None): global GO print '<<In circle event the index:',idx n = len(BL.data) #print 'len:',n if idx - 2 < 0 or idx + 2 >= n: return None pp = BL.data[idx] lp = BL.data[idx-2].focus rp = BL.data[idx+2].focus ll = BL.data[idx-1] rl = BL.data[idx+1] if lp == rp: return None ip = ll.inter(rl) if xtra: if dist(ip,xtra) < 1e-3: print 'I have seen this cirlce event before' return None r = dist(pp.focus,ip) #color = (random.random(),random.random(),random.random()) color = npy.random.rand(3) color = color.tolist() GO += circle(ip,r,rgbcolor = color) GO += point(ip,rgbcolor = color) yc = ip[1]-r+1e-5 #BL.is_below(ip,ly) if ly < yc: print 'Ignore this possible circle event' return None ep = (ip[0],yc) h = Event(ep) h.obj = pp h.site = False h.vertex = ip if pp.event: print 'I already have an event:',pp.event.point if pp.event.y < yc: EQ.erase(pp.event.point) print '//I replaced an event' pp.event = h else: pp.event = h EQ.push(yc,h) 
       
EQ = PQ() for p in points: EQ.push(p[1],Event(p)) print EQ._pq event = EQ.pop() pb = Parabola(event.point,x_min,x_max) 
       
Traceback (click to the left of this block for traceback)
...
NameError: name 'PQ' is not defined
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_6.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("RVEgPSBQUSgpCmZvciBwIGluIHBvaW50czoKICAgIEVRLnB1c2gocFsxXSxFdmVudChwKSkKcHJpbnQgRVEuX3BxCmV2ZW50ID0gRVEucG9wKCkKcGIgPSBQYXJhYm9sYShldmVudC5wb2ludCx4X21pbix4X21heCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmp9F_RSq/___code___.py", line 3, in <module>
    EQ = PQ()
NameError: name 'PQ' is not defined

The idea

G = Graphics() G+= plot(x^2+2,-5,5,rgbcolor = (0,0,0)) G+= line([(-5,0),(5,0)],thickness = 3) G+= point((0,5),size = 20) show(G,figsize = [3,3]) 
       

Equation defining a parabola $P$

$P = \left\{x\in X:d(x,f) = d(x,L)=x_y-L_y\right\}$

Consider


$\Pi(x)_P = \left\{\begin{array}{cc}d(x,f)<d(x,L),&above \,P\\ d(x,f)=d(x,L),& in \,P\\ d(x,f)>d(x,L),& below \,P\end{array}\right.$


G = Graphics() H = Parabola((0,2),-5,5) G += H.draw(1.8) W = Parabola((2,3),-5,5) G += W.draw(1.8) G += line([(-5,1.8),(5,1.8)]) G += point((1,2.5),size = 20) show(G,xmin = -5,ymin = 0,xmax = 5,ymax = 8) 
       
Traceback (click to the left of this block for traceback)
...
NameError: name 'Parabola' is not defined
Traceback (most recent call last):    G += point((1,2.5),size = 20)
  File "", line 1, in <module>
    
  File "/tmp/tmpo97JUa/___code___.py", line 4, in <module>
    H = Parabola((_sage_const_0 ,_sage_const_2 ),-_sage_const_5 ,_sage_const_5 )
NameError: name 'Parabola' is not defined

Def.

For a set of functions $\left\{f_i\right\}$ we define the lower envelope as

$LE(x) = \min_i\left\{f_i(x)\right\}$

G = Graphics() H = Parabola((0,2),-5,5) G += H.draw(0.5) W = Parabola((2,3),-5,5) G += W.draw(0.5) G += line([(-5,0.5),(5,0.5)]) G += point((1,2.5),size = 20) show(G,xmin = -5,ymin = 0,xmax = 5,ymax = 8) 
       
Traceback (click to the left of this block for traceback)
...
NameError: name 'Parabola' is not defined
Traceback (most recent call last):    G += point((1,2.5),size = 20)
  File "", line 1, in <module>
    
  File "/tmp/tmp9PWgY1/___code___.py", line 4, in <module>
    H = Parabola((_sage_const_0 ,_sage_const_2 ),-_sage_const_5 ,_sage_const_5 )
NameError: name 'Parabola' is not defined

Observation:

If a point lies above the LE, it must be closer to one of the sites above L than to L.

Thus, this point lies in the Voronoi cell of a site that has already been registered by the sweep line L.

Rules

  1. $\forall x_i \in S$ create a parabola $P_i$ when the sweep line L passes through $x_i$ (site event)
  2. At every time consider only the LE($P_i$)
  3. The edges of the Voronoi diagram result from the $P_i\bigcap P_k$
  4. For every new tuple ($P_{i-1},P_i,P_{i+1}$)  determine a possible vertex for the Voronoi diagram (possible circle event)
  5. If a parabola $P_i$ leaves the LE (contracts to a point), call this point a vertex (circle event)
  6. Continue until all site and circle events have been considered
Attic = [] html('<!--notruncate-->') BL = BeachLine() BL.data.append(pb) print BL.data maxiter = infinity global gcont gcont = 0 global MG global GO global Delta global SL SL = False MG = Graphics() while not EQ.is_empty() and gcont < maxiter: print 'Queue content:' for x in EQ._pq: print x[2].point gcont += 1 print '***********',gcont,'*************' event = EQ.pop() GO = copy(G) if event.site: print 'New parabola at:',event.point newsite(event.point) else: print 'Circle event in action' terminate(event) GO += line([(0,event.y),(1,event.y)]) #if gcont < 4: GO += MG GO.axes_range(x_min,x_max,y_min,y_max) show(GO,aspect_ratio = 1) # GO = copy(G) BL.find_parabola((0.5,0)) GO += MG GO.axes_range(x_min,x_max,y_min,y_max) show(GO,aspect_ratio = 1) # GO = copy(G) BL.find_parabola((0.5,-5)) GO += MG GO.axes_range(x_min,x_max,y_min,y_max) show(GO,aspect_ratio = 1) 
       

[<__main__.Parabola object at 0x509b710>]
Queue content:
(0.469135802469136, 0.666292134831461)
(0.627572016460905, 0.464044943820225)
(0.553497942386831, 0.514606741573034)
(0.459876543209876, 0.359550561797753)
(0.298353909465021, 0.433707865168539)
*********** 1 *************
New parabola at: (0.469135802469136, 0.666292134831461)
0 (0.374485596707819, 0.719101123595506)
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4

Queue content:
(0.553497942386831, 0.514606741573034)
(0.627572016460905, 0.464044943820225)
(0.298353909465021, 0.433707865168539)
(0.459876543209876, 0.359550561797753)
*********** 2 *************
New parabola at: (0.553497942386831, 0.514606741573034)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.10247697508665, 1.91266323979466),
(0.379529854437908, 0.616916145872957)]
Bones: ((0.379529854437908, 0.616916145872957), (1.10247697508665,
1.91266323979466))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.379529854438, 1.10247697509)
++The right bound: 0.379529854437909
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.379529854437908, 0.616916145872958),
(1.10247697508665, 1.91266323979466)]
Bones: ((0.379529854437908, 0.616916145872958), (1.10247697508665,
1.91266323979466))
->Left bound: 0.379529854437909
2
My priority point is: []
I am a: Line
roots are: (0.379529854438, 1.10247697509)
++The right bound: 1.10247697508665
I am here
Belongs to: 2
this is the idx 2
<<In circle event the index: 2
this is the idx 2
<<In circle event the index: 6

Queue content:
(0.627572016460905, 0.464044943820225)
(0.459876543209876, 0.359550561797753)
(0.298353909465021, 0.433707865168539)
(0.298825821533728, 0.214112020414623)
*********** 3 *************
New parabola at: (0.627572016460905, 0.464044943820225)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.29777321627896, 2.26269511591816),
(0.365478688107696, 0.591732066126924)]
Bones: ((0.365478688107696, 0.591732066126924), (1.29777321627896,
2.26269511591816))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.365478688108, 1.29777321628)
++The right bound: 0.365478688107696
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.697329846315391, 0.693903384508474),
(0.465907465070068, 0.565194305227238)]
Bones: ((0.465907465070068, 0.565194305227238), (0.697329846315391,
0.693903384508474))
->Left bound: 0.365478688107696
2
My priority point is: []
I am a: Line
roots are: (0.46590746507, 0.697329846315)
++The right bound: 0.465907465070068
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.465907465070068, 0.565194305227239),
(0.697329846315391, 0.693903384508474)]
Bones: ((0.465907465070068, 0.565194305227239), (0.697329846315391,
0.693903384508474))
->Left bound: 0.465907465070068
3
My priority point is: []
I am a: Line
roots are: (0.46590746507, 0.697329846315)
++The right bound: 0.697329846315391
Belongs to: 4
++The right bound: 0.697329846315391
1
this is the idx 4
<<In circle event the index: 4
this is the idx 4
<<In circle event the index: 8
Event discarded: I already have it

Queue content:
(0.750276515989413, 0.436488112450604)
(0.298353909465021, 0.433707865168539)
(0.298825821533728, 0.214112020414623)
(0.459876543209876, 0.359550561797753)
*********** 4 *************
Circle event in action
>I want to erase: (0.750276515989413, 0.436488112450604)
max index: 2
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.553497942386831, 0.514606741573034)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.40406116143913, 2.45319631874004),
(0.357971644468610, 0.578277098672927)]
Bones: ((0.357971644468610, 0.578277098672927), (1.40406116143913,
2.45319631874004))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.357971644469, 1.40406116144)
++The right bound: 0.357971644468609
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.750257805908300, 0.723340074731691),
(0.443631807768806, 0.552805359412224)]
Bones: ((0.443631807768806, 0.552805359412224), (0.750257805908300,
0.723340074731691))
->Left bound: 0.357971644468609
2
My priority point is: []
I am a: Line
roots are: (0.443631807769, 0.750257805908)
++The right bound: 0.443631807768806
I going to graph a line
I am the 3  parabola
I have an event at: (0.750276515989413, 0.436488112450604)
basis_inter_parab: [(0.750241666356253, 0.723299425198395),
(0.585645016504529, 0.482161946403276)]
Bones: ((0.585645016504529, 0.482161946403276), (0.750241666356253,
0.723299425198395))
->Left bound: 0.443631807768806
3
My priority point is: []
I am a: Line
roots are: (0.585645016505, 0.750241666356)
++The right bound: 0.585645016504529
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.585645016504529, 0.482161946403276),
(0.750241666356253, 0.723299425198395)]
Bones: ((0.585645016504529, 0.482161946403276), (0.750241666356253,
0.723299425198395))
->Left bound: 0.585645016504529
4
My priority point is: []
I am a: Line
roots are: (0.585645016505, 0.750241666356)
++The right bound: 0.750241666356253
I going to graph a line
I am the 5  parabola
I have an event at: (0.750276515989413, 0.436488112450604)
basis_inter_parab: [(0.443631807768806, 0.552805359412225),
(0.750257805908300, 0.723340074731691)]
Bones: ((0.443631807768806, 0.552805359412225), (0.750257805908300,
0.723340074731691))
->Left bound: 0.750241666356253
5
My priority point is: []
I am a: Line
roots are: (0.443631807769, 0.750257805908)
++The right bound: 0.750257805908300
++The right bound: 0.750257805908300
1
Delta: (0.0000161395520470453, 8)
Real index: 8
<<In circle event the index: 6
I have seen this cirlce event before
<<In circle event the index: 8

Queue content:
(0.298353909465021, 0.433707865168539)
(0.459876543209876, 0.359550561797753)
(0.298825821533728, 0.214112020414623)
*********** 5 *************
New parabola at: (0.298353909465021, 0.433707865168539)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.41478065445153, 2.47240899906259),
(0.357218294852386, 0.576926860808984)]
Bones: ((0.357218294852386, 0.576926860808984), (1.41478065445153,
2.47240899906259))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.357218294852, 1.41478065445)
++The right bound: 0.357218294852386
Belongs to: 0
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.755449379184910, 0.726227447218559),
(0.441532788167628, 0.551637957716645)]
Bones: ((0.750276515989413, 0.723350480628044), (0.441532788167628,
0.551637957716645))
->Left bound: 0.357218294852386
2
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.441532788168, 0.755449379185)
++The right bound: 0.441532788167628
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.759889808902626, 0.737434152550283),
(0.584143112908074, 0.479961626731104)]
Bones: ((0.750276515989413, 0.723350480628044), (0.584143112908074,
0.479961626731104))
->Left bound: 0.441532788167628
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.584143112908, 0.759889808903)
++The right bound: 0.584143112908075
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.544632115373570, 0.562252963776151),
(0.758042781745772, 0.729434410580986)]
Bones: ((0.750276515989413, 0.723350480628044), (0.758042781745772,
0.729434410580986))
->Left bound: 0.584143112908075
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.544632115374, 0.758042781746)
++The right bound: 0.758042781745772
++The right bound: 0.758042781745772
1
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4

Queue content:
(0.354270075660151, 0.422815085041361)
(0.298825821533728, 0.214112020414623)
(0.459876543209876, 0.359550561797753)
*********** 6 *************
Circle event in action
>I want to erase: (0.354270075660151, 0.422815085041361)
max index: 1
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.374485596707819, 0.719101123595506)
6 (0.469135802469136, 0.666292134831461)
8 (0.553497942386831, 0.514606741573034)
10 (0.627572016460905, 0.464044943820225)
12 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.354244767978654, 0.571649482065496),
(0.236651521033563, 0.603018731457138)]
Bones: ((0.236651521033563, 0.603018731457138), (0.354244767978654,
0.571649482065496))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.236651521034, 0.354244767979)
++The right bound: 0.236651521033563
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.236651521033563, 0.603018731457138),
(0.354244767978654, 0.571649482065496)]
Bones: ((0.236651521033563, 0.603018731457138), (0.354244767978654,
0.571649482065496))
->Left bound: 0.236651521033563
2
My priority point is: []
I am a: Line
roots are: (0.236651521034, 0.354244767979)
++The right bound: 0.354244767978654
I going to graph a line
I am the 3  parabola
I have an event at: (0.354270075660151, 0.422815085041361)
basis_inter_parab: [(1.45677270367492, 2.54767186987976),
(0.354272775565659, 0.571647570046415)]
Bones: ((0.354272775565659, 0.571647570046415), (1.45677270367492,
2.54767186987976))
->Left bound: 0.354244767978654
3
My priority point is: []
I am a: Line
roots are: (0.354272775566, 1.45677270367)
++The right bound: 0.354272775565659
I going to graph a line
I am the 4  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.775611242851029, 0.737440774534162),
(0.433487295385238, 0.547163334463643)]
Bones: ((0.750276515989413, 0.723350480628044), (0.433487295385238,
0.547163334463643))
->Left bound: 0.354272775565659
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.433487295385, 0.775611242851)
++The right bound: 0.433487295385238
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.797095165681021, 0.791940765772952),
(0.578854050164867, 0.472213040983854)]
Bones: ((0.750276515989413, 0.723350480628044), (0.578854050164867,
0.472213040983854))
->Left bound: 0.433487295385238
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.578854050165, 0.797095165681)
++The right bound: 0.578854050164867
Belongs to: 8
I going to graph a line
I am the 6  parabola
I have no events
basis_inter_parab: [(0.532595357310274, 0.552823619582305),
(0.787145891480661, 0.752233177272024)]
Bones: ((0.750276515989413, 0.723350480628044), (0.787145891480661,
0.752233177272024))
->Left bound: 0.578854050164867
6
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.53259535731, 0.787145891481)
++The right bound: 0.787145891480661
++The right bound: 0.787145891480661
1
Delta: (0.0000280075870057184, 4)
Real index: 4
>I want to erase: (0.354270075660151, 0.422815085041361)
max index: 1
An event is about to be erased
*** Object not found ***
<<In circle event the index: 2
I have seen this cirlce event before
<<In circle event the index: 4
I already have an event: (0.298825821533728, 0.214112020414623)
>I want to erase: (0.298825821533728, 0.214112020414623)
max index: 1
An event is about to be erased
index: 1
//I replaced an event

Queue content:
(0.407381418280826, 0.385428521165244)
(0.459876543209876, 0.359550561797753)
*********** 7 *************
Circle event in action
>I want to erase: (0.407381418280826, 0.385428521165244)
max index: 0
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.469135802469136, 0.666292134831461)
6 (0.553497942386831, 0.514606741573034)
8 (0.627572016460905, 0.464044943820225)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.416836465520835, 0.554952480995667),
(0.154113296346432, 0.625036680802163)]
Bones: ((0.354270075660151, 0.571642730972274), (0.154113296346432,
0.625036680802163))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.154113296346, 0.416836465521)
++The right bound: 0.154113296346432
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.118435512496779, 0.744811248306703),
(0.407371228094392, 0.532651636060468)]
Bones: ((0.354270075660151, 0.571642730972274), (0.407371228094392,
0.532651636060468))
->Left bound: 0.154113296346432
2
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.118435512497, 0.407371228094)
++The right bound: 0.407371228094393
I going to graph a line
I am the 3  parabola
I have an event at: (0.407381418280826, 0.385428521165244)
basis_inter_parab: [(0.843296578351523, 0.775085003956705),
(0.407388172835195, 0.532647910262286)]
Bones: ((0.750276515989413, 0.723350480628044), (0.407388172835195,
0.532647910262286))
->Left bound: 0.407371228094393
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.407388172835, 0.843296578352)
++The right bound: 0.407388172835195
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.921498457721223, 0.974194148350367),
(0.563994928823414, 0.450444122475387)]
Bones: ((0.750276515989413, 0.723350480628044), (0.563994928823414,
0.450444122475387))
->Left bound: 0.407388172835195
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.563994928823, 0.921498457721)
++The right bound: 0.563994928823414
Belongs to: 6
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.500396959580791, 0.527600069097605),
(0.877919991597670, 0.823343706318876)]
Bones: ((0.750276515989413, 0.723350480628044), (0.877919991597670,
0.823343706318876))
->Left bound: 0.563994928823414
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.500396959581, 0.877919991598)
++The right bound: 0.877919991597670
++The right bound: 0.877919991597670
1
Delta: (0.0000169447408021051, 4)
Real index: 4
<<In circle event the index: 2
Ignore this possible circle event
<<In circle event the index: 4

Queue content:
(0.459876543209876, 0.359550561797753)
(0.474852700355643, 0.109821589343034)
*********** 8 *************
New parabola at: (0.459876543209876, 0.359550561797753)
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.447570753242625, 0.546753782843642),
(0.109572566805332, 0.636918394160353)]
Bones: ((0.354270075660151, 0.571642730972274), (0.109572566805332,
0.636918394160353))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.109572566805, 0.447570753243)
++The right bound: 0.109572566805332
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(-0.290313910466906, 2.73308015271672),
(0.419257669040293, 0.495188076973279)]
Bones: ((0.407381418280826, 0.532644153614078), (0.419257669040293,
0.495188076973279))
->Left bound: 0.109572566805332
2
My priority point is: [(0.407381418280826, 0.532644153614078)]
I am a: Line
roots are: (-0.290313910467, 0.41925766904)
++The right bound: 0.419257669040293
I going to graph a line
I am the 3  parabola
I have an event at: (0.474852700355643, 0.109821589343034)
basis_inter_parab: [(1.00644082346713, 1.09863646195343),
(0.554876048960853, 0.437084775845463)]
Bones: ((0.750276515989413, 0.723350480628044), (0.554876048960853,
0.437084775845463))
->Left bound: 0.419257669040293
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.554876048961, 1.00644082347)
++The right bound: 0.554876048960853
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.482003807347006, 0.513191258825756),
(0.936857646699633, 0.869514231057530)]
Bones: ((0.750276515989413, 0.723350480628044), (0.936857646699633,
0.869514231057530))
->Left bound: 0.554876048960853
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.482003807347, 0.9368576467)
++The right bound: 0.936857646699633
++The right bound: 0.936857646699633
1
this is the idx 4
<<In circle event the index: 4
I already have an event: (0.474852700355643, 0.109821589343034)
>I want to erase: (0.474852700355643, 0.109821589343034)
max index: 0
An event is about to be erased
index: 0
//I replaced an event
this is the idx 4
<<In circle event the index: 8
I already have an event: (0.474852700355643, 0.109821589343034)
>I want to erase: (0.474852700355643, 0.109821589343034)
max index: 0
An event is about to be erased
*** Object not found ***
//I replaced an event

Queue content:
(0.421344003736544, 0.353931036043738)
(0.540809004826267, 0.317538809843862)
*********** 9 *************
Circle event in action
>I want to erase: (0.421344003736544, 0.353931036043738)
max index: 0
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.553497942386831, 0.514606741573034)
6 (0.459876543209876, 0.359550561797753)
8 (0.553497942386831, 0.514606741573034)
10 (0.627572016460905, 0.464044943820225)
12 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.453722496323883, 0.545112739944304),
(0.100422687191238, 0.639359221869209)]
Bones: ((0.354270075660151, 0.571642730972274), (0.100422687191238,
0.639359221869209))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.100422687191, 0.453722496324)
++The right bound: 0.100422687191238
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(-0.327843086771826, 2.85144206106752),
(0.421340408318863, 0.488619401082134)]
Bones: ((0.407381418280826, 0.532644153614078), (0.421340408318863,
0.488619401082134))
->Left bound: 0.100422687191238
2
My priority point is: [(0.407381418280826, 0.532644153614078)]
I am a: Line
roots are: (-0.327843086772, 0.421340408319)
++The right bound: 0.421340408318863
I going to graph a line
I am the 3  parabola
I have an event at: (0.421344003736544, 0.353931036043738)
basis_inter_parab: [(0.491584705002075, 0.446197415746649),
(0.421382352449800, 0.488584907048080)]
Bones: ((0.421382352449800, 0.488584907048080), (0.491584705002075,
0.446197415746649))
->Left bound: 0.421340408318863
3
My priority point is: []
I am a: Line
roots are: (0.42138235245, 0.491584705002)
++The right bound: 0.421382352449799
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.421382352449800, 0.488584907048072),
(0.491584705002075, 0.446197415746640)]
Bones: ((0.421382352449800, 0.488584907048072), (0.491584705002075,
0.446197415746640))
->Left bound: 0.421382352449799
4
My priority point is: []
I am a: Line
roots are: (0.42138235245, 0.491584705002)
++The right bound: 0.491584705002077
I going to graph a line
I am the 5  parabola
I have an event at: (0.540809004826267, 0.317538809843862)
basis_inter_parab: [(1.02482771828927, 1.12557364119903),
(0.552954595854181, 0.434269807508116)]
Bones: ((0.750276515989413, 0.723350480628044), (0.552954595854181,
0.434269807508116))
->Left bound: 0.491584705002077
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.552954595854, 1.02482771829)
++The right bound: 0.552954595854181
Belongs to: 8
I going to graph a line
I am the 6  parabola
I have no events
basis_inter_parab: [(0.478241977779005, 0.510244320322154),
(0.949423913851599, 0.879358381582498)]
Bones: ((0.750276515989413, 0.723350480628044), (0.949423913851599,
0.879358381582498))
->Left bound: 0.552954595854181
6
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.478241977779, 0.949423913852)
++The right bound: 0.949423913851600
++The right bound: 0.949423913851600
1
Delta: (0.0000419441309358892, 4)
Real index: 4
<<In circle event the index: 2
Ignore this possible circle event
<<In circle event the index: 4
I have seen this cirlce event before

Queue content:
(0.540809004826267, 0.317538809843862)
*********** 10 *************
Circle event in action
>I want to erase: (0.540809004826267, 0.317538809843862)
max index: -1
An event is about to be erased
*** Object not found ***
Expected index: 6
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.553497942386831, 0.514606741573034)
8 (0.627572016460905, 0.464044943820225)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.490901428434245, 0.535194864353800),
(0.0438277282385515, 0.654456529136569)]
Bones: ((0.354270075660151, 0.571642730972274), (0.0438277282385515,
0.654456529136569))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.0438277282386, 0.490901428434)
++The right bound: 0.0438277282385516
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.718816712385825, 1.13653582037833),
(0.383948660494745, 0.407156956262779)]
Bones: ((0.421344003736544, 0.488608061624679), (0.383948660494745,
0.407156956262779))
->Left bound: 0.0438277282385516
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.383948660495, 0.718816712386)
++The right bound: 0.383948660494745
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.328220823153012, 0.544834923879855),
(0.540799696457747, 0.416481887044475)]
Bones: ((0.421344003736544, 0.488608061624679), (0.540799696457747,
0.416481887044475))
->Left bound: 0.383948660494745
3
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.328220823153, 0.540799696458)
++The right bound: 0.540799696457747
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have an event at: (0.540809004826267, 0.317538809843862)
basis_inter_parab: [(1.14360074689799, 1.29957857200028),
(0.540812287633578, 0.416481076123200)]
Bones: ((0.750276515989413, 0.723350480628044), (0.540812287633578,
0.416481076123200))
->Left bound: 0.540799696457747
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.540812287634, 1.1436007469)
++The right bound: 0.540812287633578
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.455200224206078, 0.492193893111904),
(1.02948348318762, 0.942075371598470)]
Bones: ((0.750276515989413, 0.723350480628044), (1.02948348318762,
0.942075371598470))
->Left bound: 0.540812287633578
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.455200224206, 1.02948348319)
++The right bound: 1.02948348318762
++The right bound: 1.02948348318762
1
Delta: (0.0000125911758311892, 6)
Real index: 6
<<In circle event the index: 4
Ignore this possible circle event
<<In circle event the index: 6
Ignore this possible circle event

0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.760648697747172, 0.463236911124201),
(-0.395333251066896, 0.771607391458986)]
Bones: ((0.354270075660151, 0.571642730972274), (-0.395333251066896,
0.771607391458986))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-0.395333251067, 0.760648697747)
++The right bound: -0.395333251066896
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(2.18945362779742, 4.33974220818326),
(0.296579543420937, 0.216857562187410)]
Bones: ((0.421344003736544, 0.488608061624679), (0.296579543420937,
0.216857562187410))
->Left bound: -0.395333251066896
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.296579543421, 2.1894536278)
++The right bound: 0.296579543420937
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-0.889512430861534, 2.71189565117621),
(0.655232152973133, 0.232846835112496)]
Bones: ((0.540809004826267, 0.416476266742942), (0.655232152973133,
0.232846835112496))
->Left bound: 0.296579543420937
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-0.889512430862, 0.655232152973)
++The right bound: 0.655232152973133
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.284742676866488, 0.358661020236023),
(1.69744753803978, 1.46534442371345)]
Bones: ((0.750276515989413, 0.723350480628044), (1.69744753803978,
1.46534442371345))
->Left bound: 0.655232152973133
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.284742676866, 1.69744753804)
++The right bound: 1.69744753803978
++The right bound: 1.69744753803978
1

0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(4.61837150618560, -0.565851680317078),
(-6.92066242352464, 2.51230835423591)]
Bones: ((0.354270075660151, 0.571642730972274), (-6.92066242352464,
2.51230835423591))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-6.92066242352, 4.61837150619)
++The right bound: -6.92066242352464
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(25.0673364388865, 54.1702473396440),
(-0.800220838437692, -2.17209239038003)]
Bones: ((0.421344003736544, 0.488608061624679), (-0.800220838437692,
-2.17209239038003))
->Left bound: -6.92066242352464
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (-0.800220838438, 25.0673364389)
++The right bound: -0.800220838437696
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-18.3739254335841, 30.7713650337259),
(2.09136868328548, -2.07190477394553)]
Bones: ((0.540809004826267, 0.416476266742942), (2.09136868328548,
-2.07190477394553))
->Left bound: -0.800220838437696
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-18.3739254336, 2.09136868329)
++The right bound: 2.09136868328546
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(-2.16032125997597, -1.55675086352956),
(11.9763020555864, 9.51758379371196)]
Bones: ((0.750276515989413, 0.723350480628044), (11.9763020555864,
9.51758379371196))
->Left bound: 2.09136868328546
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-2.16032125998, 11.9763020556)
++The right bound: 11.9763020555864
++The right bound: 11.9763020555864
1

[<__main__.Parabola object at 0x509b710>]
Queue content:
(0.469135802469136, 0.666292134831461)
(0.627572016460905, 0.464044943820225)
(0.553497942386831, 0.514606741573034)
(0.459876543209876, 0.359550561797753)
(0.298353909465021, 0.433707865168539)
*********** 1 *************
New parabola at: (0.469135802469136, 0.666292134831461)
0 (0.374485596707819, 0.719101123595506)
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4

Queue content:
(0.553497942386831, 0.514606741573034)
(0.627572016460905, 0.464044943820225)
(0.298353909465021, 0.433707865168539)
(0.459876543209876, 0.359550561797753)
*********** 2 *************
New parabola at: (0.553497942386831, 0.514606741573034)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.10247697508665, 1.91266323979466), (0.379529854437908, 0.616916145872957)]
Bones: ((0.379529854437908, 0.616916145872957), (1.10247697508665, 1.91266323979466))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.379529854438, 1.10247697509)
++The right bound: 0.379529854437909
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.379529854437908, 0.616916145872958), (1.10247697508665, 1.91266323979466)]
Bones: ((0.379529854437908, 0.616916145872958), (1.10247697508665, 1.91266323979466))
->Left bound: 0.379529854437909
2
My priority point is: []
I am a: Line
roots are: (0.379529854438, 1.10247697509)
++The right bound: 1.10247697508665
I am here
Belongs to: 2
this is the idx 2
<<In circle event the index: 2
this is the idx 2
<<In circle event the index: 6

Queue content:
(0.627572016460905, 0.464044943820225)
(0.459876543209876, 0.359550561797753)
(0.298353909465021, 0.433707865168539)
(0.298825821533728, 0.214112020414623)
*********** 3 *************
New parabola at: (0.627572016460905, 0.464044943820225)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.29777321627896, 2.26269511591816), (0.365478688107696, 0.591732066126924)]
Bones: ((0.365478688107696, 0.591732066126924), (1.29777321627896, 2.26269511591816))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.365478688108, 1.29777321628)
++The right bound: 0.365478688107696
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.697329846315391, 0.693903384508474), (0.465907465070068, 0.565194305227238)]
Bones: ((0.465907465070068, 0.565194305227238), (0.697329846315391, 0.693903384508474))
->Left bound: 0.365478688107696
2
My priority point is: []
I am a: Line
roots are: (0.46590746507, 0.697329846315)
++The right bound: 0.465907465070068
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.465907465070068, 0.565194305227239), (0.697329846315391, 0.693903384508474)]
Bones: ((0.465907465070068, 0.565194305227239), (0.697329846315391, 0.693903384508474))
->Left bound: 0.465907465070068
3
My priority point is: []
I am a: Line
roots are: (0.46590746507, 0.697329846315)
++The right bound: 0.697329846315391
Belongs to: 4
++The right bound: 0.697329846315391
1
this is the idx 4
<<In circle event the index: 4
this is the idx 4
<<In circle event the index: 8
Event discarded: I already have it

Queue content:
(0.750276515989413, 0.436488112450604)
(0.298353909465021, 0.433707865168539)
(0.298825821533728, 0.214112020414623)
(0.459876543209876, 0.359550561797753)
*********** 4 *************
Circle event in action
>I want to erase: (0.750276515989413, 0.436488112450604)
max index: 2
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.553497942386831, 0.514606741573034)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.40406116143913, 2.45319631874004), (0.357971644468610, 0.578277098672927)]
Bones: ((0.357971644468610, 0.578277098672927), (1.40406116143913, 2.45319631874004))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.357971644469, 1.40406116144)
++The right bound: 0.357971644468609
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.750257805908300, 0.723340074731691), (0.443631807768806, 0.552805359412224)]
Bones: ((0.443631807768806, 0.552805359412224), (0.750257805908300, 0.723340074731691))
->Left bound: 0.357971644468609
2
My priority point is: []
I am a: Line
roots are: (0.443631807769, 0.750257805908)
++The right bound: 0.443631807768806
I going to graph a line
I am the 3  parabola
I have an event at: (0.750276515989413, 0.436488112450604)
basis_inter_parab: [(0.750241666356253, 0.723299425198395), (0.585645016504529, 0.482161946403276)]
Bones: ((0.585645016504529, 0.482161946403276), (0.750241666356253, 0.723299425198395))
->Left bound: 0.443631807768806
3
My priority point is: []
I am a: Line
roots are: (0.585645016505, 0.750241666356)
++The right bound: 0.585645016504529
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.585645016504529, 0.482161946403276), (0.750241666356253, 0.723299425198395)]
Bones: ((0.585645016504529, 0.482161946403276), (0.750241666356253, 0.723299425198395))
->Left bound: 0.585645016504529
4
My priority point is: []
I am a: Line
roots are: (0.585645016505, 0.750241666356)
++The right bound: 0.750241666356253
I going to graph a line
I am the 5  parabola
I have an event at: (0.750276515989413, 0.436488112450604)
basis_inter_parab: [(0.443631807768806, 0.552805359412225), (0.750257805908300, 0.723340074731691)]
Bones: ((0.443631807768806, 0.552805359412225), (0.750257805908300, 0.723340074731691))
->Left bound: 0.750241666356253
5
My priority point is: []
I am a: Line
roots are: (0.443631807769, 0.750257805908)
++The right bound: 0.750257805908300
++The right bound: 0.750257805908300
1
Delta: (0.0000161395520470453, 8)
Real index: 8
<<In circle event the index: 6
I have seen this cirlce event before
<<In circle event the index: 8

Queue content:
(0.298353909465021, 0.433707865168539)
(0.459876543209876, 0.359550561797753)
(0.298825821533728, 0.214112020414623)
*********** 5 *************
New parabola at: (0.298353909465021, 0.433707865168539)
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(1.41478065445153, 2.47240899906259), (0.357218294852386, 0.576926860808984)]
Bones: ((0.357218294852386, 0.576926860808984), (1.41478065445153, 2.47240899906259))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.357218294852, 1.41478065445)
++The right bound: 0.357218294852386
Belongs to: 0
I going to graph a line
I am the 2  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.755449379184910, 0.726227447218559), (0.441532788167628, 0.551637957716645)]
Bones: ((0.750276515989413, 0.723350480628044), (0.441532788167628, 0.551637957716645))
->Left bound: 0.357218294852386
2
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.441532788168, 0.755449379185)
++The right bound: 0.441532788167628
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.759889808902626, 0.737434152550283), (0.584143112908074, 0.479961626731104)]
Bones: ((0.750276515989413, 0.723350480628044), (0.584143112908074, 0.479961626731104))
->Left bound: 0.441532788167628
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.584143112908, 0.759889808903)
++The right bound: 0.584143112908075
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.544632115373570, 0.562252963776151), (0.758042781745772, 0.729434410580986)]
Bones: ((0.750276515989413, 0.723350480628044), (0.758042781745772, 0.729434410580986))
->Left bound: 0.584143112908075
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.544632115374, 0.758042781746)
++The right bound: 0.758042781745772
++The right bound: 0.758042781745772
1
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4

Queue content:
(0.354270075660151, 0.422815085041361)
(0.298825821533728, 0.214112020414623)
(0.459876543209876, 0.359550561797753)
*********** 6 *************
Circle event in action
>I want to erase: (0.354270075660151, 0.422815085041361)
max index: 1
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.374485596707819, 0.719101123595506)
6 (0.469135802469136, 0.666292134831461)
8 (0.553497942386831, 0.514606741573034)
10 (0.627572016460905, 0.464044943820225)
12 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.354244767978654, 0.571649482065496), (0.236651521033563, 0.603018731457138)]
Bones: ((0.236651521033563, 0.603018731457138), (0.354244767978654, 0.571649482065496))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.236651521034, 0.354244767979)
++The right bound: 0.236651521033563
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.236651521033563, 0.603018731457138), (0.354244767978654, 0.571649482065496)]
Bones: ((0.236651521033563, 0.603018731457138), (0.354244767978654, 0.571649482065496))
->Left bound: 0.236651521033563
2
My priority point is: []
I am a: Line
roots are: (0.236651521034, 0.354244767979)
++The right bound: 0.354244767978654
I going to graph a line
I am the 3  parabola
I have an event at: (0.354270075660151, 0.422815085041361)
basis_inter_parab: [(1.45677270367492, 2.54767186987976), (0.354272775565659, 0.571647570046415)]
Bones: ((0.354272775565659, 0.571647570046415), (1.45677270367492, 2.54767186987976))
->Left bound: 0.354244767978654
3
My priority point is: []
I am a: Line
roots are: (0.354272775566, 1.45677270367)
++The right bound: 0.354272775565659
I going to graph a line
I am the 4  parabola
I have an event at: (0.298825821533728, 0.214112020414623)
basis_inter_parab: [(0.775611242851029, 0.737440774534162), (0.433487295385238, 0.547163334463643)]
Bones: ((0.750276515989413, 0.723350480628044), (0.433487295385238, 0.547163334463643))
->Left bound: 0.354272775565659
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.433487295385, 0.775611242851)
++The right bound: 0.433487295385238
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.797095165681021, 0.791940765772952), (0.578854050164867, 0.472213040983854)]
Bones: ((0.750276515989413, 0.723350480628044), (0.578854050164867, 0.472213040983854))
->Left bound: 0.433487295385238
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.578854050165, 0.797095165681)
++The right bound: 0.578854050164867
Belongs to: 8
I going to graph a line
I am the 6  parabola
I have no events
basis_inter_parab: [(0.532595357310274, 0.552823619582305), (0.787145891480661, 0.752233177272024)]
Bones: ((0.750276515989413, 0.723350480628044), (0.787145891480661, 0.752233177272024))
->Left bound: 0.578854050164867
6
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.53259535731, 0.787145891481)
++The right bound: 0.787145891480661
++The right bound: 0.787145891480661
1
Delta: (0.0000280075870057184, 4)
Real index: 4
>I want to erase: (0.354270075660151, 0.422815085041361)
max index: 1
An event is about to be erased
*** Object not found ***
<<In circle event the index: 2
I have seen this cirlce event before
<<In circle event the index: 4
I already have an event: (0.298825821533728, 0.214112020414623)
>I want to erase: (0.298825821533728, 0.214112020414623)
max index: 1
An event is about to be erased
index: 1
//I replaced an event

Queue content:
(0.407381418280826, 0.385428521165244)
(0.459876543209876, 0.359550561797753)
*********** 7 *************
Circle event in action
>I want to erase: (0.407381418280826, 0.385428521165244)
max index: 0
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.469135802469136, 0.666292134831461)
6 (0.553497942386831, 0.514606741573034)
8 (0.627572016460905, 0.464044943820225)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.416836465520835, 0.554952480995667), (0.154113296346432, 0.625036680802163)]
Bones: ((0.354270075660151, 0.571642730972274), (0.154113296346432, 0.625036680802163))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.154113296346, 0.416836465521)
++The right bound: 0.154113296346432
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.118435512496779, 0.744811248306703), (0.407371228094392, 0.532651636060468)]
Bones: ((0.354270075660151, 0.571642730972274), (0.407371228094392, 0.532651636060468))
->Left bound: 0.154113296346432
2
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.118435512497, 0.407371228094)
++The right bound: 0.407371228094393
I going to graph a line
I am the 3  parabola
I have an event at: (0.407381418280826, 0.385428521165244)
basis_inter_parab: [(0.843296578351523, 0.775085003956705), (0.407388172835195, 0.532647910262286)]
Bones: ((0.750276515989413, 0.723350480628044), (0.407388172835195, 0.532647910262286))
->Left bound: 0.407371228094393
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.407388172835, 0.843296578352)
++The right bound: 0.407388172835195
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.921498457721223, 0.974194148350367), (0.563994928823414, 0.450444122475387)]
Bones: ((0.750276515989413, 0.723350480628044), (0.563994928823414, 0.450444122475387))
->Left bound: 0.407388172835195
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.563994928823, 0.921498457721)
++The right bound: 0.563994928823414
Belongs to: 6
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.500396959580791, 0.527600069097605), (0.877919991597670, 0.823343706318876)]
Bones: ((0.750276515989413, 0.723350480628044), (0.877919991597670, 0.823343706318876))
->Left bound: 0.563994928823414
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.500396959581, 0.877919991598)
++The right bound: 0.877919991597670
++The right bound: 0.877919991597670
1
Delta: (0.0000169447408021051, 4)
Real index: 4
<<In circle event the index: 2
Ignore this possible circle event
<<In circle event the index: 4

Queue content:
(0.459876543209876, 0.359550561797753)
(0.474852700355643, 0.109821589343034)
*********** 8 *************
New parabola at: (0.459876543209876, 0.359550561797753)
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.553497942386831, 0.514606741573034)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.447570753242625, 0.546753782843642), (0.109572566805332, 0.636918394160353)]
Bones: ((0.354270075660151, 0.571642730972274), (0.109572566805332, 0.636918394160353))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.109572566805, 0.447570753243)
++The right bound: 0.109572566805332
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(-0.290313910466906, 2.73308015271672), (0.419257669040293, 0.495188076973279)]
Bones: ((0.407381418280826, 0.532644153614078), (0.419257669040293, 0.495188076973279))
->Left bound: 0.109572566805332
2
My priority point is: [(0.407381418280826, 0.532644153614078)]
I am a: Line
roots are: (-0.290313910467, 0.41925766904)
++The right bound: 0.419257669040293
I going to graph a line
I am the 3  parabola
I have an event at: (0.474852700355643, 0.109821589343034)
basis_inter_parab: [(1.00644082346713, 1.09863646195343), (0.554876048960853, 0.437084775845463)]
Bones: ((0.750276515989413, 0.723350480628044), (0.554876048960853, 0.437084775845463))
->Left bound: 0.419257669040293
3
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.554876048961, 1.00644082347)
++The right bound: 0.554876048960853
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.482003807347006, 0.513191258825756), (0.936857646699633, 0.869514231057530)]
Bones: ((0.750276515989413, 0.723350480628044), (0.936857646699633, 0.869514231057530))
->Left bound: 0.554876048960853
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.482003807347, 0.9368576467)
++The right bound: 0.936857646699633
++The right bound: 0.936857646699633
1
this is the idx 4
<<In circle event the index: 4
I already have an event: (0.474852700355643, 0.109821589343034)
>I want to erase: (0.474852700355643, 0.109821589343034)
max index: 0
An event is about to be erased
index: 0
//I replaced an event
this is the idx 4
<<In circle event the index: 8
I already have an event: (0.474852700355643, 0.109821589343034)
>I want to erase: (0.474852700355643, 0.109821589343034)
max index: 0
An event is about to be erased
*** Object not found ***
//I replaced an event

Queue content:
(0.421344003736544, 0.353931036043738)
(0.540809004826267, 0.317538809843862)
*********** 9 *************
Circle event in action
>I want to erase: (0.421344003736544, 0.353931036043738)
max index: 0
An event is about to be erased
*** Object not found ***
Expected index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.553497942386831, 0.514606741573034)
6 (0.459876543209876, 0.359550561797753)
8 (0.553497942386831, 0.514606741573034)
10 (0.627572016460905, 0.464044943820225)
12 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.453722496323883, 0.545112739944304), (0.100422687191238, 0.639359221869209)]
Bones: ((0.354270075660151, 0.571642730972274), (0.100422687191238, 0.639359221869209))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.100422687191, 0.453722496324)
++The right bound: 0.100422687191238
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(-0.327843086771826, 2.85144206106752), (0.421340408318863, 0.488619401082134)]
Bones: ((0.407381418280826, 0.532644153614078), (0.421340408318863, 0.488619401082134))
->Left bound: 0.100422687191238
2
My priority point is: [(0.407381418280826, 0.532644153614078)]
I am a: Line
roots are: (-0.327843086772, 0.421340408319)
++The right bound: 0.421340408318863
I going to graph a line
I am the 3  parabola
I have an event at: (0.421344003736544, 0.353931036043738)
basis_inter_parab: [(0.491584705002075, 0.446197415746649), (0.421382352449800, 0.488584907048080)]
Bones: ((0.421382352449800, 0.488584907048080), (0.491584705002075, 0.446197415746649))
->Left bound: 0.421340408318863
3
My priority point is: []
I am a: Line
roots are: (0.42138235245, 0.491584705002)
++The right bound: 0.421382352449799
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.421382352449800, 0.488584907048072), (0.491584705002075, 0.446197415746640)]
Bones: ((0.421382352449800, 0.488584907048072), (0.491584705002075, 0.446197415746640))
->Left bound: 0.421382352449799
4
My priority point is: []
I am a: Line
roots are: (0.42138235245, 0.491584705002)
++The right bound: 0.491584705002077
I going to graph a line
I am the 5  parabola
I have an event at: (0.540809004826267, 0.317538809843862)
basis_inter_parab: [(1.02482771828927, 1.12557364119903), (0.552954595854181, 0.434269807508116)]
Bones: ((0.750276515989413, 0.723350480628044), (0.552954595854181, 0.434269807508116))
->Left bound: 0.491584705002077
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.552954595854, 1.02482771829)
++The right bound: 0.552954595854181
Belongs to: 8
I going to graph a line
I am the 6  parabola
I have no events
basis_inter_parab: [(0.478241977779005, 0.510244320322154), (0.949423913851599, 0.879358381582498)]
Bones: ((0.750276515989413, 0.723350480628044), (0.949423913851599, 0.879358381582498))
->Left bound: 0.552954595854181
6
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.478241977779, 0.949423913852)
++The right bound: 0.949423913851600
++The right bound: 0.949423913851600
1
Delta: (0.0000419441309358892, 4)
Real index: 4
<<In circle event the index: 2
Ignore this possible circle event
<<In circle event the index: 4
I have seen this cirlce event before

Queue content:
(0.540809004826267, 0.317538809843862)
*********** 10 *************
Circle event in action
>I want to erase: (0.540809004826267, 0.317538809843862)
max index: -1
An event is about to be erased
*** Object not found ***
Expected index: 6
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.553497942386831, 0.514606741573034)
8 (0.627572016460905, 0.464044943820225)
10 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.490901428434245, 0.535194864353800), (0.0438277282385515, 0.654456529136569)]
Bones: ((0.354270075660151, 0.571642730972274), (0.0438277282385515, 0.654456529136569))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (0.0438277282386, 0.490901428434)
++The right bound: 0.0438277282385516
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.718816712385825, 1.13653582037833), (0.383948660494745, 0.407156956262779)]
Bones: ((0.421344003736544, 0.488608061624679), (0.383948660494745, 0.407156956262779))
->Left bound: 0.0438277282385516
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.383948660495, 0.718816712386)
++The right bound: 0.383948660494745
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(0.328220823153012, 0.544834923879855), (0.540799696457747, 0.416481887044475)]
Bones: ((0.421344003736544, 0.488608061624679), (0.540799696457747, 0.416481887044475))
->Left bound: 0.383948660494745
3
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.328220823153, 0.540799696458)
++The right bound: 0.540799696457747
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have an event at: (0.540809004826267, 0.317538809843862)
basis_inter_parab: [(1.14360074689799, 1.29957857200028), (0.540812287633578, 0.416481076123200)]
Bones: ((0.750276515989413, 0.723350480628044), (0.540812287633578, 0.416481076123200))
->Left bound: 0.540799696457747
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.540812287634, 1.1436007469)
++The right bound: 0.540812287633578
I going to graph a line
I am the 5  parabola
I have no events
basis_inter_parab: [(0.455200224206078, 0.492193893111904), (1.02948348318762, 0.942075371598470)]
Bones: ((0.750276515989413, 0.723350480628044), (1.02948348318762, 0.942075371598470))
->Left bound: 0.540812287633578
5
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.455200224206, 1.02948348319)
++The right bound: 1.02948348318762
++The right bound: 1.02948348318762
1
Delta: (0.0000125911758311892, 6)
Real index: 6
<<In circle event the index: 4
Ignore this possible circle event
<<In circle event the index: 6
Ignore this possible circle event

0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.760648697747172, 0.463236911124201), (-0.395333251066896, 0.771607391458986)]
Bones: ((0.354270075660151, 0.571642730972274), (-0.395333251066896, 0.771607391458986))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-0.395333251067, 0.760648697747)
++The right bound: -0.395333251066896
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(2.18945362779742, 4.33974220818326), (0.296579543420937, 0.216857562187410)]
Bones: ((0.421344003736544, 0.488608061624679), (0.296579543420937, 0.216857562187410))
->Left bound: -0.395333251066896
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (0.296579543421, 2.1894536278)
++The right bound: 0.296579543420937
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-0.889512430861534, 2.71189565117621), (0.655232152973133, 0.232846835112496)]
Bones: ((0.540809004826267, 0.416476266742942), (0.655232152973133, 0.232846835112496))
->Left bound: 0.296579543420937
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-0.889512430862, 0.655232152973)
++The right bound: 0.655232152973133
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(0.284742676866488, 0.358661020236023), (1.69744753803978, 1.46534442371345)]
Bones: ((0.750276515989413, 0.723350480628044), (1.69744753803978, 1.46534442371345))
->Left bound: 0.655232152973133
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (0.284742676866, 1.69744753804)
++The right bound: 1.69744753803978
++The right bound: 1.69744753803978
1

0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(4.61837150618560, -0.565851680317078), (-6.92066242352464, 2.51230835423591)]
Bones: ((0.354270075660151, 0.571642730972274), (-6.92066242352464, 2.51230835423591))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-6.92066242352, 4.61837150619)
++The right bound: -6.92066242352464
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(25.0673364388865, 54.1702473396440), (-0.800220838437692, -2.17209239038003)]
Bones: ((0.421344003736544, 0.488608061624679), (-0.800220838437692, -2.17209239038003))
->Left bound: -6.92066242352464
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (-0.800220838438, 25.0673364389)
++The right bound: -0.800220838437696
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-18.3739254335841, 30.7713650337259), (2.09136868328548, -2.07190477394553)]
Bones: ((0.540809004826267, 0.416476266742942), (2.09136868328548, -2.07190477394553))
->Left bound: -0.800220838437696
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-18.3739254336, 2.09136868329)
++The right bound: 2.09136868328546
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(-2.16032125997597, -1.55675086352956), (11.9763020555864, 9.51758379371196)]
Bones: ((0.750276515989413, 0.723350480628044), (11.9763020555864, 9.51758379371196))
->Left bound: 2.09136868328546
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-2.16032125998, 11.9763020556)
++The right bound: 11.9763020555864
++The right bound: 11.9763020555864
1
EQ = PQ() for p in points: EQ.push(p[1],Event(p)) print EQ._pq event = EQ.pop() pb = Parabola(event.point,x_min,x_max) Attic = [] #html('<!--notruncate-->') BL = BeachLine() BL.data.append(pb) print BL.data tmesh = npy.linspace(-2.5,0.7,100) for t in tmesh: h = Event((10,t)) h.time = True EQ.push(t,h) maxiter = infinity global gcont gcont = 0 global MG global GO global Delta global SL SL = False MG = Graphics() while not EQ.is_empty() and gcont < maxiter: #print 'Queue content:' #for x in EQ._pq: # print x[2].point gcont += 1 #print '***********',gcont,'*************' event = EQ.pop() GO = copy(G) if event.time: BL.find_parabola((0.5,event.y)) elif event.site: print 'New parabola at:',event.point newsite(event.point) else: print 'Circle event in action' terminate(event) if GO == G: continue GO += line([(0,event.y),(1,event.y)]) GO += line([(0,0),(0,1),(1,1),(1,0)]) GO += MG #GO.aspect_ratio = 1 Attic.append(GO) ANIM = animate(Attic,xmin=0,ymin=0,xmax=1,ymax=1,figsize=[5,5]) 
       
WARNING: Output truncated!  
full_output.txt



[(0.719101123595506, 1, <__main__.Event object at 0x6b94810>),
(0.666292134831461, 2, <__main__.Event object at 0x63fcdd0>),
(0.514606741573034, 3, <__main__.Event object at 0x63fced0>),
(0.464044943820225, 4, <__main__.Event object at 0x63fc8d0>),
(0.433707865168539, 5, <__main__.Event object at 0x63fc890>),
(0.359550561797753, 6, <__main__.Event object at 0x63fcb90>)]
[<__main__.Parabola object at 0x6f03310>]
0 (0.374485596707819, 0.719101123595506)
0 (0.374485596707819, 0.719101123595506)
New parabola at: (0.469135802469136, 0.666292134831461)
0 (0.374485596707819, 0.719101123595506)
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.62905956708336364, 1.0641513457549698),
(0.42011530925200552, 0.68965796007876812)]
Bones: ((0.42011530925200552, 0.68965796007876812),
(0.62905956708336364, 1.0641513457549698))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.420115309252, 0.629059567083)
++The right bound: 0.420115309252
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.42011530925200552, 0.68965796007876778),
(0.62905956708336364, 1.0641513457549694)]
Bones: ((0.42011530925200552, 0.68965796007876778),
(0.62905956708336364, 1.0641513457549694))
->Left bound: 0.420115309252
2
My priority point is: []
I am a: Line
roots are: (0.420115309252, 0.629059567083)
++The right bound: 0.629059567083
Belongs to: 2
++The right bound: 0.629059567083
1
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.75839263552382008, 1.2959566089522505),
(0.40664890146413113, 0.66552195032324868)]
Bones: ((0.40664890146413113, 0.66552195032324868),
(0.75839263552382008, 1.2959566089522505))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.406648901464, 0.758392635524)
++The right bound: 0.406648901464
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.40664890146413113, 0.66552195032324868),
(0.75839263552382008, 1.2959566089522505)]
Bones: ((0.40664890146413113, 0.66552195032324868),
(0.75839263552382008, 1.2959566089522505))
->Left bound: 0.406648901464
2

...

->Left bound: 1.36654233681
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-0.926284472117, 6.77472729079)
++The right bound: 6.77472729079
++The right bound: 6.77472729079
1
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(2.6963130104682462, -0.053122132797779914),
(-3.6648007457976268, 1.643772621048784)]
Bones: ((0.354270075660151, 0.571642730972274), (-3.6648007457976268,
1.643772621048784))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-3.6648007458, 2.69631301047)
++The right bound: -3.6648007458
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(13.630060344465406, 29.25862200179861),
(-0.25348595863180118, -0.98124464198126171)]
Bones: ((0.421344003736544, 0.488608061624679), (-0.25348595863180118,
-0.98124464198126171))
->Left bound: -3.6648007458
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (-0.253485958632, 13.6300603445)
++The right bound: -0.253485958632
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-9.6342173207534536, 16.745639825438548),
(1.3757988066599283, -0.92353845240401478)]
Bones: ((0.540809004826267, 0.416476266742942), (1.3757988066599283,
-0.92353845240401478))
->Left bound: -0.253485958632
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-9.63421732075, 1.37579880666)
++The right bound: 1.37579880666
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(-0.94204619598357908, -0.60237969142853376),
(6.8411317012419346, 5.4947988784944846)]
Bones: ((0.750276515989413, 0.723350480628044), (6.8411317012419346,
5.4947988784944846))
->Left bound: 1.37579880666
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-0.942046195984, 6.84113170124)
++The right bound: 6.84113170124
++The right bound: 6.84113170124
1
WARNING: Output truncated!  
full_output.txt



[(0.719101123595506, 1, <__main__.Event object at 0x6b94810>), (0.666292134831461, 2, <__main__.Event object at 0x63fcdd0>), (0.514606741573034, 3, <__main__.Event object at 0x63fced0>), (0.464044943820225, 4, <__main__.Event object at 0x63fc8d0>), (0.433707865168539, 5, <__main__.Event object at 0x63fc890>), (0.359550561797753, 6, <__main__.Event object at 0x63fcb90>)]
[<__main__.Parabola object at 0x6f03310>]
0 (0.374485596707819, 0.719101123595506)
0 (0.374485596707819, 0.719101123595506)
New parabola at: (0.469135802469136, 0.666292134831461)
0 (0.374485596707819, 0.719101123595506)
this is the idx 0
<<In circle event the index: 0
this is the idx 0
<<In circle event the index: 4
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.62905956708336364, 1.0641513457549698), (0.42011530925200552, 0.68965796007876812)]
Bones: ((0.42011530925200552, 0.68965796007876812), (0.62905956708336364, 1.0641513457549698))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.420115309252, 0.629059567083)
++The right bound: 0.420115309252
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.42011530925200552, 0.68965796007876778), (0.62905956708336364, 1.0641513457549694)]
Bones: ((0.42011530925200552, 0.68965796007876778), (0.62905956708336364, 1.0641513457549694))
->Left bound: 0.420115309252
2
My priority point is: []
I am a: Line
roots are: (0.420115309252, 0.629059567083)
++The right bound: 0.629059567083
Belongs to: 2
++The right bound: 0.629059567083
1
0 (0.374485596707819, 0.719101123595506)
2 (0.469135802469136, 0.666292134831461)
4 (0.374485596707819, 0.719101123595506)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(0.75839263552382008, 1.2959566089522505), (0.40664890146413113, 0.66552195032324868)]
Bones: ((0.40664890146413113, 0.66552195032324868), (0.75839263552382008, 1.2959566089522505))
->Left bound: -10
1
My priority point is: []
I am a: Line
roots are: (0.406648901464, 0.758392635524)
++The right bound: 0.406648901464
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(0.40664890146413113, 0.66552195032324868), (0.75839263552382008, 1.2959566089522505)]
Bones: ((0.40664890146413113, 0.66552195032324868), (0.75839263552382008, 1.2959566089522505))
->Left bound: 0.406648901464
2

...

->Left bound: 1.36654233681
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-0.926284472117, 6.77472729079)
++The right bound: 6.77472729079
++The right bound: 6.77472729079
1
0 (0.374485596707819, 0.719101123595506)
2 (0.298353909465021, 0.433707865168539)
4 (0.459876543209876, 0.359550561797753)
6 (0.627572016460905, 0.464044943820225)
8 (0.469135802469136, 0.666292134831461)
I going to graph a line
I am the 1  parabola
I have no events
basis_inter_parab: [(2.6963130104682462, -0.053122132797779914), (-3.6648007457976268, 1.643772621048784)]
Bones: ((0.354270075660151, 0.571642730972274), (-3.6648007457976268, 1.643772621048784))
->Left bound: -10
1
My priority point is: [(0.354270075660151, 0.571642730972274)]
I am a: Line
roots are: (-3.6648007458, 2.69631301047)
++The right bound: -3.6648007458
I going to graph a line
I am the 2  parabola
I have no events
basis_inter_parab: [(13.630060344465406, 29.25862200179861), (-0.25348595863180118, -0.98124464198126171)]
Bones: ((0.421344003736544, 0.488608061624679), (-0.25348595863180118, -0.98124464198126171))
->Left bound: -3.6648007458
2
My priority point is: [(0.421344003736544, 0.488608061624679)]
I am a: Line
roots are: (-0.253485958632, 13.6300603445)
++The right bound: -0.253485958632
I going to graph a line
I am the 3  parabola
I have no events
basis_inter_parab: [(-9.6342173207534536, 16.745639825438548), (1.3757988066599283, -0.92353845240401478)]
Bones: ((0.540809004826267, 0.416476266742942), (1.3757988066599283, -0.92353845240401478))
->Left bound: -0.253485958632
3
My priority point is: [(0.540809004826267, 0.416476266742942)]
I am a: Line
roots are: (-9.63421732075, 1.37579880666)
++The right bound: 1.37579880666
Belongs to: 4
I going to graph a line
I am the 4  parabola
I have no events
basis_inter_parab: [(-0.94204619598357908, -0.60237969142853376), (6.8411317012419346, 5.4947988784944846)]
Bones: ((0.750276515989413, 0.723350480628044), (6.8411317012419346, 5.4947988784944846))
->Left bound: 1.37579880666
4
My priority point is: [(0.750276515989413, 0.723350480628044)]
I am a: Line
roots are: (-0.942046195984, 6.84113170124)
++The right bound: 6.84113170124
++The right bound: 6.84113170124
1
AOBJ = ANIM.show(delay = 150) 
       
ww = PQ() for x in range(10): s=random.randint(0,100) ww.push(s,(s,random.randint(0,100))) for x in ww._pq: print x #while not ww.is_empty(): # print ww.pop() 
       
Traceback (click to the left of this block for traceback)
...
AttributeError: 'tuple' object has no attribute 'point'
Traceback (most recent call last):    #while not ww.is_empty():
  File "", line 1, in <module>
    
  File "/tmp/tmpqVzFpq/___code___.py", line 6, in <module>
    ww.push(s,(s,random.randint(_sage_const_0 ,_sage_const_100 )))
  File "", line 24, in push
    
AttributeError: 'tuple' object has no attribute 'point'
w = Line((1,2),(3,5)) line(((1,2),(3,5))) w.point.append('orange') q = copy(w) q.point.append('bananna') print w.point print q.point 
       
['orange', 'bananna']
['orange', 'bananna']
['orange', 'bananna']
['orange', 'bananna']
w = Graphics() w += circle((3,2),1) 
       
show(w,aspect_ratio = 0.1) 
       
 
       
 
       
 
       
 
       
 
       
 
       
L = [] for k in range(5): color = (random.random(),random.random(),random.random()) c = circle((0,0),k,rgbcolor = color) L.append(c) a = animate(L,xmin = -5,ymin = -5,xmax = 5,ymax = 5,figsize=[5,5]) show(a,delay = 100)