#!/usr/bin/env python ########################################################################### # # Convert a Bezier curve to a polyline # # Once Tk supports "RawCurves" this will not be needed. # # # Author: Orest Shardt # Created: June 29, 2007 # ########################################################################### import math def norm(vector): """Return the norm of a vector""" return math.sqrt(vector[0]**2+vector[1]**2) def splitLine(end0,end1,t): """Split a line at the distance t, with t in (0,1)""" return (end0[0]+t*(end1[0]-end0[0]),end0[1]+t*(end1[1]-end0[1])) def splitBezier(node0,control0,control1,node1,t): """Find the nodes and control points for the segments of a Bezier curve split at t""" a = splitLine(node0,control0,t) b = splitLine(control0,control1,t) c = splitLine(control1,node1,t) d = splitLine(a,b,t) e = splitLine(b,c,t) f = splitLine(d,e,t)#this is the point on the curve at t return ([node0,a,d,f],[f,e,c,node1]) def BezierWidth(node0,control0,control1,node1): """Compute the distance of the control points from the node-node axis""" deltax = node1[0] - node0[0] deltay = node1[1] - node0[1] length = norm((deltax,deltay)) if length == 0: y1 = control0[1]-node0[1] y2 = control1[1]-node0[1] else: cosine = deltax/length sine = deltay/length y1 = cosine*(control0[1]-node0[1])-sine*(control0[0]-node0[0]) y2 = cosine*(control1[1]-node0[1])-sine*(control1[0]-node0[0]) if y1*y2 >= 0: #same sign return max(abs(y1),abs(y2)) else: #opposite sign return abs(y1)+abs(y2) #If the above algorithm fails, this one will work, but it is far from elegant #def computeIntermediates(steps,node0,control0,control1,node1): #pointList = [] #for a in range(0,100,100/steps)+[100]: #t = a/100.0 #t1 = 1-t #x = node0[0]*t1**3+3*control0[0]*t*t1**2+3*control1[0]*t**2*t1+node1[0]*t**3 #y = node0[1]*t1**3+3*control0[1]*t*t1**2+3*control1[1]*t**2*t1+node1[1]*t**3 #pointList.append((x,y)) #return pointList #def makeBezier(steps,node0,control0,control1,node1): #if len(node0)!=2 or len(control0)!=2 or len(control1)!=2 or len(node1)!=2: #return -1 #else: #return [node0]+computeIntermediates(steps,node0,control0,control1,node1)+[node1] def makeBezierIntermediates(node0,control0,control1,node1,epsilon): """Find the points, excluding node0, to be used as the line segment endpoints""" if(BezierWidth(node0,control0,control1,node1) <= epsilon): return [node1] else: splitUp = splitBezier(node0,control0,control1,node1,0.5) return makeBezierIntermediates(*splitUp[0]+[epsilon])+makeBezierIntermediates(*splitUp[1]+[epsilon]) def makeBezier(node0,control0,control1,node1,epsilon=1): """Return the vertices to be used in the polyline representation of a Bezier curve""" return [node0]+makeBezierIntermediates(node0,control0,control1,node1,epsilon) if __name__ == '__main__': pointList = makeBezier((-80,0),(-150,40),(150,120),(80,0),0.5) from timeit import Timer t = Timer('makeBezier((-80,0),(-40,-40),(40,120),(80,0),1)','from __main__ import makeBezier') print pointList print len(pointList) iterations = 1000 time = t.timeit(iterations) print "%d iterations took %f seconds (%f ms for each)."%(iterations,time,1000.0*time/iterations) points = [] for point in pointList: points.append(point[0]) points.append(-point[1]) from Tkinter import * root = Tk() canv = Canvas(root,scrollregion=(-100,-100,100,100)) canv.pack() canv.create_line(points) for point in pointList: canv.create_oval(point[0],-point[1],point[0],-point[1],fill='red',outline='red') root.mainloop()