bezierTools.py revision 8ee2561bc1b45e1e0ed328c392c31137878dc0d8
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 16 >>> calcQuadraticBounds((0, 0), (50, 100), (100, 0)) 17 (0.0, 0.0, 100.0, 50.0) 18 >>> calcQuadraticBounds((0, 0), (100, 0), (100, 100)) 19 (0.0, 0.0, 100.0, 100.0) 20 """ 21 a, b, c = calcQuadraticParameters(pt1, pt2, pt3) 22 # calc first derivative 23 ax, ay = a * 2 24 bx, by = b 25 roots = [] 26 if ax != 0: 27 roots.append(-bx/ax) 28 if ay != 0: 29 roots.append(-by/ay) 30 points = [a*t*t + b*t + c for t in roots if 0 <= t < 1] + [pt1, pt3] 31 return calcBounds(points) 32 33 34def calcCubicBounds(pt1, pt2, pt3, pt4): 35 """Return the bounding rectangle for a cubic bezier segment. 36 pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles". 37 38 >>> calcCubicBounds((0, 0), (25, 100), (75, 100), (100, 0)) 39 (0.0, 0.0, 100.0, 75.0) 40 >>> calcCubicBounds((0, 0), (50, 0), (100, 50), (100, 100)) 41 (0.0, 0.0, 100.0, 100.0) 42 >>> calcCubicBounds((50, 0), (0, 100), (100, 100), (50, 0)) 43 (35.566243270259356, 0.0, 64.433756729740679, 75.0) 44 """ 45 a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4) 46 # calc first derivative 47 ax, ay = a * 3.0 48 bx, by = b * 2.0 49 cx, cy = c 50 xRoots = [t for t in solveQuadratic(ax, bx, cx) if 0 <= t < 1] 51 yRoots = [t for t in solveQuadratic(ay, by, cy) if 0 <= t < 1] 52 roots = xRoots + yRoots 53 54 points = [(a*t*t*t + b*t*t + c * t + d) for t in roots] + [pt1, pt4] 55 return calcBounds(points) 56 57 58def splitLine(pt1, pt2, where, isHorizontal): 59 """Split the line between pt1 and pt2 at position 'where', which 60 is an x coordinate if isHorizontal is False, a y coordinate if 61 isHorizontal is True. Return a list of two line segments if the 62 line was successfully split, or a list containing the original 63 line. 64 65 >>> _tuplify(splitLine((0, 0), (100, 100), 50, True)) 66 (((0, 0), (50.0, 50.0)), ((50.0, 50.0), (100, 100))) 67 >>> _tuplify(splitLine((0, 0), (100, 100), 100, True)) 68 (((0, 0), (100, 100)),) 69 >>> _tuplify(splitLine((0, 0), (100, 100), 0, True)) 70 (((0, 0), (0.0, 0.0)), ((0.0, 0.0), (100, 100))) 71 >>> _tuplify(splitLine((0, 0), (100, 100), 0, False)) 72 (((0, 0), (0.0, 0.0)), ((0.0, 0.0), (100, 100))) 73 """ 74 pt1, pt2 = Numeric.array((pt1, pt2)) 75 a = (pt2 - pt1) 76 b = pt1 77 ax = a[isHorizontal] 78 if ax == 0: 79 return [(pt1, pt2)] 80 t = float(where - b[isHorizontal]) / ax 81 if 0 <= t < 1: 82 midPt = a * t + b 83 return [(pt1, midPt), (midPt, pt2)] 84 else: 85 return [(pt1, pt2)] 86 87 88def splitQuadratic(pt1, pt2, pt3, where, isHorizontal): 89 """Split the quadratic curve between pt1, pt2 and pt3 at position 'where', 90 which is an x coordinate if isHorizontal is False, a y coordinate if 91 isHorizontal is True. Return a list of curve segments. 92 93 >>> splitQuadratic((0, 0), (50, 100), (100, 0), 150, False) 94 [((0, 0), (50, 100), (100, 0))] 95 >>> _tuplify(splitQuadratic((0, 0), (50, 100), (100, 0), 50, False)) 96 (((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)), ((50.0, 50.0), (75.0, 50.0), (100.0, 0.0))) 97 >>> _tuplify(splitQuadratic((0, 0), (50, 100), (100, 0), 25, False)) 98 (((0.0, 0.0), (12.5, 25.0), (25.0, 37.5)), ((25.0, 37.5), (62.5, 75.0), (100.0, 0.0))) 99 >>> _tuplify(splitQuadratic((0, 0), (50, 100), (100, 0), 25, True)) 100 (((0.0, 0.0), (7.3223304703363103, 14.644660940672621), (14.644660940672621, 24.999999999999996)), ((14.644660940672621, 24.999999999999996), (49.999999999999993, 75.0), (85.355339059327363, 25.000000000000025)), ((85.355339059327378, 25.0), (92.677669529663689, 14.644660940672621), (100.0, -7.1054273576010019e-15))) 101 >>> # XXX I'm not at all sure it the following behavior is desirable: 102 >>> _tuplify(splitQuadratic((0, 0), (50, 100), (100, 0), 50, True)) 103 (((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)), ((50.0, 50.0), (50.0, 50.0), (50.0, 50.0)), ((50.0, 50.0), (75.0, 50.0), (100.0, 0.0))) 104 """ 105 a, b, c = calcQuadraticParameters(pt1, pt2, pt3) 106 solutions = solveQuadratic(a[isHorizontal], b[isHorizontal], 107 c[isHorizontal] - where) 108 solutions = [t for t in solutions if 0 <= t < 1] 109 solutions.sort() 110 if not solutions: 111 return [(pt1, pt2, pt3)] 112 113 segments = [] 114 solutions.insert(0, 0.0) 115 solutions.append(1.0) 116 for i in range(len(solutions) - 1): 117 t1 = solutions[i] 118 t2 = solutions[i+1] 119 delta = (t2 - t1) 120 # calc new a, b and c 121 a1 = a * delta**2 122 b1 = (2*a*t1 + b) * delta 123 c1 = a*t1**2 + b*t1 + c 124 # calc new points 125 pt1 = c1 126 pt2 = (b1 * 0.5) + c1 127 pt3 = a1 + b1 + c1 128 segments.append((pt1, pt2, pt3)) 129 return segments 130 131 132def splitCubic(pt1, pt2, pt3, pt4, where, isHorizontal): 133 """Split the cubic curve between pt1, pt2, pt3 and pt4 at position 'where', 134 which is an x coordinate if isHorizontal is False, a y coordinate if 135 isHorizontal is True. Return a list of curve segments.""" 136 a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4) 137 solutions = solveCubic(a[isHorizontal], b[isHorizontal], c[isHorizontal], 138 d[isHorizontal] - where) 139 solutions = [t for t in solutions if 0 <= t < 1] 140 solutions.sort() 141 if not solutions: 142 return [(pt1, pt2, pt3, pt4)] 143 144 segments = [] 145 solutions.insert(0, 0.0) 146 solutions.append(1.0) 147 for i in range(len(solutions) - 1): 148 t1 = solutions[i] 149 t2 = solutions[i+1] 150 delta = (t2 - t1) 151 # calc new a, b, c and d 152 a1 = a * delta**3 153 b1 = (3*a*t1 + b) * delta**2 154 c1 = (2*b*t1 + c + 3*a*t1**2) * delta 155 d1 = a*t1**3 + b*t1**2 + c*t1 + d 156 # calc new points 157 pt1 = d1 158 pt2 = (c1 / 3.0) + d1 159 pt3 = (b1 + c1) / 3.0 + pt2 160 pt4 = a1 + d1 + c1 + b1 161 segments.append((pt1, pt2, pt3, pt4)) 162 return segments 163 164 165# 166# Equation solvers. 167# 168 169from math import sqrt, acos, cos, pi 170 171 172def solveQuadratic(a, b, c, 173 sqrt=sqrt): 174 """Solve a quadratic equation where a, b and c are real. 175 a*x*x + b*x + c = 0 176 This function returns a list of roots. Note that the returned list 177 is neither guaranteed to be sorted nor to contain unique values! 178 """ 179 if a == 0.0: 180 if b == 0.0: 181 # We have a non-equation; therefore, we have no valid solution 182 roots = [] 183 else: 184 # We have a linear equation with 1 root. 185 roots = [-c/b] 186 else: 187 # We have a true quadratic equation. Apply the quadratic formula to find two roots. 188 DD = b*b - 4.0*a*c 189 if DD >= 0.0: 190 rDD = sqrt(DD) 191 roots = [(-b+rDD)/2.0/a, (-b-rDD)/2.0/a] 192 else: 193 # complex roots, ignore 194 roots = [] 195 return roots 196 197 198def solveCubic(a, b, c, d, 199 abs=abs, pow=pow, sqrt=sqrt, cos=cos, acos=acos, pi=pi): 200 """Solve a cubic equation where a, b, c and d are real. 201 a*x*x*x + b*x*x + c*x + d = 0 202 This function returns a list of roots. Note that the returned list 203 is neither guaranteed to be sorted nor to contain unique values! 204 """ 205 # 206 # adapted from: 207 # CUBIC.C - Solve a cubic polynomial 208 # public domain by Ross Cottrell 209 # found at: http://www.strangecreations.com/library/snippets/Cubic.C 210 # 211 if abs(a) < 1e-6: 212 # don't just test for zero; for very small values of 'a' solveCubic() 213 # returns unreliable results, so we fall back to quad. 214 return solveQuadratic(b, c, d) 215 a = float(a) 216 a1 = b/a 217 a2 = c/a 218 a3 = d/a 219 220 Q = (a1*a1 - 3.0*a2)/9.0 221 R = (2.0*a1*a1*a1 - 9.0*a1*a2 + 27.0*a3)/54.0 222 R2_Q3 = R*R - Q*Q*Q 223 224 if R2_Q3 < 0: 225 theta = acos(R/sqrt(Q*Q*Q)) 226 rQ2 = -2.0*sqrt(Q) 227 x0 = rQ2*cos(theta/3.0) - a1/3.0 228 x1 = rQ2*cos((theta+2.0*pi)/3.0) - a1/3.0 229 x2 = rQ2*cos((theta+4.0*pi)/3.0) - a1/3.0 230 return [x0, x1, x2] 231 else: 232 if Q == 0 and R == 0: 233 x = 0 234 else: 235 x = pow(sqrt(R2_Q3)+abs(R), 1/3.0) 236 x = x + Q/x 237 if R >= 0.0: 238 x = -x 239 x = x - a1/3.0 240 return [x] 241 242 243def calcQuadraticParameters(pt1, pt2, pt3): 244 pt1, pt2, pt3 = Numeric.array((pt1, pt2, pt3)) 245 c = pt1 246 b = (pt2 - c) * 2.0 247 a = pt3 - c - b 248 return a, b, c 249 250 251def calcCubicParameters(pt1, pt2, pt3, pt4): 252 pt1, pt2, pt3, pt4 = Numeric.array((pt1, pt2, pt3, pt4)) 253 d = pt1 254 c = (pt2 - d) * 3.0 255 b = (pt3 - pt2) * 3.0 - c 256 a = pt4 - d - c - b 257 return a, b, c, d 258 259 260def _tuplify(obj): 261 """ 262 >>> _tuplify([1, [2, 3], [], [[2, [3, 4]]]]) 263 (1, (2, 3), (), ((2, (3, 4)),)) 264 """ 265 try: 266 it = iter(obj) 267 except TypeError: 268 return obj 269 else: 270 return tuple([_tuplify(x) for x in it]) 271 272 273if __name__ == "__main__": 274 import doctest 275 doctest.testmod() 276