1from __future__ import division 2from math import sqrt, cos, sin, acos, degrees, radians, log, pi 3from collections import MutableSequence 4from bisect import bisect 5 6# This file contains classes for the different types of SVG path segments as 7# well as a Path object that contains a sequence of path segments. 8 9MIN_DEPTH = 5 10ERROR = 1e-12 11 12 13def segment_length(curve, start, end, start_point, end_point, error, min_depth, depth): 14 """Recursively approximates the length by straight lines""" 15 mid = (start + end) / 2 16 mid_point = curve.point(mid) 17 length = abs(end_point - start_point) 18 first_half = abs(mid_point - start_point) 19 second_half = abs(end_point - mid_point) 20 21 length2 = first_half + second_half 22 if (length2 - length > error) or (depth < min_depth): 23 # Calculate the length of each segment: 24 depth += 1 25 return segment_length( 26 curve, start, mid, start_point, mid_point, error, min_depth, depth 27 ) + segment_length( 28 curve, mid, end, mid_point, end_point, error, min_depth, depth 29 ) 30 # This is accurate enough. 31 return length2 32 33 34class Linear(object): 35 """A straight line 36 37 The base for Line() and Close(). 38 """ 39 40 def __init__(self, start, end): 41 self.start = start 42 self.end = end 43 44 def __ne__(self, other): 45 if not isinstance(other, Line): 46 return NotImplemented 47 return not self == other 48 49 def point(self, pos): 50 distance = self.end - self.start 51 return self.start + distance * pos 52 53 def length(self, error=None, min_depth=None): 54 distance = self.end - self.start 55 return sqrt(distance.real ** 2 + distance.imag ** 2) 56 57 58class Line(Linear): 59 def __repr__(self): 60 return "Line(start=%s, end=%s)" % (self.start, self.end) 61 62 def __eq__(self, other): 63 if not isinstance(other, Line): 64 return NotImplemented 65 return self.start == other.start and self.end == other.end 66 67 68class CubicBezier(object): 69 def __init__(self, start, control1, control2, end): 70 self.start = start 71 self.control1 = control1 72 self.control2 = control2 73 self.end = end 74 75 def __repr__(self): 76 return "CubicBezier(start=%s, control1=%s, control2=%s, end=%s)" % ( 77 self.start, 78 self.control1, 79 self.control2, 80 self.end, 81 ) 82 83 def __eq__(self, other): 84 if not isinstance(other, CubicBezier): 85 return NotImplemented 86 return ( 87 self.start == other.start 88 and self.end == other.end 89 and self.control1 == other.control1 90 and self.control2 == other.control2 91 ) 92 93 def __ne__(self, other): 94 if not isinstance(other, CubicBezier): 95 return NotImplemented 96 return not self == other 97 98 def is_smooth_from(self, previous): 99 """Checks if this segment would be a smooth segment following the previous""" 100 if isinstance(previous, CubicBezier): 101 return self.start == previous.end and (self.control1 - self.start) == ( 102 previous.end - previous.control2 103 ) 104 else: 105 return self.control1 == self.start 106 107 def point(self, pos): 108 """Calculate the x,y position at a certain position of the path""" 109 return ( 110 ((1 - pos) ** 3 * self.start) 111 + (3 * (1 - pos) ** 2 * pos * self.control1) 112 + (3 * (1 - pos) * pos ** 2 * self.control2) 113 + (pos ** 3 * self.end) 114 ) 115 116 def length(self, error=ERROR, min_depth=MIN_DEPTH): 117 """Calculate the length of the path up to a certain position""" 118 start_point = self.point(0) 119 end_point = self.point(1) 120 return segment_length(self, 0, 1, start_point, end_point, error, min_depth, 0) 121 122 123class QuadraticBezier(object): 124 def __init__(self, start, control, end): 125 self.start = start 126 self.end = end 127 self.control = control 128 129 def __repr__(self): 130 return "QuadraticBezier(start=%s, control=%s, end=%s)" % ( 131 self.start, 132 self.control, 133 self.end, 134 ) 135 136 def __eq__(self, other): 137 if not isinstance(other, QuadraticBezier): 138 return NotImplemented 139 return ( 140 self.start == other.start 141 and self.end == other.end 142 and self.control == other.control 143 ) 144 145 def __ne__(self, other): 146 if not isinstance(other, QuadraticBezier): 147 return NotImplemented 148 return not self == other 149 150 def is_smooth_from(self, previous): 151 """Checks if this segment would be a smooth segment following the previous""" 152 if isinstance(previous, QuadraticBezier): 153 return self.start == previous.end and (self.control - self.start) == ( 154 previous.end - previous.control 155 ) 156 else: 157 return self.control == self.start 158 159 def point(self, pos): 160 return ( 161 (1 - pos) ** 2 * self.start 162 + 2 * (1 - pos) * pos * self.control 163 + pos ** 2 * self.end 164 ) 165 166 def length(self, error=None, min_depth=None): 167 a = self.start - 2 * self.control + self.end 168 b = 2 * (self.control - self.start) 169 a_dot_b = a.real * b.real + a.imag * b.imag 170 171 if abs(a) < 1e-12: 172 s = abs(b) 173 elif abs(a_dot_b + abs(a) * abs(b)) < 1e-12: 174 k = abs(b) / abs(a) 175 if k >= 2: 176 s = abs(b) - abs(a) 177 else: 178 s = abs(a) * (k ** 2 / 2 - k + 1) 179 else: 180 # For an explanation of this case, see 181 # http://www.malczak.info/blog/quadratic-bezier-curve-length/ 182 A = 4 * (a.real ** 2 + a.imag ** 2) 183 B = 4 * (a.real * b.real + a.imag * b.imag) 184 C = b.real ** 2 + b.imag ** 2 185 186 Sabc = 2 * sqrt(A + B + C) 187 A2 = sqrt(A) 188 A32 = 2 * A * A2 189 C2 = 2 * sqrt(C) 190 BA = B / A2 191 192 s = ( 193 A32 * Sabc 194 + A2 * B * (Sabc - C2) 195 + (4 * C * A - B ** 2) * log((2 * A2 + BA + Sabc) / (BA + C2)) 196 ) / (4 * A32) 197 return s 198 199 200class Arc(object): 201 def __init__(self, start, radius, rotation, arc, sweep, end): 202 """radius is complex, rotation is in degrees, 203 large and sweep are 1 or 0 (True/False also work)""" 204 205 self.start = start 206 self.radius = radius 207 self.rotation = rotation 208 self.arc = bool(arc) 209 self.sweep = bool(sweep) 210 self.end = end 211 212 self._parameterize() 213 214 def __repr__(self): 215 return "Arc(start=%s, radius=%s, rotation=%s, arc=%s, sweep=%s, end=%s)" % ( 216 self.start, 217 self.radius, 218 self.rotation, 219 self.arc, 220 self.sweep, 221 self.end, 222 ) 223 224 def __eq__(self, other): 225 if not isinstance(other, Arc): 226 return NotImplemented 227 return ( 228 self.start == other.start 229 and self.end == other.end 230 and self.radius == other.radius 231 and self.rotation == other.rotation 232 and self.arc == other.arc 233 and self.sweep == other.sweep 234 ) 235 236 def __ne__(self, other): 237 if not isinstance(other, Arc): 238 return NotImplemented 239 return not self == other 240 241 def _parameterize(self): 242 # Conversion from endpoint to center parameterization 243 # http://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes 244 if self.start == self.end: 245 # This is equivalent of omitting the segment, so do nothing 246 return 247 248 if self.radius.real == 0 or self.radius.imag == 0: 249 # This should be treated as a straight line 250 return 251 252 cosr = cos(radians(self.rotation)) 253 sinr = sin(radians(self.rotation)) 254 dx = (self.start.real - self.end.real) / 2 255 dy = (self.start.imag - self.end.imag) / 2 256 x1prim = cosr * dx + sinr * dy 257 x1prim_sq = x1prim * x1prim 258 y1prim = -sinr * dx + cosr * dy 259 y1prim_sq = y1prim * y1prim 260 261 rx = self.radius.real 262 rx_sq = rx * rx 263 ry = self.radius.imag 264 ry_sq = ry * ry 265 266 # Correct out of range radii 267 radius_scale = (x1prim_sq / rx_sq) + (y1prim_sq / ry_sq) 268 if radius_scale > 1: 269 radius_scale = sqrt(radius_scale) 270 rx *= radius_scale 271 ry *= radius_scale 272 rx_sq = rx * rx 273 ry_sq = ry * ry 274 self.radius_scale = radius_scale 275 else: 276 # SVG spec only scales UP 277 self.radius_scale = 1 278 279 t1 = rx_sq * y1prim_sq 280 t2 = ry_sq * x1prim_sq 281 c = sqrt(abs((rx_sq * ry_sq - t1 - t2) / (t1 + t2))) 282 283 if self.arc == self.sweep: 284 c = -c 285 cxprim = c * rx * y1prim / ry 286 cyprim = -c * ry * x1prim / rx 287 288 self.center = complex( 289 (cosr * cxprim - sinr * cyprim) + ((self.start.real + self.end.real) / 2), 290 (sinr * cxprim + cosr * cyprim) + ((self.start.imag + self.end.imag) / 2), 291 ) 292 293 ux = (x1prim - cxprim) / rx 294 uy = (y1prim - cyprim) / ry 295 vx = (-x1prim - cxprim) / rx 296 vy = (-y1prim - cyprim) / ry 297 n = sqrt(ux * ux + uy * uy) 298 p = ux 299 theta = degrees(acos(p / n)) 300 if uy < 0: 301 theta = -theta 302 self.theta = theta % 360 303 304 n = sqrt((ux * ux + uy * uy) * (vx * vx + vy * vy)) 305 p = ux * vx + uy * vy 306 d = p / n 307 # In certain cases the above calculation can through inaccuracies 308 # become just slightly out of range, f ex -1.0000000000000002. 309 if d > 1.0: 310 d = 1.0 311 elif d < -1.0: 312 d = -1.0 313 delta = degrees(acos(d)) 314 if (ux * vy - uy * vx) < 0: 315 delta = -delta 316 self.delta = delta % 360 317 if not self.sweep: 318 self.delta -= 360 319 320 def point(self, pos): 321 if self.start == self.end: 322 # This is equivalent of omitting the segment 323 return self.start 324 325 if self.radius.real == 0 or self.radius.imag == 0: 326 # This should be treated as a straight line 327 distance = self.end - self.start 328 return self.start + distance * pos 329 330 angle = radians(self.theta + (self.delta * pos)) 331 cosr = cos(radians(self.rotation)) 332 sinr = sin(radians(self.rotation)) 333 radius = self.radius * self.radius_scale 334 335 x = ( 336 cosr * cos(angle) * radius.real 337 - sinr * sin(angle) * radius.imag 338 + self.center.real 339 ) 340 y = ( 341 sinr * cos(angle) * radius.real 342 + cosr * sin(angle) * radius.imag 343 + self.center.imag 344 ) 345 return complex(x, y) 346 347 def length(self, error=ERROR, min_depth=MIN_DEPTH): 348 """The length of an elliptical arc segment requires numerical 349 integration, and in that case it's simpler to just do a geometric 350 approximation, as for cubic bezier curves. 351 """ 352 if self.start == self.end: 353 # This is equivalent of omitting the segment 354 return 0 355 356 if self.radius.real == 0 or self.radius.imag == 0: 357 # This should be treated as a straight line 358 distance = self.end - self.start 359 return sqrt(distance.real ** 2 + distance.imag ** 2) 360 361 if self.radius.real == self.radius.imag: 362 # It's a circle, which simplifies this a LOT. 363 radius = self.radius.real * self.radius_scale 364 return abs(radius * self.delta * pi / 180) 365 366 start_point = self.point(0) 367 end_point = self.point(1) 368 return segment_length(self, 0, 1, start_point, end_point, error, min_depth, 0) 369 370 371class Move(object): 372 """Represents move commands. Does nothing, but is there to handle 373 paths that consist of only move commands, which is valid, but pointless. 374 """ 375 376 def __init__(self, to): 377 self.start = self.end = to 378 379 def __repr__(self): 380 return "Move(to=%s)" % self.start 381 382 def __eq__(self, other): 383 if not isinstance(other, Move): 384 return NotImplemented 385 return self.start == other.start 386 387 def __ne__(self, other): 388 if not isinstance(other, Move): 389 return NotImplemented 390 return not self == other 391 392 def point(self, pos): 393 return self.start 394 395 def length(self, error=ERROR, min_depth=MIN_DEPTH): 396 return 0 397 398 399class Close(Linear): 400 """Represents the closepath command""" 401 402 def __eq__(self, other): 403 if not isinstance(other, Close): 404 return NotImplemented 405 return self.start == other.start and self.end == other.end 406 407 def __repr__(self): 408 return "Close(start=%s, end=%s)" % (self.start, self.end) 409 410 411class Path(MutableSequence): 412 """A Path is a sequence of path segments""" 413 414 def __init__(self, *segments): 415 self._segments = list(segments) 416 self._length = None 417 self._lengths = None 418 # Fractional distance from starting point through the end of each segment. 419 self._fractions = [] 420 421 def __getitem__(self, index): 422 return self._segments[index] 423 424 def __setitem__(self, index, value): 425 self._segments[index] = value 426 self._length = None 427 428 def __delitem__(self, index): 429 del self._segments[index] 430 self._length = None 431 432 def insert(self, index, value): 433 self._segments.insert(index, value) 434 self._length = None 435 436 def reverse(self): 437 # Reversing the order of a path would require reversing each element 438 # as well. That's not implemented. 439 raise NotImplementedError 440 441 def __len__(self): 442 return len(self._segments) 443 444 def __repr__(self): 445 return "Path(%s)" % (", ".join(repr(x) for x in self._segments)) 446 447 def __eq__(self, other): 448 449 if not isinstance(other, Path): 450 return NotImplemented 451 if len(self) != len(other): 452 return False 453 for s, o in zip(self._segments, other._segments): 454 if not s == o: 455 return False 456 return True 457 458 def __ne__(self, other): 459 if not isinstance(other, Path): 460 return NotImplemented 461 return not self == other 462 463 def _calc_lengths(self, error=ERROR, min_depth=MIN_DEPTH): 464 if self._length is not None: 465 return 466 467 lengths = [ 468 each.length(error=error, min_depth=min_depth) for each in self._segments 469 ] 470 self._length = sum(lengths) 471 self._lengths = [each / self._length for each in lengths] 472 # Calculate the fractional distance for each segment to use in point() 473 fraction = 0 474 for each in self._lengths: 475 fraction += each 476 self._fractions.append(fraction) 477 478 def point(self, pos, error=ERROR): 479 480 # Shortcuts 481 if pos == 0.0: 482 return self._segments[0].point(pos) 483 if pos == 1.0: 484 return self._segments[-1].point(pos) 485 486 self._calc_lengths(error=error) 487 # Find which segment the point we search for is located on: 488 i = bisect(self._fractions, pos) 489 if i == 0: 490 segment_pos = pos / self._fractions[0] 491 else: 492 segment_pos = (pos - self._fractions[i - 1]) / ( 493 self._fractions[i] - self._fractions[i - 1] 494 ) 495 return self._segments[i].point(segment_pos) 496 497 def length(self, error=ERROR, min_depth=MIN_DEPTH): 498 self._calc_lengths(error, min_depth) 499 return self._length 500 501 def d(self): 502 current_pos = None 503 parts = [] 504 previous_segment = None 505 end = self[-1].end 506 507 for segment in self: 508 start = segment.start 509 # If the start of this segment does not coincide with the end of 510 # the last segment or if this segment is actually the close point 511 # of a closed path, then we should start a new subpath here. 512 if isinstance(segment, Close): 513 parts.append("Z") 514 elif ( 515 isinstance(segment, Move) 516 or (current_pos != start) 517 or (start == end and not isinstance(previous_segment, Move)) 518 ): 519 parts.append("M {0:G},{1:G}".format(start.real, start.imag)) 520 521 if isinstance(segment, Line): 522 parts.append("L {0:G},{1:G}".format(segment.end.real, segment.end.imag)) 523 elif isinstance(segment, CubicBezier): 524 if segment.is_smooth_from(previous_segment): 525 parts.append( 526 "S {0:G},{1:G} {2:G},{3:G}".format( 527 segment.control2.real, 528 segment.control2.imag, 529 segment.end.real, 530 segment.end.imag, 531 ) 532 ) 533 else: 534 parts.append( 535 "C {0:G},{1:G} {2:G},{3:G} {4:G},{5:G}".format( 536 segment.control1.real, 537 segment.control1.imag, 538 segment.control2.real, 539 segment.control2.imag, 540 segment.end.real, 541 segment.end.imag, 542 ) 543 ) 544 elif isinstance(segment, QuadraticBezier): 545 if segment.is_smooth_from(previous_segment): 546 parts.append( 547 "T {0:G},{1:G}".format(segment.end.real, segment.end.imag) 548 ) 549 else: 550 parts.append( 551 "Q {0:G},{1:G} {2:G},{3:G}".format( 552 segment.control.real, 553 segment.control.imag, 554 segment.end.real, 555 segment.end.imag, 556 ) 557 ) 558 elif isinstance(segment, Arc): 559 parts.append( 560 "A {0:G},{1:G} {2:G} {3:d},{4:d} {5:G},{6:G}".format( 561 segment.radius.real, 562 segment.radius.imag, 563 segment.rotation, 564 int(segment.arc), 565 int(segment.sweep), 566 segment.end.real, 567 segment.end.imag, 568 ) 569 ) 570 571 current_pos = segment.end 572 previous_segment = segment 573 574 return " ".join(parts) 575