bezierTools.py revision 9524c7bdd383d6c51e0c061e0158b3d2f95ff8ea
1"""fontTools.misc.bezierTools.py -- tools for working with bezier path segments.""" 2 3 4__all__ = ["calcQuadraticBounds", "calcCubicBounds", "splitLine", "splitQuadratic", 5 "splitCubic", "solveQuadratic", "solveCubic"] 6 7 8from fontTools.misc.arrayTools import calcBounds 9import Numeric 10 11 12def calcQuadraticBounds(pt1, pt2, pt3): 13 """Return the bounding rectangle for a qudratic bezier segment. 14 pt1 and pt3 are the "anchor" points, pt2 is the "handle".""" 15 # convert points to Numeric arrays 16 pt1, pt2, pt3 = Numeric.array((pt1, pt2, pt3)) 17 18 # calc quadratic parameters 19 c = pt1 20 b = (pt2 - c) * 2.0 21 a = pt3 - c - b 22 23 # calc first derivative 24 ax, ay = a * 2 25 bx, by = b 26 roots = [] 27 if ax != 0: 28 roots.append(-bx/ax) 29 if ay != 0: 30 roots.append(-by/ay) 31 points = [a*t*t + b*t + c for t in roots if 0 <= t < 1] + [pt1, pt3] 32 return calcBounds(points) 33 34 35def calcCubicBounds(pt1, pt2, pt3, pt4): 36 """Return the bounding rectangle for a cubic bezier segment. 37 pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles".""" 38 # convert points to Numeric arrays 39 pt1, pt2, pt3, pt4 = Numeric.array((pt1, pt2, pt3, pt4)) 40 41 # calc cubic parameters 42 d = pt1 43 c = (pt2 - d) * 3.0 44 b = (pt3 - pt2) * 3.0 - c 45 a = pt4 - d - c - b 46 47 # calc first derivative 48 ax, ay = a * 3.0 49 bx, by = b * 2.0 50 cx, cy = c 51 xRoots = [t for t in solveQuadratic(ax, bx, cx) if 0 <= t < 1] 52 yRoots = [t for t in solveQuadratic(ay, by, cy) if 0 <= t < 1] 53 roots = xRoots + yRoots 54 55 points = [(a*t*t*t + b*t*t + c * t + d) for t in roots] + [pt1, pt4] 56 return calcBounds(points) 57 58 59def splitLine(pt1, pt2, where, isHorizontal): 60 """Split the line between pt1 and pt2 at position 'where', which 61 is an x coordinate if isHorizontal is False, a y coordinate if 62 isHorizontal is True. Return a list of two line segments if the 63 line was successfully split, or a list containing the original 64 line.""" 65 pt1, pt2 = Numeric.array((pt1, pt2)) 66 a = (pt2 - pt1) 67 b = pt1 68 ax = a[isHorizontal] 69 if ax == 0: 70 return [(pt1, pt2)] 71 t = float(where - b[isHorizontal]) / ax 72 if 0 <= t < 1: 73 midPt = a * t + b 74 return [(pt1, midPt), (midPt, pt2)] 75 else: 76 return [(pt1, pt2)] 77 78 79def splitQuadratic(pt1, pt2, pt3, where, isHorizontal): 80 """Split the quadratic curve between pt1, pt2 and pt3 at position 'where', 81 which is an x coordinate if isHorizontal is False, a y coordinate if 82 isHorizontal is True. Return a list of curve segments.""" 83 pt1, pt2, pt3 = Numeric.array((pt1, pt2, pt3)) 84 c = pt1 85 b = (pt2 - c) * 2.0 86 a = pt3 - c - b 87 solutions = solveQuadratic(a[isHorizontal], b[isHorizontal], 88 c[isHorizontal] - where) 89 solutions = [t for t in solutions if 0 <= t < 1] 90 solutions.sort() 91 if not solutions: 92 return [(pt1, pt2, pt3)] 93 94 segments = [] 95 solutions.insert(0, 0.0) 96 solutions.append(1.0) 97 for i in range(len(solutions) - 1): 98 t1 = solutions[i] 99 t2 = solutions[i+1] 100 delta = (t2 - t1) 101 # calc new a, b and c 102 a1 = a * delta**2 103 b1 = (2*a*t1 + b) * delta 104 c1 = a*t1**2 + b*t1 + c 105 # calc new points 106 pt1 = c1 107 pt2 = (b1 * 0.5) + c1 108 pt3 = a1 + b1 + c1 109 segments.append((pt1, pt2, pt3)) 110 return segments 111 112 113def splitCubic(pt1, pt2, pt3, pt4, where, isHorizontal): 114 """Split the cubic curve between pt1, pt2, pt3 and pt4 at position 'where', 115 which is an x coordinate if isHorizontal is False, a y coordinate if 116 isHorizontal is True. Return a list of curve segments.""" 117 pt1, pt2, pt3, pt4 = Numeric.array((pt1, pt2, pt3, pt4)) 118 d = pt1 119 c = (pt2 - d) * 3.0 120 b = (pt3 - pt2) * 3.0 - c 121 a = pt4 - d - c - b 122 123 solutions = solveCubic(a[isHorizontal], b[isHorizontal], c[isHorizontal], 124 d[isHorizontal] - where) 125 solutions = [t for t in solutions if 0 <= t < 1] 126 solutions.sort() 127 if not solutions: 128 return [(pt1, pt2, pt3, pt4)] 129 130 segments = [] 131 solutions.insert(0, 0.0) 132 solutions.append(1.0) 133 for i in range(len(solutions) - 1): 134 t1 = solutions[i] 135 t2 = solutions[i+1] 136 delta = (t2 - t1) 137 # calc new a, b, c and d 138 a1 = a * delta**3 139 b1 = (3*a*t1 + b) * delta**2 140 c1 = (2*b*t1 + c + 3*a*t1**2) * delta 141 d1 = a*t1**3 + b*t1**2 + c*t1 + d 142 # calc new points 143 pt1 = d1 144 pt2 = (c1 / 3.0) + d1 145 pt3 = (b1 + c1) / 3.0 + pt2 146 pt4 = a1 + d1 + c1 + b1 147 segments.append((pt1, pt2, pt3, pt4)) 148 return segments 149 150 151# 152# Equation solvers. 153# 154 155from math import sqrt, acos, cos, pi 156 157 158def solveQuadratic(a, b, c, 159 sqrt=sqrt): 160 """Solve a quadratic equation where a, b and c are real. 161 a*x*x + b*x + c = 0 162 This function returns a list of roots. 163 """ 164 if a == 0.0: 165 if b == 0.0: 166 # We have a non-equation; therefore, we have no valid solution 167 roots = [] 168 else: 169 # We have a linear equation with 1 root. 170 roots = [-c/b] 171 else: 172 # We have a true quadratic equation. Apply the quadratic formula to find two roots. 173 DD = b*b - 4.0*a*c 174 if DD >= 0.0: 175 roots = [(-b+sqrt(DD))/2.0/a, (-b-sqrt(DD))/2.0/a] 176 else: 177 # complex roots, ignore 178 roots = [] 179 return roots 180 181 182def solveCubic(a, b, c, d, 183 abs=abs, pow=pow, sqrt=sqrt, cos=cos, acos=acos, pi=pi): 184 """Solve a cubic equation where a, b, c and d are real. 185 a*x*x*x + b*x*x + c*x + d = 0 186 This function returns a list of roots. 187 """ 188 # 189 # adapted from: 190 # CUBIC.C - Solve a cubic polynomial 191 # public domain by Ross Cottrell 192 # found at: http://www.strangecreations.com/library/snippets/Cubic.C 193 # 194 if abs(a) < 1e-6: 195 # don't just test for zero; for very small values of 'a' solveCubic() 196 # returns unreliable results, so we fall back to quad. 197 return solveQuadratic(b, c, d) 198 a1 = b/a 199 a2 = c/a 200 a3 = d/a 201 202 Q = (a1*a1 - 3.0*a2)/9.0 203 R = (2.0*a1*a1*a1 - 9.0*a1*a2 + 27.0*a3)/54.0 204 R2_Q3 = R*R - Q*Q*Q 205 206 if R2_Q3 <= 0: 207 theta = acos(R/sqrt(Q*Q*Q)) 208 x0 = -2.0*sqrt(Q)*cos(theta/3.0) - a1/3.0 209 x1 = -2.0*sqrt(Q)*cos((theta+2.0*pi)/3.0) - a1/3.0 210 x2 = -2.0*sqrt(Q)*cos((theta+4.0*pi)/3.0) - a1/3.0 211 return [x0, x1, x2] 212 else: 213 x = pow(sqrt(R2_Q3)+abs(R), 1/3.0) 214 x = x + Q/x 215 if R >= 0.0: 216 x = -x 217 x = x - a1/3.0 218 return [x] 219