pyx/path.py

   1 #!/usr/bin/env python
   2 #
   3 #
   4 # Copyright (C) 2002 Jörg Lehmann <joergl@users.sourceforge.net>
   5 # Copyright (C) 2002 André Wobst <wobsta@users.sourceforge.net>
   6 #
   7 # This file is part of PyX (http://pyx.sourceforge.net/).
   8 #
   9 # PyX is free software; you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation; either version 2 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # PyX is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with PyX; if not, write to the Free Software
  21 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22
  23 # TODO: - nocurrentpoint exception?
  24 #       - correct bbox for curveto and bpathel
  25 #         (maybe we still need the current bbox implementation (then maybe called
  26 #          cbox = control box) for bpathel for the use during the
  27 #          intersection of bpaths)
  28
  29 import math
  30 from math import cos, sin, pi
  31 import base, bbox, unit
  32
  33
  34 class PathException(Exception): pass
  35
  36 ################################################################################
  37 # _pathcontext: context during walk along path
  38 ################################################################################
  39
  40 class _pathcontext:
  41
  42     """context during walk along path"""
  43
  44     def __init__(self, currentpoint=None, currentsubpath=None):
  45         """ initialize context
  46
  47         currentpoint:   position of current point
  48         currentsubpath: position of first point of current subpath
  49
  50         """
  51
  52         self.currentpoint = currentpoint
  53         self.currentsubpath = currentsubpath
  54
  55 ################################################################################
  56 # pathel: element of a PS style path
  57 ################################################################################
  58
  59 class pathel(base.PSOp):
  60
  61     """element of a PS style path"""
  62
  63     def _updatecontext(self, context):
  64         """update context of during walk along pathel
  65
  66         changes context in place
  67         """
  68
  69
  70     def _bbox(self, context):
  71         """calculate bounding box of pathel
  72
  73         context: context of pathel
  74
  75         returns bounding box of pathel (in given context)
  76
  77         Important note: all coordinates in bbox, currentpoint, and
  78         currrentsubpath have to be floats (in the unit.topt)
  79
  80         """
  81
  82         pass
  83
  84     def _normalized(self, context):
  85         """returns tupel consisting of normalized version of pathel
  86
  87         context: context of pathel
  88
  89         returns list consisting of corresponding normalized pathels
  90         _moveto, _lineto, _curveto, closepath in given context
  91
  92         """
  93
  94         pass
  95
  96     def write(self, file):
  97         """write pathel to file in the context of canvas"""
  98
  99         pass
 100
 101 ################################################################################
 102 # normpathel: normalized element of a PS style path
 103 ################################################################################
 104
 105 class normpathel(pathel):
 106
 107     """normalized element of a PS style path"""
 108
 109     def _at(self, context, t):
 110         """returns coordinates of point at parameter t (0<=t<=1)
 111
 112         context: context of normpathel
 113
 114         """
 115
 116         pass
 117
 118     def _bcurve(self, context):
 119         """convert normpathel to bpathel
 120
 121         context: context of normpathel
 122
 123         return bpathel corresponding to pathel in the given context
 124
 125         """
 126
 127         pass
 128
 129     def _arclength(self, context, epsilon=1e-5):
 130         """returns arc length of normpathel in pts in given context
 131
 132         context: context of normpathel
 133         epsilon: epsilon controls the accuracy for calculation of the
 134                  length of the Bezier elements
 135
 136         """
 137
 138     def _reversed(self, context):
 139         """return reversed normpathel
 140
 141         context: context of normpathel
 142
 143         """
 144
 145         pass
 146
 147     def _split(self, context, t):
 148         """splits normpathel
 149
 150         context: contex of normpathel
 151         t: parameter value (0<=t<=1) at which to split
 152
 153         returns None or two tuples of normpathels corresponding to
 154         the two parts of the orginal normpathel.
 155
 156         """
 157
 158         pass
 159
 160     def _tangent(self, context, t):
 161         """returns tangent vector of _normpathel at parameter t (0<=t<=1)
 162
 163         context: context of normpathel
 164
 165         """
 166
 167         pass
 168
 169
 170     def transformed(self, trafo):
 171         """return transformed normpathel according to trafo"""
 172
 173         pass
 174
 175
 176
 177 # first come the various normpathels. Each one comes in two variants:
 178 #  - one with an preceding underscore, which does no coordinate to pt conversion
 179 #  - the other without preceding underscore, which converts to pts
 180
 181
 182 class closepath(normpathel):
 183
 184     """Connect subpath back to its starting point"""
 185
 186     def _updatecontext(self, context):
 187         context.currentpoint = None
 188         context.currentsubpath = None
 189
 190     def _at(self, context, t):
 191         x0, y0 = context.currentpoint
 192         x1, y1 = context.currentsubpath
 193         return (unit.t_pt(x0 + (x1-x0)*t), unit.t_pt(y0 + (y1-y0)*t))
 194
 195     def _bbox(self, context):
 196         x0, y0 = context.currentpoint
 197         x1, y1 = context.currentsubpath
 198
 199         return bbox.bbox(min(x0, x1), min(y0, y1),
 200                          max(x0, x1), max(y0, y1))
 201
 202     def _bcurve(self, context):
 203         x0, y0 = context.currentpoint
 204         x1, y1 = context.currentsubpath
 205
 206         return _bline(x0, y0, x1, y1)
 207
 208     def _arclength(self, context, epsilon=1e-5):
 209         x0, y0 = context.currentpoint
 210         x1, y1 = context.currentsubpath
 211
 212         return unit.t_pt(math.sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1)))
 213
 214     def _normalized(self, context):
 215         return [closepath()]
 216
 217     def _reversed(self, context):
 218         return _lineto(*context.currentsubpath)
 219
 220     def _split(self, context, t):
 221         x0, y0 = context.currentpoint
 222         x1, y1 = context.currentsubpath
 223         xs, ys = x0 + (x1-x0)*t, y0 + (y1-y0)*t
 224
 225         return ((_lineto(xs, ys),),
 226                 (_moveto(xs, ys), _lineto(x1, y1)))
 227
 228     def _tangent(self, context, t):
 229         x0, y0 = context.currentpoint
 230         x1, y1 = context.currentsubpath
 231         tx, ty = x0 + (x1-x0)*t, y0 + (y1-y0)*t
 232         tvectx, tvecty = x1-x0, y1-y0
 233
 234         return _line(tx, ty, tx+tvectx, tx+tvecty)
 235
 236     def write(self, file):
 237         file.write("closepath\n")
 238
 239     def transformed(self, trafo):
 240         return closepath()
 241
 242
 243 class _moveto(normpathel):
 244
 245     """Set current point to (x, y) (coordinates in pts)"""
 246
 247     def __init__(self, x, y):
 248          self.x = x
 249          self.y = y
 250
 251     def _at(self, context, t):
 252         return None
 253
 254     def _updatecontext(self, context):
 255         context.currentpoint = self.x, self.y
 256         context.currentsubpath = self.x, self.y
 257
 258     def _bbox(self, context):
 259         return bbox.bbox()
 260
 261     def _bcurve(self, context):
 262         return None
 263
 264     def _arclength(self, context, epsilon=1e-5):
 265         return 0
 266
 267     def _normalized(self, context):
 268         return [_moveto(self.x, self.y)]
 269
 270     def _reversed(self, context):
 271         return None
 272
 273     def _split(self, context, t):
 274         return None
 275
 276     def _tangent(self, context, t):
 277         return None
 278
 279     def write(self, file):
 280         file.write("%f %f moveto\n" % (self.x, self.y) )
 281
 282     def transformed(self, trafo):
 283         return _moveto(*trafo._apply(self.x, self.y))
 284
 285 class _lineto(normpathel):
 286
 287     """Append straight line to (x, y) (coordinates in pts)"""
 288
 289     def __init__(self, x, y):
 290          self.x = x
 291          self.y = y
 292
 293     def _updatecontext(self, context):
 294         context.currentsubpath = context.currentsubpath or context.currentpoint
 295         context.currentpoint = self.x, self.y
 296
 297     def _at(self, context, t):
 298         x0, y0 = context.currentpoint
 299         return (unit.t_pt(x0 + (self.x-x0)*t), unit.t_pt(y0 + (self.y-y0)*t))
 300
 301     def _bbox(self, context):
 302         return bbox.bbox(min(context.currentpoint[0], self.x),
 303                          min(context.currentpoint[1], self.y),
 304                          max(context.currentpoint[0], self.x),
 305                          max(context.currentpoint[1], self.y))
 306
 307     def _bcurve(self, context):
 308         return _bline(context.currentpoint[0], context.currentpoint[1],
 309                       self.x, self.y)
 310
 311     def _arclength(self, context, epsilon=1e-5):
 312         x0, y0 = context.currentpoint
 313
 314         return unit.t_pt(math.sqrt((x0-self.x)*(x0-self.x)+(y0-self.y)*(y0-self.y)))
 315
 316     def _normalized(self, context):
 317         return [_lineto(self.x, self.y)]
 318
 319     def _reversed(self, context):
 320         return _lineto(*context.currentpoint)
 321
 322     def _split(self, context, t):
 323         x0, y0 = context.currentpoint
 324         xs, ys = x0 + (self.x-x0)*t, y0 + (self.y-y0)*t
 325
 326         return ((_lineto(xs, ys),),
 327                 (_moveto(xs, ys), _lineto(self.x, self.y)))
 328
 329     def _tangent(self, context, t):
 330         x0, y0 = context.currentpoint
 331         tx, ty = x0 + (self.x-x0)*t, y0 + (self.y-y0)*t
 332         tvectx, tvecty = self.x-x0, self.y-y0
 333
 334         return _line(tx, ty, tx+tvectx, ty+tvecty)
 335
 336     def write(self, file):
 337         file.write("%f %f lineto\n" % (self.x, self.y) )
 338
 339     def transformed(self, trafo):
 340         return _lineto(*trafo._apply(self.x, self.y))
 341
 342
 343 class _curveto(normpathel):
 344
 345     """Append curveto (coordinates in pts)"""
 346
 347     def __init__(self, x1, y1, x2, y2, x3, y3):
 348         self.x1 = x1
 349         self.y1 = y1
 350         self.x2 = x2
 351         self.y2 = y2
 352         self.x3 = x3
 353         self.y3 = y3
 354
 355     def _updatecontext(self, context):
 356         context.currentsubpath = context.currentsubpath or context.currentpoint
 357         context.currentpoint = self.x3, self.y3
 358
 359     def _at(self, context, t):
 360         x0, y0 = context.currentpoint
 361         return ( unit.t_pt((  -x0+3*self.x1-3*self.x2+self.x3)*t*t*t +
 362                            ( 3*x0-6*self.x1+3*self.x2        )*t*t +
 363                            (-3*x0+3*self.x1                  )*t +
 364                                x0) ,
 365                  unit.t_pt((  -y0+3*self.y1-3*self.y2+self.y3)*t*t*t +
 366                            ( 3*y0-6*self.y1+3*self.y2        )*t*t +
 367                            (-3*y0+3*self.y1                  )*t +
 368                                y0)
 369                )
 370
 371     def _bbox(self, context):
 372         return bbox.bbox(min(context.currentpoint[0], self.x1, self.x2, self.x3),
 373                          min(context.currentpoint[1], self.y1, self.y2, self.y3),
 374                          max(context.currentpoint[0], self.x1, self.x2, self.x3),
 375                          max(context.currentpoint[1], self.y1, self.y2, self.y3))
 376
 377     def _bcurve(self, context):
 378         return _bcurve(context.currentpoint[0], context.currentpoint[1],
 379                         self.x1, self.y1,
 380                         self.x2, self.y2,
 381                         self.x3, self.y3)
 382
 383     def _arclength(self, context, epsilon=1e-5):
 384         return self._bcurve(context).arclength(epsilon)
 385
 386     def _normalized(self, context):
 387         return [_curveto(self.x1, self.y1,
 388                          self.x2, self.y2,
 389                          self.x3, self.y3)]
 390
 391     def _reversed(self, context):
 392         return _curveto(self.x2, self.y2,
 393                         self.x1, self.y1,
 394                         context.currentpoint[0], context.currentpoint[1])
 395
 396     def _split(self, context, t):
 397         bp1, bp2 = self._bcurve(context).split(t)
 398
 399         return ((_curveto(bp1.x1, bp1.y1, bp1.x2, bp1.y2, bp1.x3, bp1.y3),),
 400                 (_moveto(bp2.x0, bp2.y0),
 401                 _curveto(bp2.x1, bp2.y1, bp2.x2, bp2.y2, bp2.x3, bp2.y3)))
 402
 403     def _tangent(self, context, t):
 404         x0, y0 = context.currentpoint
 405         tp = self._at(context, t)
 406         tpx, tpy = unit.topt(tp[0]), unit.topt(tp[1])
 407         tvectx = (3*(  -x0+3*self.x1-3*self.x2+self.x3)*t*t +
 408                   2*( 3*x0-6*self.x1+3*self.x2        )*t +
 409                     (-3*x0+3*self.x1                  ))
 410         tvecty = (3*(  -y0+3*self.y1-3*self.y2+self.y3)*t*t +
 411                   2*( 3*y0-6*self.y1+3*self.y2        )*t +
 412                     (-3*y0+3*self.y1                  ))
 413
 414         return _line(tpx, tpy, tpx+tvectx, tpy+tvecty)
 415
 416     def write(self, file):
 417         file.write("%f %f %f %f %f %f curveto\n" % ( self.x1, self.y1,
 418                                                      self.x2, self.y2,
 419                                                      self.x3, self.y3 ) )
 420
 421     def transformed(self, trafo):
 422         return _curveto(*(trafo._apply(self.x1, self.y1)+
 423                           trafo._apply(self.x2, self.y2)+
 424                           trafo._apply(self.x3, self.y3)))
 425
 426 #
 427 # now the versions that convert from user coordinates to pts
 428 #
 429
 430 class moveto(_moveto):
 431
 432     """Set current point to (x, y)"""
 433
 434     def __init__(self, x, y):
 435          _moveto.__init__(self, unit.topt(x), unit.topt(y))
 436
 437
 438 class lineto(_lineto):
 439
 440     """Append straight line to (x, y)"""
 441
 442     def __init__(self, x, y):
 443         _lineto.__init__(self, unit.topt(x), unit.topt(y))
 444
 445
 446 class curveto(_curveto):
 447
 448     """Append curveto"""
 449
 450     def __init__(self, x1, y1, x2, y2, x3, y3):
 451         _curveto.__init__(self,
 452                           unit.topt(x1), unit.topt(y1),
 453                           unit.topt(x2), unit.topt(y2),
 454                           unit.topt(x3), unit.topt(y3))
 455
 456 #
 457 # now come the pathels, again in two versions
 458 #
 459
 460 class _rmoveto(pathel):
 461
 462     """Perform relative moveto (coordinates in pts)"""
 463
 464     def __init__(self, dx, dy):
 465          self.dx = dx
 466          self.dy = dy
 467
 468     def _updatecontext(self, context):
 469         context.currentpoint = (context.currentpoint[0] + self.dx,
 470                                 context.currentpoint[1] + self.dy)
 471         context.currentsubpath = context.currentpoint
 472
 473     def _bbox(self, context):
 474         return bbox.bbox()
 475
 476     def _normalized(self, context):
 477         x = context.currentpoint[0]+self.dx
 478         y = context.currentpoint[1]+self.dy
 479
 480         return [_moveto(x, y)]
 481
 482     def write(self, file):
 483         file.write("%f %f rmoveto\n" % (self.dx, self.dy) )
 484
 485
 486 class _rlineto(pathel):
 487
 488     """Perform relative lineto (coordinates in pts)"""
 489
 490     def __init__(self, dx, dy):
 491          self.dx = dx
 492          self.dy = dy
 493
 494     def _updatecontext(self, context):
 495         context.currentsubpath = context.currentsubpath or context.currentpoint
 496         context.currentpoint = (context.currentpoint[0]+self.dx,
 497                                 context.currentpoint[1]+self.dy)
 498
 499     def _bbox(self, context):
 500         x = context.currentpoint[0] + self.dx
 501         y = context.currentpoint[1] + self.dy
 502         return bbox.bbox(min(context.currentpoint[0], x),
 503                          min(context.currentpoint[1], y),
 504                          max(context.currentpoint[0], x),
 505                          max(context.currentpoint[1], y))
 506
 507     def _normalized(self, context):
 508         x = context.currentpoint[0] + self.dx
 509         y = context.currentpoint[1] + self.dy
 510
 511         return [_lineto(x, y)]
 512
 513     def write(self, file):
 514         file.write("%f %f rlineto\n" % (self.dx, self.dy) )
 515
 516
 517 class _rcurveto(pathel):
 518
 519     """Append rcurveto (coordinates in pts)"""
 520
 521     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
 522         self.dx1 = dx1
 523         self.dy1 = dy1
 524         self.dx2 = dx2
 525         self.dy2 = dy2
 526         self.dx3 = dx3
 527         self.dy3 = dy3
 528
 529     def write(self, file):
 530         file.write("%f %f %f %f %f %f rcurveto\n" % ( self.dx1, self.dy1,
 531                                                     self.dx2, self.dy2,
 532                                                     self.dx3, self.dy3 ) )
 533
 534     def _updatecontext(self, context):
 535         x3 = context.currentpoint[0]+self.dx3
 536         y3 = context.currentpoint[1]+self.dy3
 537
 538         context.currentsubpath = context.currentsubpath or context.currentpoint
 539         context.currentpoint = x3, y3
 540
 541
 542     def _bbox(self, context):
 543         x1 = context.currentpoint[0]+self.dx1
 544         y1 = context.currentpoint[1]+self.dy1
 545         x2 = context.currentpoint[0]+self.dx2
 546         y2 = context.currentpoint[1]+self.dy2
 547         x3 = context.currentpoint[0]+self.dx3
 548         y3 = context.currentpoint[1]+self.dy3
 549         return bbox.bbox(min(context.currentpoint[0], x1, x2, x3),
 550                          min(context.currentpoint[1], y1, y2, y3),
 551                          max(context.currentpoint[0], x1, x2, x3),
 552                          max(context.currentpoint[1], y1, y2, y3))
 553
 554     def _normalized(self, context):
 555         x2 = context.currentpoint[0]+self.dx1
 556         y2 = context.currentpoint[1]+self.dy1
 557         x3 = context.currentpoint[0]+self.dx2
 558         y3 = context.currentpoint[1]+self.dy2
 559         x4 = context.currentpoint[0]+self.dx3
 560         y4 = context.currentpoint[1]+self.dy3
 561
 562         return [_curveto(x2, y2, x3, y3, x4, y4)]
 563
 564 #
 565 # arc, arcn, arct
 566 #
 567
 568 class _arc(pathel):
 569
 570     """Append counterclockwise arc (coordinates in pts)"""
 571
 572     def __init__(self, x, y, r, angle1, angle2):
 573         self.x = x
 574         self.y = y
 575         self.r = r
 576         self.angle1 = angle1
 577         self.angle2 = angle2
 578
 579     def _sarc(self):
 580         """Return starting point of arc segment"""
 581         return (self.x+self.r*cos(pi*self.angle1/180),
 582                 self.y+self.r*sin(pi*self.angle1/180))
 583
 584     def _earc(self):
 585         """Return end point of arc segment"""
 586         return (self.x+self.r*cos(pi*self.angle2/180),
 587                 self.y+self.r*sin(pi*self.angle2/180))
 588
 589     def _updatecontext(self, context):
 590         if context.currentpoint:
 591             context.currentsubpath = context.currentsubpath or context.currentpoint
 592         else:
 593             # we assert that currentsubpath is also None
 594             context.currentsubpath = self._sarc()
 595
 596         context.currentpoint = self._earc()
 597
 598     def _bbox(self, context):
 599         phi1=pi*self.angle1/180
 600         phi2=pi*self.angle2/180
 601
 602         # starting end end point of arc segment
 603         sarcx, sarcy = self._sarc()
 604         earcx, earcy = self._earc()
 605
 606         # Now, we have to determine the corners of the bbox for the
 607         # arc segment, i.e. global maxima/mimima of cos(phi) and sin(phi)
 608         # in the interval [phi1, phi2]. These can either be located
 609         # on the borders of this interval or in the interior.
 610
 611         if phi2<phi1:
 612             # guarantee that phi2>phi1
 613             phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
 614
 615         # next minimum of cos(phi) looking from phi1 in counterclockwise
 616         # direction: 2*pi*floor((phi1-pi)/(2*pi)) + 3*pi
 617
 618         if phi2<(2*math.floor((phi1-pi)/(2*pi))+3)*pi:
 619             minarcx = min(sarcx, earcx)
 620         else:
 621             minarcx = self.x-self.r
 622
 623         # next minimum of sin(phi) looking from phi1 in counterclockwise
 624         # direction: 2*pi*floor((phi1-3*pi/2)/(2*pi)) + 7/2*pi
 625
 626         if phi2<(2*math.floor((phi1-3.0*pi/2)/(2*pi))+7.0/2)*pi:
 627             minarcy = min(sarcy, earcy)
 628         else:
 629             minarcy = self.y-self.r
 630
 631         # next maximum of cos(phi) looking from phi1 in counterclockwise
 632         # direction: 2*pi*floor((phi1)/(2*pi))+2*pi
 633
 634         if phi2<(2*math.floor((phi1)/(2*pi))+2)*pi:
 635             maxarcx = max(sarcx, earcx)
 636         else:
 637             maxarcx = self.x+self.r
 638
 639         # next maximum of sin(phi) looking from phi1 in counterclockwise
 640         # direction: 2*pi*floor((phi1-pi/2)/(2*pi)) + 1/2*pi
 641
 642         if phi2<(2*math.floor((phi1-pi/2)/(2*pi))+5.0/2)*pi:
 643             maxarcy = max(sarcy, earcy)
 644         else:
 645             maxarcy = self.y+self.r
 646
 647         # Finally, we are able to construct the bbox for the arc segment.
 648         # Note that if there is a currentpoint defined, we also
 649         # have to include the straight line from this point
 650         # to the first point of the arc segment
 651
 652         if context.currentpoint:
 653             return (bbox.bbox(min(context.currentpoint[0], sarcx),
 654                               min(context.currentpoint[1], sarcy),
 655                               max(context.currentpoint[0], sarcx),
 656                               max(context.currentpoint[1], sarcy)) +
 657                     bbox.bbox(minarcx, minarcy, maxarcx, maxarcy)
 658                     )
 659         else:
 660             return  bbox.bbox(minarcx, minarcy, maxarcx, maxarcy)
 661
 662     def _normalized(self, context):
 663         # get starting and end point of arc segment and bpath corresponding to arc
 664         sarcx, sarcy = self._sarc()
 665         earcx, earcy = self._earc()
 666         barc = _arctobezierpath(self.x, self.y, self.r, self.angle1, self.angle2)
 667
 668         # convert to list of curvetos omitting movetos
 669         nbarc = []
 670
 671         for bpathel in barc:
 672             nbarc.append(_curveto(bpathel.x1, bpathel.y1,
 673                                   bpathel.x2, bpathel.y2,
 674                                   bpathel.x3, bpathel.y3))
 675
 676         # Note that if there is a currentpoint defined, we also
 677         # have to include the straight line from this point
 678         # to the first point of the arc segment.
 679         # Otherwise, we have to add a moveto at the beginning
 680         if context.currentpoint:
 681             return [_lineto(sarcx, sarcy)] + nbarc
 682         else:
 683             return [_moveto(sarcx, sarcy)] + nbarc
 684
 685
 686     def write(self, file):
 687         file.write("%f %f %f %f %f arc\n" % ( self.x, self.y,
 688                                             self.r,
 689                                             self.angle1,
 690                                             self.angle2 ) )
 691
 692
 693 class _arcn(pathel):
 694
 695     """Append clockwise arc (coordinates in pts)"""
 696
 697     def __init__(self, x, y, r, angle1, angle2):
 698         self.x = x
 699         self.y = y
 700         self.r = r
 701         self.angle1 = angle1
 702         self.angle2 = angle2
 703
 704     def _sarc(self):
 705         """Return starting point of arc segment"""
 706         return (self.x+self.r*cos(pi*self.angle1/180),
 707                 self.y+self.r*sin(pi*self.angle1/180))
 708
 709     def _earc(self):
 710         """Return end point of arc segment"""
 711         return (self.x+self.r*cos(pi*self.angle2/180),
 712                 self.y+self.r*sin(pi*self.angle2/180))
 713
 714     def _updatecontext(self, context):
 715         if context.currentpoint:
 716             context.currentsubpath = context.currentsubpath or context.currentpoint
 717         else:  # we assert that currentsubpath is also None
 718             context.currentsubpath = self._sarc()
 719
 720         context.currentpoint = self._earc()
 721
 722     def _bbox(self, context):
 723         # in principle, we obtain bbox of an arcn element from
 724         # the bounding box of the corrsponding arc element with
 725         # angle1 and angle2 interchanged. Though, we have to be carefull
 726         # with the straight line segment, which is added if currentpoint
 727         # is defined.
 728
 729         # Hence, we first compute the bbox of the arc without this line:
 730
 731         a = _arc(self.x, self.y, self.r,
 732                  self.angle2,
 733                  self.angle1)
 734
 735         sarc = self._sarc()
 736         arcbb = a._bbox(_pathcontext())
 737
 738         # Then, we repeat the logic from arc.bbox, but with interchanged
 739         # start and end points of the arc
 740
 741         if context.currentpoint:
 742             return  bbox.bbox(min(context.currentpoint[0], sarc[0]),
 743                               min(context.currentpoint[1], sarc[1]),
 744                               max(context.currentpoint[0], sarc[0]),
 745                               max(context.currentpoint[1], sarc[1]))+ arcbb
 746         else:
 747             return arcbb
 748
 749     def _normalized(self, context):
 750         # get starting and end point of arc segment and bpath corresponding to arc
 751         sarcx, sarcy = self._sarc()
 752         earcx, earcy = self._earc()
 753         barc = _arctobezierpath(self.x, self.y, self.r, self.angle2, self.angle1)
 754         barc.reverse()
 755
 756         # convert to list of curvetos omitting movetos
 757         nbarc = []
 758
 759         for bpathel in barc:
 760             nbarc.append(_curveto(bpathel.x2, bpathel.y2,
 761                                   bpathel.x1, bpathel.y1,
 762                                   bpathel.x0, bpathel.y0))
 763
 764         # Note that if there is a currentpoint defined, we also
 765         # have to include the straight line from this point
 766         # to the first point of the arc segment.
 767         # Otherwise, we have to add a moveto at the beginning
 768         if context.currentpoint:
 769             return [_lineto(sarcx, sarcy)] + nbarc
 770         else:
 771             return [_moveto(sarcx, sarcy)] + nbarc
 772
 773
 774     def write(self, file):
 775         file.write("%f %f %f %f %f arcn\n" % ( self.x, self.y,
 776                                              self.r,
 777                                              self.angle1,
 778                                              self.angle2 ) )
 779
 780
 781 class _arct(pathel):
 782
 783     """Append tangent arc (coordinates in pts)"""
 784
 785     def __init__(self, x1, y1, x2, y2, r):
 786         self.x1 = x1
 787         self.y1 = y1
 788         self.x2 = x2
 789         self.y2 = y2
 790         self.r  = r
 791
 792     def write(self, file):
 793         file.write("%f %f %f %f %f arct\n" % ( self.x1, self.y1,
 794                                              self.x2, self.y2,
 795                                              self.r ) )
 796     def _path(self, currentpoint, currentsubpath):
 797         """returns new currentpoint, currentsubpath and path consisting
 798         of arc and/or line which corresponds to arct
 799
 800         this is a helper routine for _bbox and _normalized, which both need
 801         this path. Note: we don't want to calculate the bbox from a bpath
 802
 803         """
 804
 805         # direction and length of tangent 1
 806         dx1  = currentpoint[0]-self.x1
 807         dy1  = currentpoint[1]-self.y1
 808         l1   = math.sqrt(dx1*dx1+dy1*dy1)
 809
 810         # direction and length of tangent 2
 811         dx2  = self.x2-self.x1
 812         dy2  = self.y2-self.y1
 813         l2   = math.sqrt(dx2*dx2+dy2*dy2)
 814
 815         # intersection angle between two tangents
 816         alpha = math.acos((dx1*dx2+dy1*dy2)/(l1*l2))
 817
 818         if math.fabs(sin(alpha))>=1e-15 and 1.0+self.r!=1.0:
 819             cotalpha2 = 1.0/math.tan(alpha/2)
 820
 821             # two tangent points
 822             xt1 = self.x1+dx1*self.r*cotalpha2/l1
 823             yt1 = self.y1+dy1*self.r*cotalpha2/l1
 824             xt2 = self.x1+dx2*self.r*cotalpha2/l2
 825             yt2 = self.y1+dy2*self.r*cotalpha2/l2
 826
 827             # direction of center of arc
 828             rx = self.x1-0.5*(xt1+xt2)
 829             ry = self.y1-0.5*(yt1+yt2)
 830             lr = math.sqrt(rx*rx+ry*ry)
 831
 832             # angle around which arc is centered
 833
 834             if rx==0:
 835                 phi=90
 836             elif rx>0:
 837                 phi = math.atan(ry/rx)/math.pi*180
 838             else:
 839                 phi = math.atan(rx/ry)/math.pi*180+180
 840
 841             # half angular width of arc
 842             deltaphi = 90*(1-alpha/math.pi)
 843
 844             # center position of arc
 845             mx = self.x1-rx*self.r/(lr*sin(alpha/2))
 846             my = self.y1-ry*self.r/(lr*sin(alpha/2))
 847
 848             # now we are in the position to construct the path
 849             p = path(_moveto(*currentpoint))
 850
 851             if phi<0:
 852                 p.append(_arc(mx, my, self.r, phi-deltaphi, phi+deltaphi))
 853             else:
 854                 p.append(_arcn(mx, my, self.r, phi+deltaphi, phi-deltaphi))
 855
 856             return ( (xt2, yt2) ,
 857                      currentsubpath or (xt2, yt2),
 858                      p )
 859
 860         else:
 861             # we need no arc, so just return a straight line to currentpoint to x1, y1
 862             return  ( (self.x1, self.y1),
 863                       currentsubpath or (self.x1, self.y1),
 864                       _line(currentpoint[0], currentpoint[1], self.x1, self.y1) )
 865
 866     def _updatecontext(self, context):
 867         r = self._path(context.currentpoint,
 868                        context.currentsubpath)
 869
 870         context.currentpoint, context.currentsubpath = r[:2]
 871
 872     def _bbox(self, context):
 873         return self._path(context.currentpoint,
 874                           context.currentsubpath)[2].bbox()
 875
 876     def _normalized(self, context):
 877         return _normalizepath(self._path(context.currentpoint,
 878                               context.currentsubpath)[2])
 879
 880 #
 881 # the user coordinates versions...
 882 #
 883
 884 class rmoveto(_rmoveto):
 885
 886     """Perform relative moveto"""
 887
 888     def __init__(self, dx, dy):
 889         _rmoveto.__init__(self, unit.topt(dx), unit.topt(dy))
 890
 891
 892 class rlineto(_rlineto):
 893
 894     """Perform relative lineto"""
 895
 896     def __init__(self, dx, dy):
 897         _rlineto.__init__(self, unit.topt(dx), unit.topt(dy))
 898
 899
 900 class rcurveto(_rcurveto):
 901
 902     """Append rcurveto"""
 903
 904     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
 905         _rcurveto.__init__(self,
 906                            unit.topt(dx1), unit.topt(dy1),
 907                            unit.topt(dx2), unit.topt(dy2),
 908                            unit.topt(dx3), unit.topt(dy3))
 909
 910
 911 class arcn(_arcn):
 912
 913     """Append clockwise arc"""
 914
 915     def __init__(self, x, y, r, angle1, angle2):
 916         _arcn.__init__(self,
 917                        unit.topt(x), unit.topt(y), unit.topt(r),
 918                        angle1, angle2)
 919
 920
 921 class arc(_arc):
 922
 923     """Append counterclockwise arc"""
 924
 925     def __init__(self, x, y, r, angle1, angle2):
 926         _arc.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r),
 927                       angle1, angle2)
 928
 929
 930 class arct(_arct):
 931
 932     """Append tangent arc"""
 933
 934     def __init__(self, x1, y1, x2, y2, r):
 935         _arct.__init__(self, unit.topt(x1), unit.topt(y1),
 936                              unit.topt(x2), unit.topt(y2),
 937                              unit.topt(r))
 938
 939 ################################################################################
 940 # path: PS style path
 941 ################################################################################
 942
 943 class path(base.PSCmd):
 944
 945     """PS style path"""
 946
 947     def __init__(self, *args):
 948         if len(args)==1 and isinstance(args[0], path):
 949             self.path = args[0].path
 950         else:
 951             self.path = list(args)
 952
 953     def __add__(self, other):
 954         return path(*(self.path+other.path))
 955
 956     def __getitem__(self, i):
 957         return self.path[i]
 958
 959     def __len__(self):
 960         return len(self.path)
 961
 962     def append(self, pathel):
 963         self.path.append(pathel)
 964
 965     def arclength(self, epsilon=1e-5):
 966         """returns total arc length of path in pts with accuracy epsilon"""
 967         return normpath(self).arclength(epsilon)
 968
 969     def at(self, t):
 970         """return coordinates of corresponding normpath at parameter value t"""
 971         return normpath(self).at(t)
 972
 973     def bbox(self):
 974         context = _pathcontext()
 975         abbox = bbox.bbox()
 976
 977         for pel in self.path:
 978             nbbox =  pel._bbox(context)
 979             pel._updatecontext(context)
 980             if abbox: abbox = abbox+nbbox
 981
 982         return abbox
 983
 984     def begin(self):
 985         """return first point of first subpath in path"""
 986         return normpath(self).begin()
 987
 988     def end(self):
 989         """return last point of last subpath in path"""
 990         return normpath(self).end()
 991
 992     def glue(self, other):
 993         """return path consisting of self and other glued together"""
 994         return normpath(self).glue(other)
 995
 996     # << operator also designates glueing
 997     __lshift__ = glue
 998
 999     def intersect(self, other, epsilon=1e-5):
