1 """fontTools.misc.bezierTools.py -- tools for working with bezier path segments. 2 """ 3 4 from __future__ import print_function, division, absolute_import 5 from fontTools.misc.py23 import * 6 7 __all__ = [ 8 "calcQuadraticBounds", 9 "calcCubicBounds", 10 "splitLine", 11 "splitQuadratic", 12 "splitCubic", 13 "splitQuadraticAtT", 14 "splitCubicAtT", 15 "solveQuadratic", 16 "solveCubic", 17 ] 18 19 from fontTools.misc.arrayTools import calcBounds 20 21 epsilon = 1e-12 22 23 24 def calcQuadraticBounds(pt1, pt2, pt3): 25 """Return the bounding rectangle for a qudratic bezier segment. 26 pt1 and pt3 are the "anchor" points, pt2 is the "handle". 27 28 >>> calcQuadraticBounds((0, 0), (50, 100), (100, 0)) 29 (0, 0, 100, 50.0) 30 >>> calcQuadraticBounds((0, 0), (100, 0), (100, 100)) 31 (0.0, 0.0, 100, 100) 32 """ 33 (ax, ay), (bx, by), (cx, cy) = calcQuadraticParameters(pt1, pt2, pt3) 34 ax2 = ax*2.0 35 ay2 = ay*2.0 36 roots = [] 37 if ax2 != 0: 38 roots.append(-bx/ax2) 39 if ay2 != 0: 40 roots.append(-by/ay2) 41 points = [(ax*t*t + bx*t + cx, ay*t*t + by*t + cy) for t in roots if 0 <= t < 1] + [pt1, pt3] 42 return calcBounds(points) 43 44 45 def calcCubicBounds(pt1, pt2, pt3, pt4): 46 """Return the bounding rectangle for a cubic bezier segment. 47 pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles". 48 49 >>> calcCubicBounds((0, 0), (25, 100), (75, 100), (100, 0)) 50 (0, 0, 100, 75.0) 51 >>> calcCubicBounds((0, 0), (50, 0), (100, 50), (100, 100)) 52 (0.0, 0.0, 100, 100) 53 >>> print "%f %f %f %f" % calcCubicBounds((50, 0), (0, 100), (100, 100), (50, 0)) 54 35.566243 0.000000 64.433757 75.000000 55 """ 56 (ax, ay), (bx, by), (cx, cy), (dx, dy) = calcCubicParameters(pt1, pt2, pt3, pt4) 57 # calc first derivative 58 ax3 = ax * 3.0 59 ay3 = ay * 3.0 60 bx2 = bx * 2.0 61 by2 = by * 2.0 62 xRoots = [t for t in solveQuadratic(ax3, bx2, cx) if 0 <= t < 1] 63 yRoots = [t for t in solveQuadratic(ay3, by2, cy) if 0 <= t < 1] 64 roots = xRoots + yRoots 65 66 points = [(ax*t*t*t + bx*t*t + cx * t + dx, ay*t*t*t + by*t*t + cy * t + dy) for t in roots] + [pt1, pt4] 67 return calcBounds(points) 68 69 70 def splitLine(pt1, pt2, where, isHorizontal): 71 """Split the line between pt1 and pt2 at position 'where', which 72 is an x coordinate if isHorizontal is False, a y coordinate if 73 isHorizontal is True. Return a list of two line segments if the 74 line was successfully split, or a list containing the original 75 line. 76 77 >>> printSegments(splitLine((0, 0), (100, 100), 50, True)) 78 ((0, 0), (50.0, 50.0)) 79 ((50.0, 50.0), (100, 100)) 80 >>> printSegments(splitLine((0, 0), (100, 100), 100, True)) 81 ((0, 0), (100, 100)) 82 >>> printSegments(splitLine((0, 0), (100, 100), 0, True)) 83 ((0, 0), (0.0, 0.0)) 84 ((0.0, 0.0), (100, 100)) 85 >>> printSegments(splitLine((0, 0), (100, 100), 0, False)) 86 ((0, 0), (0.0, 0.0)) 87 ((0.0, 0.0), (100, 100)) 88 """ 89 pt1x, pt1y = pt1 90 pt2x, pt2y = pt2 91 92 ax = (pt2x - pt1x) 93 ay = (pt2y - pt1y) 94 95 bx = pt1x 96 by = pt1y 97 98 if ax == 0: 99 return [(pt1, pt2)] 100 101 t = (where - (bx, by)[isHorizontal]) / ax 102 if 0 <= t < 1: 103 midPt = ax * t + bx, ay * t + by 104 return [(pt1, midPt), (midPt, pt2)] 105 else: 106 return [(pt1, pt2)] 107 108 109 def splitQuadratic(pt1, pt2, pt3, where, isHorizontal): 110 """Split the quadratic curve between pt1, pt2 and pt3 at position 'where', 111 which is an x coordinate if isHorizontal is False, a y coordinate if 112 isHorizontal is True. Return a list of curve segments. 113 114 >>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 150, False)) 115 ((0, 0), (50, 100), (100, 0)) 116 >>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 50, False)) 117 ((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)) 118 ((50.0, 50.0), (75.0, 50.0), (100.0, 0.0)) 119 >>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 25, False)) 120 ((0.0, 0.0), (12.5, 25.0), (25.0, 37.5)) 121 ((25.0, 37.5), (62.5, 75.0), (100.0, 0.0)) 122 >>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 25, True)) 123 ((0.0, 0.0), (7.32233047034, 14.6446609407), (14.6446609407, 25.0)) 124 ((14.6446609407, 25.0), (50.0, 75.0), (85.3553390593, 25.0)) 125 ((85.3553390593, 25.0), (92.6776695297, 14.6446609407), (100.0, -7.1054273576e-15)) 126 >>> # XXX I'm not at all sure if the following behavior is desirable: 127 >>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 50, True)) 128 ((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)) 129 ((50.0, 50.0), (50.0, 50.0), (50.0, 50.0)) 130 ((50.0, 50.0), (75.0, 50.0), (100.0, 0.0)) 131 """ 132 a, b, c = calcQuadraticParameters(pt1, pt2, pt3) 133 solutions = solveQuadratic(a[isHorizontal], b[isHorizontal], 134 c[isHorizontal] - where) 135 solutions = sorted([t for t in solutions if 0 <= t < 1]) 136 if not solutions: 137 return [(pt1, pt2, pt3)] 138 return _splitQuadraticAtT(a, b, c, *solutions) 139 140 141 def splitCubic(pt1, pt2, pt3, pt4, where, isHorizontal): 142 """Split the cubic curve between pt1, pt2, pt3 and pt4 at position 'where', 143 which is an x coordinate if isHorizontal is False, a y coordinate if 144 isHorizontal is True. Return a list of curve segments. 145 146 >>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 150, False)) 147 ((0, 0), (25, 100), (75, 100), (100, 0)) 148 >>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 50, False)) 149 ((0.0, 0.0), (12.5, 50.0), (31.25, 75.0), (50.0, 75.0)) 150 ((50.0, 75.0), (68.75, 75.0), (87.5, 50.0), (100.0, 0.0)) 151 >>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 25, True)) 152 ((0.0, 0.0), (2.2937927384, 9.17517095361), (4.79804488188, 17.5085042869), (7.47413641001, 25.0)) 153 ((7.47413641001, 25.0), (31.2886200204, 91.6666666667), (68.7113799796, 91.6666666667), (92.52586359, 25.0)) 154 ((92.52586359, 25.0), (95.2019551181, 17.5085042869), (97.7062072616, 9.17517095361), (100.0, 1.7763568394e-15)) 155 """ 156 a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4) 157 solutions = solveCubic(a[isHorizontal], b[isHorizontal], c[isHorizontal], 158 d[isHorizontal] - where) 159 solutions = sorted([t for t in solutions if 0 <= t < 1]) 160 if not solutions: 161 return [(pt1, pt2, pt3, pt4)] 162 return _splitCubicAtT(a, b, c, d, *solutions) 163 164 165 def splitQuadraticAtT(pt1, pt2, pt3, *ts): 166 """Split the quadratic curve between pt1, pt2 and pt3 at one or more 167 values of t. Return a list of curve segments. 168 169 >>> printSegments(splitQuadraticAtT((0, 0), (50, 100), (100, 0), 0.5)) 170 ((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)) 171 ((50.0, 50.0), (75.0, 50.0), (100.0, 0.0)) 172 >>> printSegments(splitQuadraticAtT((0, 0), (50, 100), (100, 0), 0.5, 0.75)) 173 ((0.0, 0.0), (25.0, 50.0), (50.0, 50.0)) 174 ((50.0, 50.0), (62.5, 50.0), (75.0, 37.5)) 175 ((75.0, 37.5), (87.5, 25.0), (100.0, 0.0)) 176 """ 177 a, b, c = calcQuadraticParameters(pt1, pt2, pt3) 178 return _splitQuadraticAtT(a, b, c, *ts) 179 180 181 def splitCubicAtT(pt1, pt2, pt3, pt4, *ts): 182 """Split the cubic curve between pt1, pt2, pt3 and pt4 at one or more 183 values of t. Return a list of curve segments. 184 185 >>> printSegments(splitCubicAtT((0, 0), (25, 100), (75, 100), (100, 0), 0.5)) 186 ((0.0, 0.0), (12.5, 50.0), (31.25, 75.0), (50.0, 75.0)) 187 ((50.0, 75.0), (68.75, 75.0), (87.5, 50.0), (100.0, 0.0)) 188 >>> printSegments(splitCubicAtT((0, 0), (25, 100), (75, 100), (100, 0), 0.5, 0.75)) 189 ((0.0, 0.0), (12.5, 50.0), (31.25, 75.0), (50.0, 75.0)) 190 ((50.0, 75.0), (59.375, 75.0), (68.75, 68.75), (77.34375, 56.25)) 191 ((77.34375, 56.25), (85.9375, 43.75), (93.75, 25.0), (100.0, 0.0)) 192 """ 193 a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4) 194 return _splitCubicAtT(a, b, c, d, *ts) 195 196 197 def _splitQuadraticAtT(a, b, c, *ts): 198 ts = list(ts) 199 segments = [] 200 ts.insert(0, 0.0) 201 ts.append(1.0) 202 ax, ay = a 203 bx, by = b 204 cx, cy = c 205 for i in range(len(ts) - 1): 206 t1 = ts[i] 207 t2 = ts[i+1] 208 delta = (t2 - t1) 209 # calc new a, b and c 210 a1x = ax * delta**2 211 a1y = ay * delta**2 212 b1x = (2*ax*t1 + bx) * delta 213 b1y = (2*ay*t1 + by) * delta 214 c1x = ax*t1**2 + bx*t1 + cx 215 c1y = ay*t1**2 + by*t1 + cy 216 217 pt1, pt2, pt3 = calcQuadraticPoints((a1x, a1y), (b1x, b1y), (c1x, c1y)) 218 segments.append((pt1, pt2, pt3)) 219 return segments 220 221 222 def _splitCubicAtT(a, b, c, d, *ts): 223 ts = list(ts) 224 ts.insert(0, 0.0) 225 ts.append(1.0) 226 segments = [] 227 ax, ay = a 228 bx, by = b 229 cx, cy = c 230 dx, dy = d 231 for i in range(len(ts) - 1): 232 t1 = ts[i] 233 t2 = ts[i+1] 234 delta = (t2 - t1) 235 # calc new a, b, c and d 236 a1x = ax * delta**3 237 a1y = ay * delta**3 238 b1x = (3*ax*t1 + bx) * delta**2 239 b1y = (3*ay*t1 + by) * delta**2 240 c1x = (2*bx*t1 + cx + 3*ax*t1**2) * delta 241 c1y = (2*by*t1 + cy + 3*ay*t1**2) * delta 242 d1x = ax*t1**3 + bx*t1**2 + cx*t1 + dx 243 d1y = ay*t1**3 + by*t1**2 + cy*t1 + dy 244 pt1, pt2, pt3, pt4 = calcCubicPoints((a1x, a1y), (b1x, b1y), (c1x, c1y), (d1x, d1y)) 245 segments.append((pt1, pt2, pt3, pt4)) 246 return segments 247 248 249 # 250 # Equation solvers. 251 # 252 253 from math import sqrt, acos, cos, pi 254 255 256 def solveQuadratic(a, b, c, 257 sqrt=sqrt): 258 """Solve a quadratic equation where a, b and c are real. 259 a*x*x + b*x + c = 0 260 This function returns a list of roots. Note that the returned list 261 is neither guaranteed to be sorted nor to contain unique values! 262 """ 263 if abs(a) < epsilon: 264 if abs(b) < epsilon: 265 # We have a non-equation; therefore, we have no valid solution 266 roots = [] 267 else: 268 # We have a linear equation with 1 root. 269 roots = [-c/b] 270 else: 271 # We have a true quadratic equation. Apply the quadratic formula to find two roots. 272 DD = b*b - 4.0*a*c 273 if DD >= 0.0: 274 rDD = sqrt(DD) 275 roots = [(-b+rDD)/2.0/a, (-b-rDD)/2.0/a] 276 else: 277 # complex roots, ignore 278 roots = [] 279 return roots 280 281 282 def solveCubic(a, b, c, d): 283 """Solve a cubic equation where a, b, c and d are real. 284 a*x*x*x + b*x*x + c*x + d = 0 285 This function returns a list of roots. Note that the returned list 286 is neither guaranteed to be sorted nor to contain unique values! 287 """ 288 # 289 # adapted from: 290 # CUBIC.C - Solve a cubic polynomial 291 # public domain by Ross Cottrell 292 # found at: http://www.strangecreations.com/library/snippets/Cubic.C 293 # 294 if abs(a) < epsilon: 295 # don't just test for zero; for very small values of 'a' solveCubic() 296 # returns unreliable results, so we fall back to quad. 297 return solveQuadratic(b, c, d) 298 a = float(a) 299 a1 = b/a 300 a2 = c/a 301 a3 = d/a 302 303 Q = (a1*a1 - 3.0*a2)/9.0 304 R = (2.0*a1*a1*a1 - 9.0*a1*a2 + 27.0*a3)/54.0 305 R2_Q3 = R*R - Q*Q*Q 306 307 if R2_Q3 < 0: 308 theta = acos(R/sqrt(Q*Q*Q)) 309 rQ2 = -2.0*sqrt(Q) 310 x0 = rQ2*cos(theta/3.0) - a1/3.0 311 x1 = rQ2*cos((theta+2.0*pi)/3.0) - a1/3.0 312 x2 = rQ2*cos((theta+4.0*pi)/3.0) - a1/3.0 313 return [x0, x1, x2] 314 else: 315 if Q == 0 and R == 0: 316 x = 0 317 else: 318 x = pow(sqrt(R2_Q3)+abs(R), 1/3.0) 319 x = x + Q/x 320 if R >= 0.0: 321 x = -x 322 x = x - a1/3.0 323 return [x] 324 325 326 # 327 # Conversion routines for points to parameters and vice versa 328 # 329 330 def calcQuadraticParameters(pt1, pt2, pt3): 331 x2, y2 = pt2 332 x3, y3 = pt3 333 cx, cy = pt1 334 bx = (x2 - cx) * 2.0 335 by = (y2 - cy) * 2.0 336 ax = x3 - cx - bx 337 ay = y3 - cy - by 338 return (ax, ay), (bx, by), (cx, cy) 339 340 341 def calcCubicParameters(pt1, pt2, pt3, pt4): 342 x2, y2 = pt2 343 x3, y3 = pt3 344 x4, y4 = pt4 345 dx, dy = pt1 346 cx = (x2 -dx) * 3.0 347 cy = (y2 -dy) * 3.0 348 bx = (x3 - x2) * 3.0 - cx 349 by = (y3 - y2) * 3.0 - cy 350 ax = x4 - dx - cx - bx 351 ay = y4 - dy - cy - by 352 return (ax, ay), (bx, by), (cx, cy), (dx, dy) 353 354 355 def calcQuadraticPoints(a, b, c): 356 ax, ay = a 357 bx, by = b 358 cx, cy = c 359 x1 = cx 360 y1 = cy 361 x2 = (bx * 0.5) + cx 362 y2 = (by * 0.5) + cy 363 x3 = ax + bx + cx 364 y3 = ay + by + cy 365 return (x1, y1), (x2, y2), (x3, y3) 366 367 368 def calcCubicPoints(a, b, c, d): 369 ax, ay = a 370 bx, by = b 371 cx, cy = c 372 dx, dy = d 373 x1 = dx 374 y1 = dy 375 x2 = (cx / 3.0) + dx 376 y2 = (cy / 3.0) + dy 377 x3 = (bx + cx) / 3.0 + x2 378 y3 = (by + cy) / 3.0 + y2 379 x4 = ax + dx + cx + bx 380 y4 = ay + dy + cy + by 381 return (x1, y1), (x2, y2), (x3, y3), (x4, y4) 382 383 384 def _segmentrepr(obj): 385 """ 386 >>> _segmentrepr([1, [2, 3], [], [[2, [3, 4], [0.1, 2.2]]]]) 387 '(1, (2, 3), (), ((2, (3, 4), (0.1, 2.2))))' 388 """ 389 try: 390 it = iter(obj) 391 except TypeError: 392 return str(obj) 393 else: 394 return "(%s)" % ", ".join([_segmentrepr(x) for x in it]) 395 396 397 def printSegments(segments): 398 """Helper for the doctests, displaying each segment in a list of 399 segments on a single line as a tuple. 400 """ 401 for segment in segments: 402 print(_segmentrepr(segment)) 403 404 if __name__ == "__main__": 405 import doctest 406 doctest.testmod() 407