1000         """intersect normpath corresponding to self with other path"""
1001         return normpath(self).intersect(other, epsilon)
1002
1003     def range(self):
1004         """return maximal value for parameter value t for corr. normpath"""
1005         return normpath(self).range()
1006
1007     def reversed(self):
1008         """return reversed path"""
1009         return normpath(self).reversed()
1010
1011     def split(self, t):
1012         """return corresponding normpaths split at parameter value t"""
1013         return normpath(self).split(t)
1014
1015     def tangent(self, t):
1016         """return tangent vector at parameter value t of corr. normpath"""
1017         return normpath(self).tangent(t)
1018
1019     def transformed(self, trafo):
1020         """return transformed path"""
1021         return normpath(self).transformed(trafo)
1022
1023     def write(self, file):
1024         if not (isinstance(self.path[0], _moveto) or
1025                 isinstance(self.path[0], _arc) or
1026                 isinstance(self.path[0], _arcn)):
1027             raise PathException, "first path element must be either moveto, arc, or arcn"
1028         for pel in self.path:
1029             pel.write(file)
1030
1031 ################################################################################
1032 # normpath: normalized PS style path
1033 ################################################################################
1034
1035 # helper routine for the normalization of a path
1036
1037 def _normalizepath(path):
1038     context = _pathcontext()
1039     np = []
1040     for pel in path:
1041         npels = pel._normalized(context)
1042         pel._updatecontext(context)
1043         if npels:
1044             for npel in npels:
1045                 np.append(npel)
1046     return np
1047
1048 class normpath(path):
1049
1050     """normalized PS style path"""
1051
1052     def __init__(self, *args):
1053         if len(args)==1 and isinstance(args[0], path):
1054             path.__init__(self, *_normalizepath(args[0].path))
1055         else:
1056             path.__init__(self, *_normalizepath(args))
1057
1058     def __add__(self, other):
1059         return normpath(*(self.path+other.path))
1060
1061     def append(self, pathel):
1062         self.path.append(pathel)
1063         self.path = _normalizepath(self.path)
1064
1065     def arclength(self, epsilon=1e-5):
1066         """returns total arc length of normpath in pts with accuracy epsilon"""
1067
1068         context = _pathcontext()
1069         length = 0
1070
1071         for pel in self.path:
1072             length += pel._arclength(context, epsilon)
1073             pel._updatecontext(context)
1074
1075         return length
1076
1077     def at(self, t):
1078         """return coordinates of path at parameter value t
1079
1080         Negative values of t count from the end of the path. The absolute
1081         value of t must be smaller or equal to the number of segments in
1082         the normpath, otherwise None is returned.
1083         At discontinuities in the path, the limit from below is returned
1084
1085         """
1086
1087         if t>=0:
1088             p = self.path
1089         else:
1090             p = self.reversed().path
1091
1092         context=_pathcontext()
1093
1094         for pel in p:
1095             if not isinstance(pel, _moveto):
1096                 if t>1:
1097                     t -= 1
1098                 else:
1099                     return pel._at(context, t)
1100
1101             pel._updatecontext(context)
1102
1103         return None
1104
1105     def begin(self):
1106         """return first point of first subpath in path"""
1107         return self.at(0)
1108
1109     def end(self):
1110         """return last point of last subpath in path"""
1111         return self.reversed().at(0)
1112
1113     def glue(self, other):
1114         # XXX check for closepath at end and raise Exception
1115         if isinstance(other, normpath):
1116             return normpath(*(self.path+other.path[1:]))
1117         else:
1118             return path(*(self.path+normpath(other).path[1]))
1119
1120     def intersect(self, other, epsilon=1e-5):
1121         """intersect self with other path
1122
1123         returns a list of tuples consisting of the corresponding parameters
1124         of the two bpaths
1125
1126         """
1127
1128         if not isinstance(other, normpath):
1129             other = normpath(other)
1130
1131         intersections = ()
1132         t_a = 0
1133         context_a = _pathcontext()
1134         context_b = _pathcontext()
1135
1136         for normpathel_a in self.path:
1137             bpathel_a = normpathel_a._bcurve(context_a)
1138             normpathel_a._updatecontext(context_a)
1139
1140             if bpathel_a:
1141                 t_a += 1
1142                 t_b = 0
1143                 for normpathel_b in other.path:
1144                     bpathel_b = normpathel_b._bcurve(context_b)
1145                     normpathel_b._updatecontext(context_b)
1146
1147                     if bpathel_b:
1148                         t_b += 1
1149                         intersections = intersections + \
1150                                         _bcurveIntersect(bpathel_a, t_a-1, t_a,
1151                                                          bpathel_b, t_b-1, t_b, epsilon)
1152
1153         return intersections
1154
1155     def range(self):
1156         """return maximal value for parameter value t"""
1157
1158         context=_pathcontext()
1159         t=0
1160
1161         for pel in self.path:
1162             if not isinstance(pel, _moveto):
1163                 t += 1
1164             pel._updatecontext(context)
1165
1166         return t
1167
1168     def reversed(self):
1169         """return reversed path"""
1170
1171         context = _pathcontext()
1172
1173         # we have to reverse subpath by subpath to get the closepaths right
1174         subpath = []
1175         np = normpath()
1176
1177         # we append a _moveto operation at the end to end the last
1178         # subpath explicitely.
1179         for pel in self.path+[_moveto(0,0)]:
1180             pelr =pel._reversed(context)
1181             if pelr:
1182                 subpath.append(pelr)
1183
1184             if subpath and (isinstance(pel, _moveto) or isinstance(pel, closepath)):
1185                 subpath.append(_moveto(*context.currentpoint))
1186                 subpath.reverse()
1187                 if isinstance(pel, closepath):
1188                      subpath.append(closepath())
1189                 np = np + normpath(*subpath)
1190                 subpath = []
1191
1192             pel._updatecontext(context)
1193
1194         return np
1195
1196     def split(self, t):
1197         """split path at parameter value t"""
1198
1199         context = _pathcontext()
1200
1201         np1 = normpath()
1202         # np2 is None is a marker, that we still have to append to np1
1203         np2 = None
1204
1205         for pel in self.path:
1206             if np2 is None:
1207                 # we still have to construct np1
1208                 if isinstance(pel, _moveto):
1209                     np1.path.append(pel)
1210                 else:
1211                     if t>1:
1212                         t -= 1
1213                         np1.path.append(pel)
1214                     else:
1215                         pels1, pels2 = pel._split(context, t)
1216
1217                         for pel1 in pels1:
1218                             np1.path.append(pel1)
1219
1220                         np2 = normpath(*pels2)
1221
1222                         # marker: we are creating the first subpath of np2
1223                         np2isfirstsubpath = 1
1224             else:
1225                 # construction of np2
1226                 # Note: We have to be careful to not close the first subpath!
1227
1228                 if np2isfirstsubpath :
1229                     # closepath and _moveto both end a subpath, but we
1230                     # don't want to append a closepath for the
1231                     # first subpath
1232                     if isinstance(pel, closepath):
1233                         np2isfirstsubpath = 0
1234                     elif isinstance(pel, _moveto):
1235                         np2isfirstsubpath = 0
1236                         np2.path.append(pel)
1237                     else:
1238                         np2.path.append(pel)
1239                 else:
1240                     np2.path.append(pel)
1241
1242             # go further along path
1243             pel._updatecontext(context)
1244
1245         return np1, np2
1246
1247     def tangent(self, t):
1248         """return tangent vector of path at parameter value t
1249
1250         Negative values of t count from the end of the path. The absolute
1251         value of t must be smaller or equal to the number of segments in
1252         the normpath, otherwise None is returned.
1253         At discontinuities in the path, the limit from below is returned
1254
1255         """
1256
1257         if t>=0:
1258             p = self.path
1259         else:
1260             p = self.reversed().path
1261
1262         context=_pathcontext()
1263
1264         for pel in p:
1265             if not isinstance(pel, _moveto):
1266                 if t>1:
1267                     t -= 1
1268                 else:
1269                     return pel._tangent(context, t)
1270
1271             pel._updatecontext(context)
1272
1273         return None
1274
1275     def transformed(self, trafo):
1276         """return transformed path"""
1277         return normpath(*map(lambda x, trafo=trafo: x.transformed(trafo), self.path))
1278
1279 #
1280 # some special kinds of path, again in two variants
1281 #
1282
1283 # straight lines
1284
1285 class _line(normpath):
1286
1287    """straight line from (x1, y1) to (x2, y2) (coordinates in pts)"""
1288
1289    def __init__(self, x1, y1, x2, y2):
1290        normpath.__init__(self, _moveto(x1, y1), _lineto(x2, y2))
1291
1292
1293 class line(_line):
1294
1295    """straight line from (x1, y1) to (x2, y2)"""
1296
1297    def __init__(self, x1, y1, x2, y2):
1298        _line.__init__(self,
1299                       unit.topt(x1), unit.topt(y1),
1300                       unit.topt(x2), unit.topt(y2)
1301                       )
1302
1303 # bezier curves
1304
1305 class _curve(normpath):
1306
1307    """Bezier curve with control points (x0, y1),..., (x3, y3)
1308    (coordinates in pts)"""
1309
1310    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1311        normpath.__init__(self,
1312                          _moveto(x0, y0),
1313                          _curveto(x1, y1, x2, y2, x3, y3))
1314
1315 class curve(_curve):
1316
1317    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
1318
1319    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1320        _curve.__init__(self,
1321                        unit.topt(x0), unit.topt(y0),
1322                        unit.topt(x1), unit.topt(y1),
1323                        unit.topt(x2), unit.topt(y2),
1324                        unit.topt(x3), unit.topt(y3)
1325                       )
1326
1327 # rectangles
1328
1329 class _rect(normpath):
1330
1331    """rectangle at position (x,y) with width and height (coordinates in pts)"""
1332
1333    def __init__(self, x, y, width, height):
1334        path.__init__(self, _moveto(x, y),
1335                            _lineto(x+width, y),
1336                            _lineto(x+width, y+height),
1337                            _lineto(x, y+height),
1338                            closepath())
1339
1340
1341 class rect(_rect):
1342
1343    """rectangle at position (x,y) with width and height"""
1344
1345    def __init__(self, x, y, width, height):
1346        _rect.__init__(self,
1347                       unit.topt(x), unit.topt(y),
1348                       unit.topt(width), unit.topt(height))
1349
1350 # circles
1351
1352 class _circle(path):
1353
1354    """circle with center (x,y) and radius"""
1355
1356    def __init__(self, x, y, radius):
1357        path.__init__(self, _arc(x, y, radius, 0, 360),
1358                            closepath())
1359
1360
1361 class circle(_circle):
1362
1363    """circle with center (x,y) and radius"""
1364
1365    def __init__(self, x, y, radius):
1366        _circle.__init__(self,
1367                         unit.topt(x), unit.topt(y),
1368                         unit.topt(radius))
1369
1370 ################################################################################
1371 # helper classes and routines for Bezier curves
1372 ################################################################################
1373
1374 #
1375 # _bcurve: Bezier curve segment with four control points (coordinates in pts)
1376 #
1377
1378 class _bcurve(base.PSOp):
1379
1380     """element of Bezier path (coordinates in pts)"""
1381
1382     def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1383         self.x0 = x0
1384         self.y0 = y0
1385         self.x1 = x1
1386         self.y1 = y1
1387         self.x2 = x2
1388         self.y2 = y2
1389         self.x3 = x3
1390         self.y3 = y3
1391
1392     def __str__(self):
1393         return "%f %f moveto %f %f %f %f %f %f curveto" % \
1394                ( self.x0, self.y0,
1395                  self.x1, self.y1,
1396                  self.x2, self.y2,
1397                  self.x3, self.y3 )
1398
1399     def write(self, file):
1400          file.write( "%f %f moveto %f %f %f %f %f %f curveto\n" % \
1401                      ( self.x0, self.y0,
1402                        self.x1, self.y1,
1403                        self.x2, self.y2,
1404                        self.x3, self.y3 ) )
1405
1406     def __getitem__(self, t):
1407         """return pathel at parameter value t (0<=t<=1)"""
1408         assert 0 <= t <= 1, "parameter t of pathel out of range [0,1]"
1409         return ( unit.t_pt((  -self.x0+3*self.x1-3*self.x2+self.x3)*t*t*t +
1410                            ( 3*self.x0-6*self.x1+3*self.x2        )*t*t +
1411                            (-3*self.x0+3*self.x1                  )*t +
1412                                self.x0) ,
1413                  unit.t_pt((  -self.y0+3*self.y1-3*self.y2+self.y3)*t*t*t +
1414                            ( 3*self.y0-6*self.y1+3*self.y2        )*t*t +
1415                            (-3*self.y0+3*self.y1                  )*t +
1416                                self.y0)
1417                )
1418
1419     pos = __getitem__
1420
1421     def bbox(self):
1422         return bbox.bbox(min(self.x0, self.x1, self.x2, self.x3),
1423                          min(self.y0, self.y1, self.y2, self.y3),
1424                          max(self.x0, self.x1, self.x2, self.x3),
1425                          max(self.y0, self.y1, self.y2, self.y3))
1426
1427     def transform(self, trafo):
1428         return _bcurve(*(trafo._apply(self.x0, self.y0)+
1429                          trafo._apply(self.x1, self.y1)+
1430                          trafo._apply(self.x2, self.y2)+
1431                          trafo._apply(self.x3, self.y3)))
1432
1433     def reverse(self):
1434         return _bcurve(self.x3, self.y3,
1435                        self.x2, self.y2,
1436                        self.x1, self.y1,
1437                        self.x0, self.y0)
1438
1439     def isStraight(self, epsilon=1e-5):
1440         """check wheter the _bcurve is approximately straight"""
1441
1442         # just check, whether the modulus of the difference between
1443         # the length of the control polygon
1444         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1445         # straight line between starting and ending point of the
1446         # _bcurve (i.e. |P3-P1|) is smaller the epsilon
1447         return abs(math.sqrt((self.x1-self.x0)*(self.x1-self.x0)+
1448                              (self.y1-self.y0)*(self.y1-self.y0)) +
1449                    math.sqrt((self.x2-self.x1)*(self.x2-self.x1)+
1450                              (self.y2-self.y1)*(self.y2-self.y1)) +
1451                    math.sqrt((self.x3-self.x2)*(self.x3-self.x2)+
1452                              (self.y3-self.y2)*(self.y3-self.y2)) -
1453                    math.sqrt((self.x3-self.x0)*(self.x3-self.x0)+
1454                              (self.y3-self.y0)*(self.y3-self.y0)))<epsilon
1455
1456     def split(self, t):
1457         """return tuple consisting of two _bcurves corresponding to split at 0<=t<=1"""
1458
1459         # first, we calculate the coefficients corresponding to our
1460         # original bezier curve. These represent a useful starting
1461         # point for the following change of the polynomial parameter
1462         a0x = self.x0
1463         a0y = self.y0
1464         a1x = 3*(-self.x0+self.x1)
1465         a1y = 3*(-self.y0+self.y1)
1466         a2x = 3*(self.x0-2*self.x1+self.x2)
1467         a2y = 3*(self.y0-2*self.y1+self.y2)
1468         a3x = -self.x0+3*(self.x1-self.x2)+self.x3
1469         a3y = -self.y0+3*(self.y1-self.y2)+self.y3
1470
1471         # [0,t] part
1472         #
1473         # the new coefficients of the [0,t] part of the bezier curve
1474         # are then given by a0, a0*t, a0*t**2, a0*t**3
1475         # from this values we obtain the new control points by inversion
1476         x0_1 = a0x
1477         y0_1 = a0y
1478         x1_1 = a1x*t/3.0+x0_1
1479         y1_1 = a1y*t/3.0+y0_1
1480         x2_1 = a2x*t*t/3.0-x0_1+2*x1_1
1481         y2_1 = a2y*t*t/3.0-y0_1+2*y1_1
1482         x3_1 = a3x*t*t*t+x0_1-3*x1_1+3*x2_1
1483         y3_1 = a3y*t*t*t+y0_1-3*y1_1+3*y2_1
1484
1485         # [t,1] part
1486         #
1487         # the new coefficients of the [0,t] part of the bezier curve
1488         # are then given by expanding a0+a1*(t+(1-t)*u)+a2*(t+(1-t)*u)**2+
1489         # a3*(t+(1-t)*u)**3 in u, yielding:
1490         #   a0+a1*t+a2*t**2+a3*t**3             +
1491         #   (a1*+2*a2*t+3*a3*t**2)*(1-t) * u    +
1492         #   (a2+3*a3*t)*(1-t)**2         * u**2 +
1493         #   a3*(1-t)**3                  * u**3
1494         #
1495         # from this values we obtain the new control points by inversion
1496         # exactly like above, except that we don't have to calculate
1497         # the first and the last control point
1498         x0_2 = x3_1
1499         y0_2 = y3_1
1500         x1_2 = (a1x+2*a2x*t+3*a3x*t*t)*(1-t)/3.0+x0_2
1501         y1_2 = (a1y+2*a2y*t+3*a3y*t*t)*(1-t)/3.0+y0_2
1502         x2_2 = (a2x+3*a3x*t)*(1-t)*(1-t)/3.0-x0_2+2*x1_2
1503         y2_2 = (a2y+3*a3y*t)*(1-t)*(1-t)/3.0-y0_2+2*y1_2
1504         x3_2 = self.x3
1505         y3_2 = self.y3
1506
1507         return (_bcurve(x0_1, y0_1,
1508                         x1_1, y1_1,
1509                         x2_1, y2_1,
1510                         x3_1, y3_1),
1511                 _bcurve(x0_2, y0_2,
1512                         x1_2, y1_2,
1513                         x2_2, y2_2,
1514                         x3_2, y3_2))
1515
1516
1517     def MidPointSplit(self):
1518         """splits bpathel at midpoint returning bpath with two bpathels"""
1519
1520         # for efficiency reason, we do not use self.split(0.5)!
1521
1522         # first, we have to calculate the  midpoints between adjacent
1523         # control points
1524         x01 = 0.5*(self.x0+self.x1)
1525         y01 = 0.5*(self.y0+self.y1)
1526         x12 = 0.5*(self.x1+self.x2)
1527         y12 = 0.5*(self.y1+self.y2)
1528         x23 = 0.5*(self.x2+self.x3)
1529         y23 = 0.5*(self.y2+self.y3)
1530
1531         # In the next iterative step, we need the midpoints between 01 and 12
1532         # and between 12 and 23
1533         x01_12 = 0.5*(x01+x12)
1534         y01_12 = 0.5*(y01+y12)
1535         x12_23 = 0.5*(x12+x23)
1536         y12_23 = 0.5*(y12+y23)
1537
1538         # Finally the midpoint is given by
1539         xmidpoint = 0.5*(x01_12+x12_23)
1540         ymidpoint = 0.5*(y01_12+y12_23)
1541
1542         return (_bcurve(self.x0, self.y0,
1543                         x01, y01,
1544                         x01_12, y01_12,
1545                         xmidpoint, ymidpoint),
1546                 _bcurve(xmidpoint, ymidpoint,
1547                         x12_23, y12_23,
1548                         x23, y23,
1549                         self.x3, self.y3))
1550
1551     def arclength(self, epsilon=1e-5):
1552         """computes arclength of bpathel using successive midpoint split"""
1553
1554         if self.isStraight(epsilon):
1555             return unit.t_pt(math.sqrt((self.x3-self.x0)*(self.x3-self.x0)+
1556                                        (self.y3-self.y0)*(self.y3-self.y0)))
1557         else:
1558             (a, b) = self.MidPointSplit()
1559             return a.arclength()+b.arclength()
1560
1561 #
1562 # _bline: Bezier curve segment corresponding to straight line (coordinates in pts)
1563 #
1564
1565 class _bline(_bcurve):
1566
1567     """_bcurve corresponding to straight line (coordiates in pts)"""
1568
1569     def __init__(self, x0, y0, x1, y1):
1570         xa = x0+(x1-x0)/3.0
1571         ya = y0+(y1-y0)/3.0
1572         xb = x0+2.0*(x1-x0)/3.0
1573         yb = y0+2.0*(y1-y0)/3.0
1574
1575         _bcurve.__init__(self, x0, y0, xa, ya, xb, yb, x1, y1)
1576
1577 ################################################################################
1578 # Bezier helper functions
1579 ################################################################################
1580
1581 def _arctobcurve(x, y, r, phi1, phi2):
1582     """generate the best bpathel corresponding to an arc segment"""
1583
1584     dphi=phi2-phi1
1585
1586     if dphi==0: return None
1587
1588     # the two endpoints should be clear
1589     (x0, y0) = ( x+r*cos(phi1), y+r*sin(phi1) )
1590     (x3, y3) = ( x+r*cos(phi2), y+r*sin(phi2) )
1591
1592     # optimal relative distance along tangent for second and third
1593     # control point
1594     l = r*4*(1-cos(dphi/2))/(3*sin(dphi/2))
1595
1596     (x1, y1) = ( x0-l*sin(phi1), y0+l*cos(phi1) )
1597     (x2, y2) = ( x3+l*sin(phi2), y3-l*cos(phi2) )
1598
1599     return _bcurve(x0, y0, x1, y1, x2, y2, x3, y3)
1600
1601
1602 def _arctobezierpath(x, y, r, phi1, phi2, dphimax=45):
1603     path = []
1604
1605     phi1 = phi1*pi/180
1606     phi2 = phi2*pi/180
1607     dphimax = dphimax*pi/180
1608
1609     if phi2<phi1:
1610         # guarantee that phi2>phi1 ...
1611         phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
1612     elif phi2>phi1+2*pi:
1613         # ... or remove unnecessary multiples of 2*pi
1614         phi2 = phi2 - (math.floor((phi2-phi1)/(2*pi))-1)*2*pi
1615
1616     if r==0 or phi1-phi2==0: return []
1617
1618     subdivisions = abs(int((1.0*(phi1-phi2))/dphimax))+1
1619
1620     dphi=(1.0*(phi2-phi1))/subdivisions
1621
1622     for i in range(subdivisions):
1623         path.append(_arctobcurve(x, y, r, phi1+i*dphi, phi1+(i+1)*dphi))
1624
1625     return path
1626
1627
1628 def _bcurveIntersect(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
1629     """intersect two bpathels
1630
1631     a and b are bpathels with parameter ranges [a_t0, a_t1],
1632     respectively [b_t0, b_t1].
1633     epsilon determines when the bpathels are assumed to be straight
1634
1635     """
1636
1637     # intersection of bboxes is a necessary criterium for intersection
1638     if not a.bbox().intersects(b.bbox()): return ()
1639
1640     if not a.isStraight(epsilon):
1641         (aa, ab) = a.MidPointSplit()
1642         a_tm = 0.5*(a_t0+a_t1)
1643
1644         if not b.isStraight(epsilon):
1645             (ba, bb) = b.MidPointSplit()
1646             b_tm = 0.5*(b_t0+b_t1)
1647
1648             return ( _bcurveIntersect(aa, a_t0, a_tm,
1649                                        ba, b_t0, b_tm, epsilon) +
1650                      _bcurveIntersect(ab, a_tm, a_t1,
1651                                        ba, b_t0, b_tm, epsilon) +
1652                      _bcurveIntersect(aa, a_t0, a_tm,
1653                                        bb, b_tm, b_t1, epsilon) +
1654                      _bcurveIntersect(ab, a_tm, a_t1,
1655                                        bb, b_tm, b_t1, epsilon) )
1656         else:
1657             return ( _bcurveIntersect(aa, a_t0, a_tm,
1658                                        b, b_t0, b_t1, epsilon) +
1659                      _bcurveIntersect(ab, a_tm, a_t1,
1660                                        b, b_t0, b_t1, epsilon) )
1661     else:
1662         if not b.isStraight(epsilon):
1663             (ba, bb) = b.MidPointSplit()
1664             b_tm = 0.5*(b_t0+b_t1)
1665
1666             return  ( _bcurveIntersect(a, a_t0, a_t1,
1667                                         ba, b_t0, b_tm, epsilon) +
1668                       _bcurveIntersect(a, a_t0, a_t1,
1669                                         ba, b_tm, b_t1, epsilon) )
1670         else:
1671             # no more subdivisions of either a or b
1672             # => try to intersect a and b as straight line segments
1673
1674             a_deltax = a.x3 - a.x0
1675             a_deltay = a.y3 - a.y0
1676             b_deltax = b.x3 - b.x0
1677             b_deltay = b.y3 - b.y0
1678
1679             det = b_deltax*a_deltay - b_deltay*a_deltax
1680
1681             # check for parallel lines
1682             if 1.0+det==1.0: return ()
1683
1684             ba_deltax0 = b.x0 - a.x0
1685             ba_deltay0 = b.y0 - a.y0
1686
1687             a_t = ( b_deltax*ba_deltay0 - b_deltay*ba_deltax0)/det
1688             b_t = ( a_deltax*ba_deltay0 - a_deltay*ba_deltax0)/det
1689
1690             # check for intersections out of bound
1691             if not ( 0<=a_t<=1 and 0<=b_t<=1): return ()
1692
1693             # return rescaled parameters of the intersection
1694             return ( ( a_t0 + a_t * (a_t1 - a_t0),
1695                        b_t0 + b_t * (b_t1 - b_t0) ),
1696                    )