pyx/path.py

   1 #!/usr/bin/env python
   2 # -*- coding: ISO-8859-1 -*-
   3 #
   4 #
   5 # Copyright (C) 2002-2004 Jörg Lehmann <joergl@users.sourceforge.net>
   6 # Copyright (C) 2003-2004 Michael Schindler <m-schindler@users.sourceforge.net>
   7 # Copyright (C) 2002-2004 André Wobst <wobsta@users.sourceforge.net>
   8 #
   9 # This file is part of PyX (http://pyx.sourceforge.net/).
  10 #
  11 # PyX is free software; you can redistribute it and/or modify
  12 # it under the terms of the GNU General Public License as published by
  13 # the Free Software Foundation; either version 2 of the License, or
  14 # (at your option) any later version.
  15 #
  16 # PyX is distributed in the hope that it will be useful,
  17 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 # GNU General Public License for more details.
  20 #
  21 # You should have received a copy of the GNU General Public License
  22 # along with PyX; if not, write to the Free Software
  23 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24
  25 #       - exceptions: nocurrentpoint, paramrange
  26 #       - correct bbox for curveto and normcurve
  27 #         (maybe we still need the current bbox implementation (then maybe called
  28 #          cbox = control box) for normcurve for the use during the
  29 #          intersection of bpaths)
  30
  31 import math, bisect
  32 from math import cos, sin, pi
  33 try:
  34     from math import radians, degrees
  35 except ImportError:
  36     # fallback implementation for Python 2.1 and below
  37     def radians(x): return x*pi/180
  38     def degrees(x): return x*180/pi
  39 import base, bbox, trafo, unit, helper
  40
  41 try:
  42     sum([])
  43 except NameError:
  44     # fallback implementation for Python 2.2. and below
  45     def sum(list):
  46         return reduce(lambda x, y: x+y, list, 0)
  47
  48 try:
  49     enumerate([])
  50 except NameError:
  51     # fallback implementation for Python 2.2. and below
  52     def enumerate(list):
  53         return zip(xrange(len(list)), list)
  54
  55 # use new style classes when possible
  56 __metaclass__ = type
  57
  58 ################################################################################
  59 # Bezier helper functions
  60 ################################################################################
  61
  62 def _arctobcurve(x_pt, y_pt, r_pt, phi1, phi2):
  63     """generate the best bezier curve corresponding to an arc segment"""
  64
  65     dphi = phi2-phi1
  66
  67     if dphi==0: return None
  68
  69     # the two endpoints should be clear
  70     x0_pt, y0_pt = x_pt+r_pt*cos(phi1), y_pt+r_pt*sin(phi1)
  71     x3_pt, y3_pt = x_pt+r_pt*cos(phi2), y_pt+r_pt*sin(phi2)
  72
  73     # optimal relative distance along tangent for second and third
  74     # control point
  75     l = r_pt*4*(1-cos(dphi/2))/(3*sin(dphi/2))
  76
  77     x1_pt, y1_pt = x0_pt-l*sin(phi1), y0_pt+l*cos(phi1)
  78     x2_pt, y2_pt = x3_pt+l*sin(phi2), y3_pt-l*cos(phi2)
  79
  80     return normcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt)
  81
  82
  83 def _arctobezierpath(x_pt, y_pt, r_pt, phi1, phi2, dphimax=45):
  84     apath = []
  85
  86     phi1 = radians(phi1)
  87     phi2 = radians(phi2)
  88     dphimax = radians(dphimax)
  89
  90     if phi2<phi1:
  91         # guarantee that phi2>phi1 ...
  92         phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
  93     elif phi2>phi1+2*pi:
  94         # ... or remove unnecessary multiples of 2*pi
  95         phi2 = phi2 - (math.floor((phi2-phi1)/(2*pi))-1)*2*pi
  96
  97     if r_pt == 0 or phi1-phi2 == 0: return []
  98
  99     subdivisions = abs(int((1.0*(phi1-phi2))/dphimax))+1
 100
 101     dphi = (1.0*(phi2-phi1))/subdivisions
 102
 103     for i in range(subdivisions):
 104         apath.append(_arctobcurve(x_pt, y_pt, r_pt, phi1+i*dphi, phi1+(i+1)*dphi))
 105
 106     return apath
 107
 108 #
 109 # we define one exception
 110 #
 111
 112 class PathException(Exception): pass
 113
 114 ################################################################################
 115 # _pathcontext: context during walk along path
 116 ################################################################################
 117
 118 class _pathcontext:
 119
 120     """context during walk along path"""
 121
 122     __slots__ = "currentpoint", "currentsubpath"
 123
 124     def __init__(self, currentpoint=None, currentsubpath=None):
 125         """ initialize context
 126
 127         currentpoint:   position of current point
 128         currentsubpath: position of first point of current subpath
 129
 130         """
 131
 132         self.currentpoint = currentpoint
 133         self.currentsubpath = currentsubpath
 134
 135 ################################################################################
 136 # pathitem: element of a PS style path
 137 ################################################################################
 138
 139 class pathitem(base.canvasitem):
 140
 141     """element of a PS style path"""
 142
 143     def _updatecontext(self, context):
 144         """update context of during walk along pathitem
 145
 146         changes context in place
 147         """
 148         pass
 149
 150
 151     def _bbox(self, context):
 152         """calculate bounding box of pathitem
 153
 154         context: context of pathitem
 155
 156         returns bounding box of pathitem (in given context)
 157
 158         Important note: all coordinates in bbox, currentpoint, and
 159         currrentsubpath have to be floats (in unit.topt)
 160
 161         """
 162         pass
 163
 164     def _normalized(self, context):
 165         """returns list of normalized version of pathitem
 166
 167         context: context of pathitem
 168
 169         Returns the path converted into a list of closepath, moveto_pt,
 170         normline, or normcurve instances.
 171
 172         """
 173         pass
 174
 175     def outputPS(self, file):
 176         """write PS code corresponding to pathitem to file"""
 177         pass
 178
 179     def outputPDF(self, file):
 180         """write PDF code corresponding to pathitem to file"""
 181         pass
 182
 183 #
 184 # various pathitems
 185 #
 186 # Each one comes in two variants:
 187 #  - one which requires the coordinates to be already in pts (mainly
 188 #    used for internal purposes)
 189 #  - another which accepts arbitrary units
 190
 191 class closepath(pathitem):
 192
 193     """Connect subpath back to its starting point"""
 194
 195     __slots__ = ()
 196
 197     def __str__(self):
 198         return "closepath"
 199
 200     def _updatecontext(self, context):
 201         context.currentpoint = None
 202         context.currentsubpath = None
 203
 204     def _bbox(self, context):
 205         x0_pt, y0_pt = context.currentpoint
 206         x1_pt, y1_pt = context.currentsubpath
 207
 208         return bbox.bbox_pt(min(x0_pt, x1_pt), min(y0_pt, y1_pt),
 209                           max(x0_pt, x1_pt), max(y0_pt, y1_pt))
 210
 211     def _normalized(self, context):
 212         return [closepath()]
 213
 214     def outputPS(self, file):
 215         file.write("closepath\n")
 216
 217     def outputPDF(self, file):
 218         file.write("h\n")
 219
 220
 221 class moveto_pt(pathitem):
 222
 223     """Set current point to (x_pt, y_pt) (coordinates in pts)"""
 224
 225     __slots__ = "x_pt", "y_pt"
 226
 227     def __init__(self, x_pt, y_pt):
 228          self.x_pt = x_pt
 229          self.y_pt = y_pt
 230
 231     def __str__(self):
 232         return "%g %g moveto" % (self.x_pt, self.y_pt)
 233
 234     def _updatecontext(self, context):
 235         context.currentpoint = self.x_pt, self.y_pt
 236         context.currentsubpath = self.x_pt, self.y_pt
 237
 238     def _bbox(self, context):
 239         return None
 240
 241     def _normalized(self, context):
 242         return [moveto_pt(self.x_pt, self.y_pt)]
 243
 244     def outputPS(self, file):
 245         file.write("%g %g moveto\n" % (self.x_pt, self.y_pt) )
 246
 247     def outputPDF(self, file):
 248         file.write("%f %f m\n" % (self.x_pt, self.y_pt) )
 249
 250
 251 class lineto_pt(pathitem):
 252
 253     """Append straight line to (x_pt, y_pt) (coordinates in pts)"""
 254
 255     __slots__ = "x_pt", "y_pt"
 256
 257     def __init__(self, x_pt, y_pt):
 258          self.x_pt = x_pt
 259          self.y_pt = y_pt
 260
 261     def __str__(self):
 262         return "%g %g lineto" % (self.x_pt, self.y_pt)
 263
 264     def _updatecontext(self, context):
 265         context.currentsubpath = context.currentsubpath or context.currentpoint
 266         context.currentpoint = self.x_pt, self.y_pt
 267
 268     def _bbox(self, context):
 269         return bbox.bbox_pt(min(context.currentpoint[0], self.x_pt),
 270                           min(context.currentpoint[1], self.y_pt),
 271                           max(context.currentpoint[0], self.x_pt),
 272                           max(context.currentpoint[1], self.y_pt))
 273
 274     def _normalized(self, context):
 275         return [normline(context.currentpoint[0], context.currentpoint[1], self.x_pt, self.y_pt)]
 276
 277     def outputPS(self, file):
 278         file.write("%g %g lineto\n" % (self.x_pt, self.y_pt) )
 279
 280     def outputPDF(self, file):
 281         file.write("%f %f l\n" % (self.x_pt, self.y_pt) )
 282
 283
 284 class curveto_pt(pathitem):
 285
 286     """Append curveto (coordinates in pts)"""
 287
 288     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
 289
 290     def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
 291         self.x1_pt = x1_pt
 292         self.y1_pt = y1_pt
 293         self.x2_pt = x2_pt
 294         self.y2_pt = y2_pt
 295         self.x3_pt = x3_pt
 296         self.y3_pt = y3_pt
 297
 298     def __str__(self):
 299         return "%g %g %g %g %g %g curveto" % (self.x1_pt, self.y1_pt,
 300                                               self.x2_pt, self.y2_pt,
 301                                               self.x3_pt, self.y3_pt)
 302
 303     def _updatecontext(self, context):
 304         context.currentsubpath = context.currentsubpath or context.currentpoint
 305         context.currentpoint = self.x3_pt, self.y3_pt
 306
 307     def _bbox(self, context):
 308         return bbox.bbox_pt(min(context.currentpoint[0], self.x1_pt, self.x2_pt, self.x3_pt),
 309                           min(context.currentpoint[1], self.y1_pt, self.y2_pt, self.y3_pt),
 310                           max(context.currentpoint[0], self.x1_pt, self.x2_pt, self.x3_pt),
 311                           max(context.currentpoint[1], self.y1_pt, self.y2_pt, self.y3_pt))
 312
 313     def _normalized(self, context):
 314         return [normcurve(context.currentpoint[0], context.currentpoint[1],
 315                           self.x1_pt, self.y1_pt,
 316                           self.x2_pt, self.y2_pt,
 317                           self.x3_pt, self.y3_pt)]
 318
 319     def outputPS(self, file):
 320         file.write("%g %g %g %g %g %g curveto\n" % ( self.x1_pt, self.y1_pt,
 321                                                      self.x2_pt, self.y2_pt,
 322                                                      self.x3_pt, self.y3_pt ) )
 323
 324     def outputPDF(self, file):
 325         file.write("%f %f %f %f %f %f c\n" % ( self.x1_pt, self.y1_pt,
 326                                                self.x2_pt, self.y2_pt,
 327                                                self.x3_pt, self.y3_pt ) )
 328
 329
 330 class rmoveto_pt(pathitem):
 331
 332     """Perform relative moveto (coordinates in pts)"""
 333
 334     __slots__ = "dx_pt", "dy_pt"
 335
 336     def __init__(self, dx_pt, dy_pt):
 337          self.dx_pt = dx_pt
 338          self.dy_pt = dy_pt
 339
 340     def _updatecontext(self, context):
 341         context.currentpoint = (context.currentpoint[0] + self.dx_pt,
 342                                 context.currentpoint[1] + self.dy_pt)
 343         context.currentsubpath = context.currentpoint
 344
 345     def _bbox(self, context):
 346         return None
 347
 348     def _normalized(self, context):
 349         x_pt = context.currentpoint[0]+self.dx_pt
 350         y_pt = context.currentpoint[1]+self.dy_pt
 351         return [moveto_pt(x_pt, y_pt)]
 352
 353     def outputPS(self, file):
 354         file.write("%g %g rmoveto\n" % (self.dx_pt, self.dy_pt) )
 355
 356
 357 class rlineto_pt(pathitem):
 358
 359     """Perform relative lineto (coordinates in pts)"""
 360
 361     __slots__ = "dx_pt", "dy_pt"
 362
 363     def __init__(self, dx_pt, dy_pt):
 364          self.dx_pt = dx_pt
 365          self.dy_pt = dy_pt
 366
 367     def _updatecontext(self, context):
 368         context.currentsubpath = context.currentsubpath or context.currentpoint
 369         context.currentpoint = (context.currentpoint[0]+self.dx_pt,
 370                                 context.currentpoint[1]+self.dy_pt)
 371
 372     def _bbox(self, context):
 373         x = context.currentpoint[0] + self.dx_pt
 374         y = context.currentpoint[1] + self.dy_pt
 375         return bbox.bbox_pt(min(context.currentpoint[0], x),
 376                           min(context.currentpoint[1], y),
 377                           max(context.currentpoint[0], x),
 378                           max(context.currentpoint[1], y))
 379
 380     def _normalized(self, context):
 381         x0_pt = context.currentpoint[0]
 382         y0_pt = context.currentpoint[1]
 383         return [normline(x0_pt, y0_pt, x0_pt+self.dx_pt, y0_pt+self.dy_pt)]
 384
 385     def outputPS(self, file):
 386         file.write("%g %g rlineto\n" % (self.dx_pt, self.dy_pt) )
 387
 388
 389 class rcurveto_pt(pathitem):
 390
 391     """Append rcurveto (coordinates in pts)"""
 392
 393     __slots__ = "dx1_pt", "dy1_pt", "dx2_pt", "dy2_pt", "dx3_pt", "dy3_pt"
 394
 395     def __init__(self, dx1_pt, dy1_pt, dx2_pt, dy2_pt, dx3_pt, dy3_pt):
 396         self.dx1_pt = dx1_pt
 397         self.dy1_pt = dy1_pt
 398         self.dx2_pt = dx2_pt
 399         self.dy2_pt = dy2_pt
 400         self.dx3_pt = dx3_pt
 401         self.dy3_pt = dy3_pt
 402
 403     def outputPS(self, file):
 404         file.write("%g %g %g %g %g %g rcurveto\n" % ( self.dx1_pt, self.dy1_pt,
 405                                                     self.dx2_pt, self.dy2_pt,
 406                                                     self.dx3_pt, self.dy3_pt ) )
 407
 408     def _updatecontext(self, context):
 409         x3_pt = context.currentpoint[0]+self.dx3_pt
 410         y3_pt = context.currentpoint[1]+self.dy3_pt
 411
 412         context.currentsubpath = context.currentsubpath or context.currentpoint
 413         context.currentpoint = x3_pt, y3_pt
 414
 415
 416     def _bbox(self, context):
 417         x1_pt = context.currentpoint[0]+self.dx1_pt
 418         y1_pt = context.currentpoint[1]+self.dy1_pt
 419         x2_pt = context.currentpoint[0]+self.dx2_pt
 420         y2_pt = context.currentpoint[1]+self.dy2_pt
 421         x3_pt = context.currentpoint[0]+self.dx3_pt
 422         y3_pt = context.currentpoint[1]+self.dy3_pt
 423         return bbox.bbox_pt(min(context.currentpoint[0], x1_pt, x2_pt, x3_pt),
 424                           min(context.currentpoint[1], y1_pt, y2_pt, y3_pt),
 425                           max(context.currentpoint[0], x1_pt, x2_pt, x3_pt),
 426                           max(context.currentpoint[1], y1_pt, y2_pt, y3_pt))
 427
 428     def _normalized(self, context):
 429         x0_pt = context.currentpoint[0]
 430         y0_pt = context.currentpoint[1]
 431         return [normcurve(x0_pt, y0_pt, x0_pt+self.dx1_pt, y0_pt+self.dy1_pt, x0_pt+self.dx2_pt, y0_pt+self.dy2_pt, x0_pt+self.dx3_pt, y0_pt+self.dy3_pt)]
 432
 433
 434 class arc_pt(pathitem):
 435
 436     """Append counterclockwise arc (coordinates in pts)"""
 437
 438     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 439
 440     def __init__(self, x_pt, y_pt, r_pt, angle1, angle2):
 441         self.x_pt = x_pt
 442         self.y_pt = y_pt
 443         self.r_pt = r_pt
 444         self.angle1 = angle1
 445         self.angle2 = angle2
 446
 447     def _sarc(self):
 448         """Return starting point of arc segment"""
 449         return (self.x_pt+self.r_pt*cos(radians(self.angle1)),
 450                 self.y_pt+self.r_pt*sin(radians(self.angle1)))
 451
 452     def _earc(self):
 453         """Return end point of arc segment"""
 454         return (self.x_pt+self.r_pt*cos(radians(self.angle2)),
 455                 self.y_pt+self.r_pt*sin(radians(self.angle2)))
 456
 457     def _updatecontext(self, context):
 458         if context.currentpoint:
 459             context.currentsubpath = context.currentsubpath or context.currentpoint
 460         else:
 461             # we assert that currentsubpath is also None
 462             context.currentsubpath = self._sarc()
 463
 464         context.currentpoint = self._earc()
 465
 466     def _bbox(self, context):
 467         phi1 = radians(self.angle1)
 468         phi2 = radians(self.angle2)
 469
 470         # starting end end point of arc segment
 471         sarcx_pt, sarcy_pt = self._sarc()
 472         earcx_pt, earcy_pt = self._earc()
 473
 474         # Now, we have to determine the corners of the bbox for the
 475         # arc segment, i.e. global maxima/mimima of cos(phi) and sin(phi)
 476         # in the interval [phi1, phi2]. These can either be located
 477         # on the borders of this interval or in the interior.
 478
 479         if phi2 < phi1:
 480             # guarantee that phi2>phi1
 481             phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
 482
 483         # next minimum of cos(phi) looking from phi1 in counterclockwise
 484         # direction: 2*pi*floor((phi1-pi)/(2*pi)) + 3*pi
 485
 486         if phi2 < (2*math.floor((phi1-pi)/(2*pi))+3)*pi:
 487             minarcx_pt = min(sarcx_pt, earcx_pt)
 488         else:
 489             minarcx_pt = self.x_pt-self.r_pt
 490
 491         # next minimum of sin(phi) looking from phi1 in counterclockwise
 492         # direction: 2*pi*floor((phi1-3*pi/2)/(2*pi)) + 7/2*pi
 493
 494         if phi2 < (2*math.floor((phi1-3.0*pi/2)/(2*pi))+7.0/2)*pi:
 495             minarcy_pt = min(sarcy_pt, earcy_pt)
 496         else:
 497             minarcy_pt = self.y_pt-self.r_pt
 498
 499         # next maximum of cos(phi) looking from phi1 in counterclockwise
 500         # direction: 2*pi*floor((phi1)/(2*pi))+2*pi
 501
 502         if phi2 < (2*math.floor((phi1)/(2*pi))+2)*pi:
 503             maxarcx_pt = max(sarcx_pt, earcx_pt)
 504         else:
 505             maxarcx_pt = self.x_pt+self.r_pt
 506
 507         # next maximum of sin(phi) looking from phi1 in counterclockwise
 508         # direction: 2*pi*floor((phi1-pi/2)/(2*pi)) + 1/2*pi
 509
 510         if phi2 < (2*math.floor((phi1-pi/2)/(2*pi))+5.0/2)*pi:
 511             maxarcy_pt = max(sarcy_pt, earcy_pt)
 512         else:
 513             maxarcy_pt = self.y_pt+self.r_pt
 514
 515         # Finally, we are able to construct the bbox for the arc segment.
 516         # Note that if there is a currentpoint defined, we also
 517         # have to include the straight line from this point
 518         # to the first point of the arc segment
 519
 520         if context.currentpoint:
 521             return (bbox.bbox_pt(min(context.currentpoint[0], sarcx_pt),
 522                                min(context.currentpoint[1], sarcy_pt),
 523                                max(context.currentpoint[0], sarcx_pt),
 524                                max(context.currentpoint[1], sarcy_pt)) +
 525                     bbox.bbox_pt(minarcx_pt, minarcy_pt, maxarcx_pt, maxarcy_pt)
 526                     )
 527         else:
 528             return  bbox.bbox_pt(minarcx_pt, minarcy_pt, maxarcx_pt, maxarcy_pt)
 529
 530     def _normalized(self, context):
 531         # get starting and end point of arc segment and bpath corresponding to arc
 532         sarcx_pt, sarcy_pt = self._sarc()
 533         earcx_pt, earcy_pt = self._earc()
 534         barc = _arctobezierpath(self.x_pt, self.y_pt, self.r_pt, self.angle1, self.angle2)
 535
 536         # convert to list of curvetos omitting movetos
 537         nbarc = []
 538
 539         for bpathitem in barc:
 540             nbarc.append(normcurve(bpathitem.x0_pt, bpathitem.y0_pt,
 541                                    bpathitem.x1_pt, bpathitem.y1_pt,
 542                                    bpathitem.x2_pt, bpathitem.y2_pt,
 543                                    bpathitem.x3_pt, bpathitem.y3_pt))
 544
 545         # Note that if there is a currentpoint defined, we also
 546         # have to include the straight line from this point
 547         # to the first point of the arc segment.
 548         # Otherwise, we have to add a moveto at the beginning
 549         if context.currentpoint:
 550             return [normline(context.currentpoint[0], context.currentpoint[1], sarcx_pt, sarcy_pt)] + nbarc
 551         else:
 552             return [moveto_pt(sarcx_pt, sarcy_pt)] + nbarc
 553
 554     def outputPS(self, file):
 555         file.write("%g %g %g %g %g arc\n" % ( self.x_pt, self.y_pt,
 556                                             self.r_pt,
 557                                             self.angle1,
 558                                             self.angle2 ) )
 559
 560
 561 class arcn_pt(pathitem):
 562
 563     """Append clockwise arc (coordinates in pts)"""
 564
 565     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 566
 567     def __init__(self, x_pt, y_pt, r_pt, angle1, angle2):
 568         self.x_pt = x_pt
 569         self.y_pt = y_pt
 570         self.r_pt = r_pt
 571         self.angle1 = angle1
 572         self.angle2 = angle2
 573
 574     def _sarc(self):
 575         """Return starting point of arc segment"""
 576         return (self.x_pt+self.r_pt*cos(radians(self.angle1)),
 577                 self.y_pt+self.r_pt*sin(radians(self.angle1)))
 578
 579     def _earc(self):
 580         """Return end point of arc segment"""
 581         return (self.x_pt+self.r_pt*cos(radians(self.angle2)),
 582                 self.y_pt+self.r_pt*sin(radians(self.angle2)))
 583
 584     def _updatecontext(self, context):
 585         if context.currentpoint:
 586             context.currentsubpath = context.currentsubpath or context.currentpoint
 587         else:  # we assert that currentsubpath is also None
 588             context.currentsubpath = self._sarc()
 589
 590         context.currentpoint = self._earc()
 591
 592     def _bbox(self, context):
 593         # in principle, we obtain bbox of an arcn element from
 594         # the bounding box of the corrsponding arc element with
 595         # angle1 and angle2 interchanged. Though, we have to be carefull
 596         # with the straight line segment, which is added if currentpoint
 597         # is defined.
 598
 599         # Hence, we first compute the bbox of the arc without this line:
 600
 601         a = arc_pt(self.x_pt, self.y_pt, self.r_pt,
 602                  self.angle2,
 603                  self.angle1)
 604
 605         sarcx_pt, sarcy_pt = self._sarc()
 606         arcbb = a._bbox(_pathcontext())
 607
 608         # Then, we repeat the logic from arc.bbox, but with interchanged
 609         # start and end points of the arc
 610
 611         if context.currentpoint:
 612             return  bbox.bbox_pt(min(context.currentpoint[0], sarcx_pt),
 613                                min(context.currentpoint[1], sarcy_pt),
 614                                max(context.currentpoint[0], sarcx_pt),
 615                                max(context.currentpoint[1], sarcy_pt))+ arcbb
 616         else:
 617             return arcbb
 618
 619     def _normalized(self, context):
 620         # get starting and end point of arc segment and bpath corresponding to arc
 621         sarcx_pt, sarcy_pt = self._sarc()
 622         earcx_pt, earcy_pt = self._earc()
 623         barc = _arctobezierpath(self.x_pt, self.y_pt, self.r_pt, self.angle2, self.angle1)
 624         barc.reverse()
 625
 626         # convert to list of curvetos omitting movetos
 627         nbarc = []
 628
 629         for bpathitem in barc:
 630             nbarc.append(normcurve(bpathitem.x3_pt, bpathitem.y3_pt,
 631                                    bpathitem.x2_pt, bpathitem.y2_pt,
 632                                    bpathitem.x1_pt, bpathitem.y1_pt,
 633                                    bpathitem.x0_pt, bpathitem.y0_pt))
 634
 635         # Note that if there is a currentpoint defined, we also
 636         # have to include the straight line from this point
 637         # to the first point of the arc segment.
 638         # Otherwise, we have to add a moveto at the beginning
 639         if context.currentpoint:
 640             return [normline(context.currentpoint[0], context.currentpoint[1], sarcx_pt, sarcy_pt)] + nbarc
 641         else:
 642             return [moveto_pt(sarcx_pt, sarcy_pt)] + nbarc
 643
 644
 645     def outputPS(self, file):
 646         file.write("%g %g %g %g %g arcn\n" % ( self.x_pt, self.y_pt,
 647                                                self.r_pt,
 648                                                self.angle1,
 649                                                self.angle2 ) )
 650
 651
 652 class arct_pt(pathitem):
 653
 654     """Append tangent arc (coordinates in pts)"""
 655
 656     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "r_pt"
 657
 658     def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt, r_pt):
 659         self.x1_pt = x1_pt
 660         self.y1_pt = y1_pt
 661         self.x2_pt = x2_pt
 662         self.y2_pt = y2_pt
 663         self.r_pt = r_pt
 664
 665     def _path(self, currentpoint, currentsubpath):
 666         """returns new currentpoint, currentsubpath and path consisting
 667         of arc and/or line which corresponds to arct
 668
 669         this is a helper routine for _bbox and _normalized, which both need
 670         this path. Note: we don't want to calculate the bbox from a bpath
 671
 672         """
 673
 674         # direction and length of tangent 1
 675         dx1_pt = currentpoint[0]-self.x1_pt
 676         dy1_pt = currentpoint[1]-self.y1_pt
 677         l1 = math.hypot(dx1_pt, dy1_pt)
 678
 679         # direction and length of tangent 2
 680         dx2_pt = self.x2_pt-self.x1_pt
 681         dy2_pt = self.y2_pt-self.y1_pt
 682         l2 = math.hypot(dx2_pt, dy2_pt)
 683
 684         # intersection angle between two tangents
 685         alpha = math.acos((dx1_pt*dx2_pt+dy1_pt*dy2_pt)/(l1*l2))
 686
 687         if math.fabs(sin(alpha)) >= 1e-15 and 1.0+self.r_pt != 1.0:
 688             cotalpha2 = 1.0/math.tan(alpha/2)
 689
 690             # two tangent points
 691             xt1_pt = self.x1_pt + dx1_pt*self.r_pt*cotalpha2/l1
 692             yt1_pt = self.y1_pt + dy1_pt*self.r_pt*cotalpha2/l1
 693             xt2_pt = self.x1_pt + dx2_pt*self.r_pt*cotalpha2/l2
 694             yt2_pt = self.y1_pt + dy2_pt*self.r_pt*cotalpha2/l2
 695
 696             # direction of center of arc
 697             rx_pt = self.x1_pt - 0.5*(xt1_pt+xt2_pt)
 698             ry_pt = self.y1_pt - 0.5*(yt1_pt+yt2_pt)
 699             lr = math.hypot(rx_pt, ry_pt)
 700
 701             # angle around which arc is centered
 702             if rx_pt >= 0:
 703                 phi = degrees(math.atan2(ry_pt, rx_pt))
 704             else:
 705                 # XXX why is rx_pt/ry_pt and not ry_pt/rx_pt used???
 706                 phi = degrees(math.atan(rx_pt/ry_pt))+180
 707
 708             # half angular width of arc
 709             deltaphi = 90*(1-alpha/pi)
 710
 711             # center position of arc
 712             mx_pt = self.x1_pt - rx_pt*self.r_pt/(lr*sin(alpha/2))
 713             my_pt = self.y1_pt - ry_pt*self.r_pt/(lr*sin(alpha/2))
 714
 715             # now we are in the position to construct the path
 716             p = path(moveto_pt(*currentpoint))
 717
 718             if phi<0:
 719                 p.append(arc_pt(mx_pt, my_pt, self.r_pt, phi-deltaphi, phi+deltaphi))
 720             else:
 721                 p.append(arcn_pt(mx_pt, my_pt, self.r_pt, phi+deltaphi, phi-deltaphi))
 722
 723             return ( (xt2_pt, yt2_pt),
 724                      currentsubpath or (xt2_pt, yt2_pt),
 725                      p )
 726
 727         else:
 728             # we need no arc, so just return a straight line to currentpoint to x1_pt, y1_pt
 729             return  ( (self.x1_pt, self.y1_pt),
 730                       currentsubpath or (self.x1_pt, self.y1_pt),
 731                       line_pt(currentpoint[0], currentpoint[1], self.x1_pt, self.y1_pt) )
 732
 733     def _updatecontext(self, context):
 734         result = self._path(context.currentpoint, context.currentsubpath)
 735         context.currentpoint, context.currentsubpath = result[:2]
 736
 737     def _bbox(self, context):
 738         return self._path(context.currentpoint, context.currentsubpath)[2].bbox()
 739
 740     def _normalized(self, context):
 741         # XXX TODO
 742         return normpath(self._path(context.currentpoint,
 743                                    context.currentsubpath)[2]).subpaths[0].normpathitems
 744     def outputPS(self, file):
 745         file.write("%g %g %g %g %g arct\n" % ( self.x1_pt, self.y1_pt,
 746                                                self.x2_pt, self.y2_pt,
 747                                                self.r_pt ) )
 748
 749 #
 750 # now the pathitems that convert from user coordinates to pts
 751 #
 752
 753 class moveto(moveto_pt):
 754
 755     """Set current point to (x, y)"""
 756
 757     __slots__ = "x_pt", "y_pt"
 758
 759     def __init__(self, x, y):
 760         moveto_pt.__init__(self, unit.topt(x), unit.topt(y))
 761
 762
 763 class lineto(lineto_pt):
 764
 765     """Append straight line to (x, y)"""
 766
 767     __slots__ = "x_pt", "y_pt"
 768
 769     def __init__(self, x, y):
 770         lineto_pt.__init__(self, unit.topt(x), unit.topt(y))
 771
 772
 773 class curveto(curveto_pt):
 774
 775     """Append curveto"""
 776
 777     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
 778
 779     def __init__(self, x1, y1, x2, y2, x3, y3):
 780         curveto_pt.__init__(self,
 781                             unit.topt(x1), unit.topt(y1),
 782                             unit.topt(x2), unit.topt(y2),
 783                             unit.topt(x3), unit.topt(y3))
 784
 785 class rmoveto(rmoveto_pt):
 786
 787     """Perform relative moveto"""
 788
 789     __slots__ = "dx_pt", "dy_pt"
 790
 791     def __init__(self, dx, dy):
 792         rmoveto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
 793
 794
 795 class rlineto(rlineto_pt):
 796
 797     """Perform relative lineto"""
 798
 799     __slots__ = "dx_pt", "dy_pt"
 800
 801     def __init__(self, dx, dy):
 802         rlineto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
 803
 804
 805 class rcurveto(rcurveto_pt):
 806
 807     """Append rcurveto"""
 808
 809     __slots__ = "dx1_pt", "dy1_pt", "dx2_pt", "dy2_pt", "dx3_pt", "dy3_pt"
 810
 811     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
 812         rcurveto_pt.__init__(self,
 813                              unit.topt(dx1), unit.topt(dy1),
 814                              unit.topt(dx2), unit.topt(dy2),
 815                              unit.topt(dx3), unit.topt(dy3))
 816
 817
 818 class arcn(arcn_pt):
 819
 820     """Append clockwise arc"""
 821
 822     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 823
 824     def __init__(self, x, y, r, angle1, angle2):
 825         arcn_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r), angle1, angle2)
 826
 827
 828 class arc(arc_pt):
 829
 830     """Append counterclockwise arc"""
 831
 832     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 833
 834     def __init__(self, x, y, r, angle1, angle2):
 835         arc_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r), angle1, angle2)
 836
 837
 838 class arct(arct_pt):
 839
 840     """Append tangent arc"""
 841
 842     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "r"
 843
 844     def __init__(self, x1, y1, x2, y2, r):
 845         arct_pt.__init__(self, unit.topt(x1), unit.topt(y1),
 846                          unit.topt(x2), unit.topt(y2), unit.topt(r))
 847
 848 #
 849 # "combined" pathitems provided for performance reasons
 850 #
 851
 852 class multilineto_pt(pathitem):
 853
 854     """Perform multiple linetos (coordinates in pts)"""
 855
 856     __slots__ = "points_pt"
 857
 858     def __init__(self, points_pt):
 859         self.points_pt = points_pt
 860
 861     def _updatecontext(self, context):
 862         context.currentsubpath = context.currentsubpath or context.currentpoint
 863         context.currentpoint = self.points_pt[-1]
 864
 865     def _bbox(self, context):
 866         xs_pt = [point[0] for point in self.points_pt]
 867         ys_pt = [point[1] for point in self.points_pt]
 868         return bbox.bbox_pt(min(context.currentpoint[0], *xs_pt),
 869                           min(context.currentpoint[1], *ys_pt),
 870                           max(context.currentpoint[0], *xs_pt),
 871                           max(context.currentpoint[1], *ys_pt))
 872
 873     def _normalized(self, context):
 874         result = []
 875         x0_pt, y0_pt = context.currentpoint
 876         for x_pt, y_pt in self.points_pt:
 877             result.append(normline(x0_pt, y0_pt, x_pt, y_pt))
 878             x0_pt, y0_pt = x_pt, y_pt
 879         return result
 880
 881     def outputPS(self, file):
 882         for point_pt in self.points_pt:
 883             file.write("%g %g lineto\n" % point_pt )
 884
 885     def outputPDF(self, file):
 886         for point_pt in self.points_pt:
 887             file.write("%f %f l\n" % point_pt )
 888
 889
 890 class multicurveto_pt(pathitem):
 891
 892     """Perform multiple curvetos (coordinates in pts)"""
 893
 894     __slots__ = "points_pt"
 895
 896     def __init__(self, points_pt):
 897         self.points_pt = points_pt
 898
 899     def _updatecontext(self, context):
 900         context.currentsubpath = context.currentsubpath or context.currentpoint
 901         context.currentpoint = self.points_pt[-1]
 902
 903     def _bbox(self, context):
 904         xs = ( [point[0] for point in self.points_pt] +
 905                [point[2] for point in self.points_pt] +
 906                [point[4] for point in self.points_pt] )
 907         ys = ( [point[1] for point in self.points_pt] +
 908                [point[3] for point in self.points_pt] +
 909                [point[5] for point in self.points_pt] )
 910         return bbox.bbox_pt(min(context.currentpoint[0], *xs_pt),
 911                           min(context.currentpoint[1], *ys_pt),
 912                           max(context.currentpoint[0], *xs_pt),
 913                           max(context.currentpoint[1], *ys_pt))
 914
 915     def _normalized(self, context):
 916         result = []
 917         x0_pt, y0_pt = context.currentpoint
 918         for point_pt in self.points_pt:
 919             result.append(normcurve(x0_pt, y0_pt, *point_pt))
 920             x0_pt, y0_pt = point_pt[4:]
 921         return result
 922
 923     def outputPS(self, file):
 924         for point_pt in self.points_pt:
 925             file.write("%g %g %g %g %g %g curveto\n" % point_pt)
 926
 927     def outputPDF(self, file):
 928         for point_pt in self.points_pt:
 929             file.write("%f %f %f %f %f %f c\n" % point_pt)
 930
 931
 932 ################################################################################
 933 # path: PS style path
 934 ################################################################################
 935
 936 class path(base.canvasitem):
 937
 938     """PS style path"""
 939
 940     __slots__ = "path"
 941
 942     def __init__(self, *args):
 943         if len(args)==1 and isinstance(args[0], path):
 944             self.path = args[0].path
 945         else:
 946             self.path = list(args)
 947
 948     def __add__(self, other):
 949         return path(*(self.path+other.path))
 950
 951     def __iadd__(self, other):
 952         self.path += other.path
 953         return self
 954
 955     def __getitem__(self, i):
 956         return self.path[i]
 957
 958     def __len__(self):
 959         return len(self.path)
 960
 961     def append(self, pathitem):
 962         self.path.append(pathitem)
 963
 964     def arclen_pt(self):
 965         """returns total arc length of path in pts"""
 966         return normpath(self).arclen_pt()
 967
 968     def arclen(self):
 969         """returns total arc length of path"""
 970         return normpath(self).arclen()
 971
 972     def arclentoparam(self, lengths):
 973         """returns the parameter value(s) matching the given length(s)"""
 974         return normpath(self).arclentoparam(lengths)
 975
 976     def at_pt(self, param=None, arclen=None):
 977         """return coordinates of path in pts at either parameter value param
 978         or arc length arclen.
 979
 980         At discontinuities in the path, the limit from below is returned
 981         """
 982         return normpath(self).at_pt(param, arclen)
 983
 984     def at(self, param=None, arclen=None):
 985         """return coordinates of path at either parameter value param
 986         or arc length arclen.
 987
 988         At discontinuities in the path, the limit from below is returned
 989         """
 990         return normpath(self).at(param, arclen)
 991
 992     def bbox(self):
 993         context = _pathcontext()
 994         abbox = None
 995
 996         for pitem in self.path:
 997             nbbox =  pitem._bbox(context)
 998             pitem._updatecontext(context)
 999             if abbox is None:
1000                 abbox = nbbox
1001             elif nbbox:
1002                 abbox += nbbox
1003
1004         return abbox
1005
1006     def begin_pt(self):
1007         """return coordinates of first point of first subpath in path (in pts)"""
1008         return normpath(self).begin_pt()
1009
1010     def begin(self):
1011         """return coordinates of first point of first subpath in path"""
1012         return normpath(self).begin()
1013
1014     def curvradius_pt(self, param=None, arclen=None):
1015         """Returns the curvature radius in pts (or None if infinite)
1016         at parameter param or arc length arclen.  This is the inverse
1017         of the curvature at this parameter
1018
1019         Please note that this radius can be negative or positive,
1020         depending on the sign of the curvature"""
1021         return normpath(self).curvradius_pt(param, arclen)
1022
1023     def curvradius(self, param=None, arclen=None):
1024         """Returns the curvature radius (or None if infinite) at
1025         parameter param or arc length arclen.  This is the inverse of
1026         the curvature at this parameter
1027
1028         Please note that this radius can be negative or positive,
1029         depending on the sign of the curvature"""
1030         return normpath(self).curvradius(param, arclen)
1031
1032     def end_pt(self):
1033         """return coordinates of last point of last subpath in path (in pts)"""
1034         return normpath(self).end_pt()
1035
1036     def end(self):
1037         """return coordinates of last point of last subpath in path"""
1038         return normpath(self).end()
1039
1040     def joined(self, other):
1041         """return path consisting of self and other joined together"""
1042         return normpath(self).joined(other)
1043
1044     # << operator also designates joining
1045     __lshift__ = joined
1046
1047     def intersect(self, other):
1048         """intersect normpath corresponding to self with other path"""
1049         return normpath(self).intersect(other)
1050
1051     def range(self):
1052         """return maximal value for parameter value t for corr. normpath"""
1053         return normpath(self).range()
1054
1055     def reversed(self):
1056         """return reversed path"""
1057         return normpath(self).reversed()
1058
1059     def split(self, params):
1060         """return corresponding normpaths split at parameter values params"""
1061         return normpath(self).split(params)
1062
1063     def tangent(self, param=None, arclen=None, length=None):
1064         """return tangent vector of path at either parameter value param
1065         or arc length arclen.
1066
1067         At discontinuities in the path, the limit from below is returned.
1068         If length is not None, the tangent vector will be scaled to
1069         the desired length.
1070         """
1071         return normpath(self).tangent(param, arclen, length)
1072
1073     def trafo(self, param=None, arclen=None):
1074         """return transformation at either parameter value param or arc length arclen"""
1075         return normpath(self).trafo(param, arclen)
1076
1077     def transformed(self, trafo):
1078         """return transformed path"""
1079         return normpath(self).transformed(trafo)
1080
1081     def outputPS(self, file):
1082         if not (isinstance(self.path[0], moveto_pt) or
1083                 isinstance(self.path[0], arc_pt) or
1084                 isinstance(self.path[0], arcn_pt)):
1085             raise PathException("first path element must be either moveto, arc, or arcn")
1086         for pitem in self.path:
1087             pitem.outputPS(file)
1088
1089     def outputPDF(self, file):
1090         if not (isinstance(self.path[0], moveto_pt) or
1091                 isinstance(self.path[0], arc_pt) or
1092                 isinstance(self.path[0], arcn_pt)):
1093             raise PathException("first path element must be either moveto, arc, or arcn")
1094         # PDF practically only supports normpathitems
1095         context = _pathcontext()
1096         for pitem in self.path:
1097             for npitem in pitem._normalized(context):
1098                 npitem.outputPDF(file)
1099             pitem._updatecontext(context)
1100
1101 ################################################################################
1102 # some special kinds of path, again in two variants
1103 ################################################################################
1104
1105 class line_pt(path):
1106
1107    """straight line from (x1_pt, y1_pt) to (x2_pt, y2_pt) (coordinates in pts)"""
1108
1109    def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt):
1110        path.__init__(self, moveto_pt(x1_pt, y1_pt), lineto_pt(x2_pt, y2_pt))
1111
1112
1113 class curve_pt(path):
1114
1115    """Bezier curve with control points (x0_pt, y1_pt),..., (x3_pt, y3_pt)
1116    (coordinates in pts)"""
1117
1118    def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1119        path.__init__(self,
1120                      moveto_pt(x0_pt, y0_pt),
1121                      curveto_pt(x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1122
1123
1124 class rect_pt(path):
1125
1126    """rectangle at position (x,y) with width and height (coordinates in pts)"""
1127
1128    def __init__(self, x, y, width, height):
1129        path.__init__(self, moveto_pt(x, y),
1130                            lineto_pt(x+width, y),
1131                            lineto_pt(x+width, y+height),
1132                            lineto_pt(x, y+height),
1133                            closepath())
1134
1135
1136 class circle_pt(path):
1137
1138    """circle with center (x,y) and radius"""
1139
1140    def __init__(self, x, y, radius):
1141        path.__init__(self, arc_pt(x, y, radius, 0, 360),
1142                      closepath())
1143
1144
1145 class line(line_pt):
1146
1147    """straight line from (x1, y1) to (x2, y2)"""
1148
1149    def __init__(self, x1, y1, x2, y2):
1150        line_pt.__init__(self,
1151                         unit.topt(x1), unit.topt(y1),
1152                         unit.topt(x2), unit.topt(y2))
1153
1154
1155 class curve(curve_pt):
1156
1157    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
1158
1159    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1160        curve_pt.__init__(self,
1161                          unit.topt(x0), unit.topt(y0),
1162                          unit.topt(x1), unit.topt(y1),
1163                          unit.topt(x2), unit.topt(y2),
1164                          unit.topt(x3), unit.topt(y3))
1165
1166
1167 class rect(rect_pt):
1168
1169    """rectangle at position (x,y) with width and height"""
1170
1171    def __init__(self, x, y, width, height):
1172        rect_pt.__init__(self,
1173                         unit.topt(x), unit.topt(y),
1174                         unit.topt(width), unit.topt(height))
1175
1176
1177 class circle(circle_pt):
1178
1179    """circle with center (x,y) and radius"""
1180
1181    def __init__(self, x, y, radius):
1182        circle_pt.__init__(self,
1183                         unit.topt(x), unit.topt(y),
1184                         unit.topt(radius))
1185
1186 ################################################################################
1187 # normpath and corresponding classes
1188 ################################################################################
1189
1190 # two helper functions for the intersection of normpathitems
1191
1192 def _intersectnormcurves(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
1193     """intersect two bpathitems
1194
1195     a and b are bpathitems with parameter ranges [a_t0, a_t1],
1196     respectively [b_t0, b_t1].
1197     epsilon determines when the bpathitems are assumed to be straight
1198
1199     """
1200
1201     # intersection of bboxes is a necessary criterium for intersection
1202     if not a.bbox().intersects(b.bbox()): return []
1203
1204     if not a.isstraight(epsilon):
1205         (aa, ab) = a.midpointsplit()
1206         a_tm = 0.5*(a_t0+a_t1)
1207
1208         if not b.isstraight(epsilon):
1209             (ba, bb) = b.midpointsplit()
1210             b_tm = 0.5*(b_t0+b_t1)
1211
1212             return ( _intersectnormcurves(aa, a_t0, a_tm,
1213                                        ba, b_t0, b_tm, epsilon) +
1214                      _intersectnormcurves(ab, a_tm, a_t1,
1215                                        ba, b_t0, b_tm, epsilon) +
1216                      _intersectnormcurves(aa, a_t0, a_tm,
1217                                        bb, b_tm, b_t1, epsilon) +
1218                      _intersectnormcurves(ab, a_tm, a_t1,
1219                                        bb, b_tm, b_t1, epsilon) )
1220         else:
1221             return ( _intersectnormcurves(aa, a_t0, a_tm,
1222                                        b, b_t0, b_t1, epsilon) +
1223                      _intersectnormcurves(ab, a_tm, a_t1,
1224                                        b, b_t0, b_t1, epsilon) )
1225     else:
1226         if not b.isstraight(epsilon):
1227             (ba, bb) = b.midpointsplit()
1228             b_tm = 0.5*(b_t0+b_t1)
1229
1230             return  ( _intersectnormcurves(a, a_t0, a_t1,
1231                                        ba, b_t0, b_tm, epsilon) +
1232                       _intersectnormcurves(a, a_t0, a_t1,
1233                                        bb, b_tm, b_t1, epsilon) )
1234         else:
1235             # no more subdivisions of either a or b
1236             # => try to intersect a and b as straight line segments
1237
1238             a_deltax = a.x3_pt - a.x0_pt
1239             a_deltay = a.y3_pt - a.y0_pt
1240             b_deltax = b.x3_pt - b.x0_pt
1241             b_deltay = b.y3_pt - b.y0_pt
1242
1243             det = b_deltax*a_deltay - b_deltay*a_deltax
1244
1245             ba_deltax0_pt = b.x0_pt - a.x0_pt
1246             ba_deltay0_pt = b.y0_pt - a.y0_pt
1247
1248             try:
1249                 a_t = ( b_deltax*ba_deltay0_pt - b_deltay*ba_deltax0_pt)/det
1250                 b_t = ( a_deltax*ba_deltay0_pt - a_deltay*ba_deltax0_pt)/det
1251             except ArithmeticError:
1252                 return []
1253
1254             # check for intersections out of bound
1255             if not (0<=a_t<=1 and 0<=b_t<=1): return []
1256
1257             # return rescaled parameters of the intersection
1258             return [ ( a_t0 + a_t * (a_t1 - a_t0),
1259                        b_t0 + b_t * (b_t1 - b_t0) ) ]
1260
1261
1262 def _intersectnormlines(a, b):
1263     """return one-element list constisting either of tuple of
1264     parameters of the intersection point of the two normlines a and b
1265     or empty list if both normlines do not intersect each other"""
1266
1267     a_deltax_pt = a.x1_pt - a.x0_pt
1268     a_deltay_pt = a.y1_pt - a.y0_pt
1269     b_deltax_pt = b.x1_pt - b.x0_pt
1270     b_deltay_pt = b.y1_pt - b.y0_pt
1271
1272     det = b_deltax_pt * a_deltay_pt - b_deltay_pt * a_deltax_pt
1273
1274     ba_deltax0_pt = b.x0_pt - a.x0_pt
1275     ba_deltay0_pt = b.y0_pt - a.y0_pt
1276
1277     try:
1278         a_t = ( b_deltax_pt * ba_deltay0_pt - b_deltay_pt * ba_deltax0_pt)/det
1279         b_t = ( a_deltax_pt * ba_deltay0_pt - a_deltay_pt * ba_deltax0_pt)/det
1280     except ArithmeticError:
1281         return []
1282
1283     # check for intersections out of bound
1284     if not (0<=a_t<=1 and 0<=b_t<=1): return []
1285
1286     # return parameters of the intersection
1287     return [( a_t, b_t)]
1288
1289 #
1290 # normpathitem: normalized element
1291 #
1292
1293 class normpathitem:
1294
1295     """element of a normalized sub path"""
1296
1297     def at_pt(self, t):
1298         """returns coordinates of point in pts at parameter t (0<=t<=1) """
1299         pass
1300
1301     def arclen_pt(self, epsilon=1e-5):
1302         """returns arc length of normpathitem in pts with given accuracy epsilon"""
1303         pass
1304
1305     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1306         """returns tuple (t,l) with
1307           t the parameter where the arclen of normpathitem is length and
1308           l the total arclen
1309
1310         length:  length (in pts) to find the parameter for
1311         epsilon: epsilon controls the accuracy for calculation of the
1312                  length of the Bezier elements
1313         """
1314         # Note: _arclentoparam returns both, parameters and total lengths
1315         # while  arclentoparam returns only parameters
1316         pass
1317
1318     def bbox(self):
1319         """return bounding box of normpathitem"""
1320         pass
1321
1322     def curvradius_pt(self, param):
1323         """Returns the curvature radius in pts at parameter param.
1324         This is the inverse of the curvature at this parameter
1325
1326         Please note that this radius can be negative or positive,
1327         depending on the sign of the curvature"""
1328         pass
1329
1330     def intersect(self, other, epsilon=1e-5):
1331         """intersect self with other normpathitem"""
1332         pass
1333
1334     def reversed(self):
1335         """return reversed normpathitem"""
1336         pass
1337
1338     def split(self, parameters):
1339         """splits normpathitem
1340
1341         parameters: list of parameter values (0<=t<=1) at which to split
1342
1343         returns None or list of tuple of normpathitems corresponding to
1344         the orginal normpathitem.
1345
1346         """
1347         pass
1348
1349     def tangentvector_pt(self, t):
1350         """returns tangent vector of normpathitem in pts at parameter t (0<=t<=1)"""
1351         pass
1352
1353     def transformed(self, trafo):
1354         """return transformed normpathitem according to trafo"""
1355         pass
1356
1357     def outputPS(self, file):
1358         """write PS code corresponding to normpathitem to file"""
1359         pass
1360
1361     def outputPS(self, file):
1362         """write PDF code corresponding to normpathitem to file"""
1363         pass
1364
1365 #
1366 # there are only two normpathitems: normline and normcurve
1367 #
1368
1369 class normline(normpathitem):
1370
1371     """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)"""
1372
1373     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt"
1374
1375     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt):
1376          self.x0_pt = x0_pt
1377          self.y0_pt = y0_pt
1378          self.x1_pt = x1_pt
1379          self.y1_pt = y1_pt
1380
1381     def __str__(self):
1382         return "normline(%g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt)
1383
1384     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1385         l = self.arclen_pt(epsilon)
1386         return ([max(min(1.0 * length / l, 1), 0) for length in lengths], l)
1387
1388     def _normcurve(self):
1389         """ return self as equivalent normcurve """
1390         xa_pt = self.x0_pt+(self.x1_pt-self.x0_pt)/3.0
1391         ya_pt = self.y0_pt+(self.y1_pt-self.y0_pt)/3.0
1392         xb_pt = self.x0_pt+2.0*(self.x1_pt-self.x0_pt)/3.0
1393         yb_pt = self.y0_pt+2.0*(self.y1_pt-self.y0_pt)/3.0
1394         return normcurve(self.x0_pt, self.y0_pt, xa_pt, ya_pt, xb_pt, yb_pt, self.x1_pt, self.y1_pt)
1395
1396     def arclen_pt(self,  epsilon=1e-5):
1397         return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
1398
1399     def at_pt(self, t):
1400         return self.x0_pt+(self.x1_pt-self.x0_pt)*t, self.y0_pt+(self.y1_pt-self.y0_pt)*t
1401
1402     def bbox(self):
1403         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt), min(self.y0_pt, self.y1_pt),
1404                           max(self.x0_pt, self.x1_pt), max(self.y0_pt, self.y1_pt))
1405
1406     def begin_pt(self):
1407         return self.x0_pt, self.y0_pt
1408
1409     def curvradius_pt(self, param):
1410         return None
1411
1412     def end_pt(self):
1413         return self.x1_pt, self.y1_pt
1414
1415     def intersect(self, other, epsilon=1e-5):
1416         if isinstance(other, normline):
1417             return _intersectnormlines(self, other)
1418         else:
1419             return  _intersectnormcurves(self._normcurve(), 0, 1, other, 0, 1, epsilon)
1420
1421     def isstraight(self, epsilon):
1422         return 1
1423
1424     def reverse(self):
1425         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt = self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1426
1427     def reversed(self):
1428         return normline(self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
1429
1430     def split(self, params):
1431         x0_pt, y0_pt = self.x0_pt, self.y0_pt
1432         x1_pt, y1_pt = self.x1_pt, self.y1_pt
1433         if params:
1434             xl_pt, yl_pt = x0_pt, y0_pt
1435             result = []
1436
1437             if params[0] == 0:
1438                 result.append(None)
1439                 params = params[1:]
1440
1441             if params:
1442                 for t in params:
1443                     xs_pt, ys_pt = x0_pt + (x1_pt-x0_pt)*t, y0_pt + (y1_pt-y0_pt)*t
1444                     result.append(normline(xl_pt, yl_pt, xs_pt, ys_pt))
1445                     xl_pt, yl_pt = xs_pt, ys_pt
1446
1447                 if params[-1]!=1:
1448                     result.append(normline(xs_pt, ys_pt, x1_pt, y1_pt))
1449                 else:
1450                     result.append(None)
1451             else:
1452                 result.append(normline(x0_pt, y0_pt, x1_pt, y1_pt))
1453         else:
1454             result = []
1455         return result
1456
1457     def tangentvector_pt(self, param):
1458         return self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt
1459
1460     def trafo(self, param):
1461         tx_pt, ty_pt = self.at_pt(param)
1462         tdx_pt, tdy_pt = self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt
1463         return trafo.translate_pt(tx_pt, ty_pt)*trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt)))
1464
1465     def transformed(self, trafo):
1466         return normline(*(trafo._apply(self.x0_pt, self.y0_pt) + trafo._apply(self.x1_pt, self.y1_pt)))
1467
1468     def outputPS(self, file):
1469         file.write("%g %g lineto\n" % (self.x1_pt, self.y1_pt))
1470
1471     def outputPDF(self, file):
1472         file.write("%f %f l\n" % (self.x1_pt, self.y1_pt))
1473
1474
1475 class normcurve(normpathitem):
1476
1477     """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)"""
1478
1479     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
1480
1481     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1482         self.x0_pt = x0_pt
1483         self.y0_pt = y0_pt
1484         self.x1_pt = x1_pt
1485         self.y1_pt = y1_pt
1486         self.x2_pt = x2_pt
1487         self.y2_pt = y2_pt
1488         self.x3_pt = x3_pt
1489         self.y3_pt = y3_pt
1490
1491     def __str__(self):
1492         return "normcurve(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt,
1493                                                               self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt)
1494
1495     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1496         """computes the parameters [t] of bpathitem where the given lengths (in pts) are assumed
1497         returns ( [parameters], total arclen)
1498         A negative length gives a parameter 0"""
1499
1500         # create the list of accumulated lengths
1501         # and the length of the parameters
1502         seg = self.seglengths(1, epsilon)
1503         arclens = [seg[i][0] for i in range(len(seg))]
1504         Dparams = [seg[i][1] for i in range(len(seg))]
1505         l = len(arclens)
1506         for i in range(1,l):
1507             arclens[i] += arclens[i-1]
1508
1509         # create the list of parameters to be returned
1510         params = []
1511         for length in lengths:
1512             # find the last index that is smaller than length
1513             try:
1514                 lindex = bisect.bisect_left(arclens, length)
1515             except: # workaround for python 2.0
1516                 lindex = bisect.bisect(arclens, length)
1517                 while lindex and (lindex >= len(arclens) or
1518                                   arclens[lindex] >= length):
1519                     lindex -= 1
1520             if lindex == 0:
1521                 param = Dparams[0] * length * 1.0 / arclens[0]
1522             elif lindex < l-1:
1523                 param = Dparams[lindex+1] * (length - arclens[lindex]) * 1.0 / (arclens[lindex+1] - arclens[lindex])
1524                 for i in range(lindex+1):
1525                     param += Dparams[i]
1526             else:
1527                 param = 1 + Dparams[-1] * (length - arclens[-1]) * 1.0 / (arclens[-1] - arclens[-2])
1528
1529             param = max(min(param,1),0)
1530             params.append(param)
1531         return (params, arclens[-1])
1532
1533     def arclen_pt(self, epsilon=1e-5):
1534         """computes arclen of bpathitem in pts using successive midpoint split"""
1535         if self.isstraight(epsilon):
1536             return math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1537         else:
1538             a, b = self.midpointsplit()
1539             return a.arclen_pt(epsilon) + b.arclen_pt(epsilon)
1540
1541
1542     def at_pt(self, t):
1543         xt_pt = ( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t +
1544                   (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt          )*t*t +
1545                   (-3*self.x0_pt+3*self.x1_pt                      )*t +
1546                   self.x0_pt )
1547         yt_pt = ( (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t +
1548                   (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt          )*t*t +
1549                   (-3*self.y0_pt+3*self.y1_pt                      )*t +
1550                   self.y0_pt )
1551         return xt_pt, yt_pt
1552
1553     def bbox(self):
1554         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1555                           min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt),
1556                           max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1557                           max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt))
1558
1559     def begin_pt(self):
1560         return self.x0_pt, self.y0_pt
1561
1562     def curvradius_pt(self, param):
1563         xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) +
1564                  6 * (1-param)*param * (-self.x1_pt + self.x2_pt) +
1565                  3 * param*param * (-self.x2_pt + self.x3_pt) )
1566         ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) +
1567                  6 * (1-param)*param * (-self.y1_pt + self.y2_pt) +
1568                  3 * param*param * (-self.y2_pt + self.y3_pt) )
1569         xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) +
1570                   6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) )
1571         yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) +
1572                   6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) )
1573         return (xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot)
1574
1575     def end_pt(self):
1576         return self.x3_pt, self.y3_pt
1577
1578     def intersect(self, other, epsilon=1e-5):
1579         if isinstance(other, normline):
1580             return  _intersectnormcurves(self, 0, 1, other._normcurve(), 0, 1, epsilon)
1581         else:
1582             return  _intersectnormcurves(self, 0, 1, other, 0, 1, epsilon)
1583
1584     def isstraight(self, epsilon=1e-5):
1585         """check wheter the normcurve is approximately straight"""
1586
1587         # just check, whether the modulus of the difference between
1588         # the length of the control polygon
1589         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1590         # straight line between starting and ending point of the
1591         # normcurve (i.e. |P3-P1|) is smaller the epsilon
1592         return abs(math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt)+
1593                    math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt)+
1594                    math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt)-
1595                    math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt))<epsilon
1596
1597     def midpointsplit(self):
1598         """splits bpathitem at midpoint returning bpath with two bpathitems"""
1599
1600         # for efficiency reason, we do not use self.split(0.5)!
1601
1602         # first, we have to calculate the  midpoints between adjacent
1603         # control points
1604         x01_pt = 0.5*(self.x0_pt + self.x1_pt)
1605         y01_pt = 0.5*(self.y0_pt + self.y1_pt)
1606         x12_pt = 0.5*(self.x1_pt + self.x2_pt)
1607         y12_pt = 0.5*(self.y1_pt + self.y2_pt)
1608         x23_pt = 0.5*(self.x2_pt + self.x3_pt)
1609         y23_pt = 0.5*(self.y2_pt + self.y3_pt)
1610
1611         # In the next iterative step, we need the midpoints between 01 and 12
1612         # and between 12 and 23
1613         x01_12_pt = 0.5*(x01_pt + x12_pt)
1614         y01_12_pt = 0.5*(y01_pt + y12_pt)
1615         x12_23_pt = 0.5*(x12_pt + x23_pt)
1616         y12_23_pt = 0.5*(y12_pt + y23_pt)
1617
1618         # Finally the midpoint is given by
1619         xmidpoint_pt = 0.5*(x01_12_pt + x12_23_pt)
1620         ymidpoint_pt = 0.5*(y01_12_pt + y12_23_pt)
1621
1622         return (normcurve(self.x0_pt, self.y0_pt,
1623                           x01_pt, y01_pt,
1624                           x01_12_pt, y01_12_pt,
1625                           xmidpoint_pt, ymidpoint_pt),
1626                 normcurve(xmidpoint_pt, ymidpoint_pt,
1627                           x12_23_pt, y12_23_pt,
1628                           x23_pt, y23_pt,
1629                           self.x3_pt, self.y3_pt))
1630
1631     def reverse(self):
1632         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt = \
1633         self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1634
1635     def reversed(self):
1636         return normcurve(self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
1637
1638     def seglengths(self, paraminterval, epsilon=1e-5):
1639         """returns the list of segment line lengths (in pts) of the normcurve
1640            together with the length of the parameterinterval"""
1641
1642         # lower and upper bounds for the arclen
1643         lowerlen = math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1644         upperlen = ( math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt) +
1645                      math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt) +
1646                      math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt) )
1647
1648         # instead of isstraight method:
1649         if abs(upperlen-lowerlen)<epsilon:
1650             return [( 0.5*(upperlen+lowerlen), paraminterval )]
1651         else:
1652             a, b = self.midpointsplit()
1653             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
1654
1655     def _split(self, parameters):
1656         """return list of normcurve corresponding to split at parameters"""
1657
1658         # first, we calculate the coefficients corresponding to our
1659         # original bezier curve. These represent a useful starting
1660         # point for the following change of the polynomial parameter
1661         a0x_pt = self.x0_pt
1662         a0y_pt = self.y0_pt
1663         a1x_pt = 3*(-self.x0_pt+self.x1_pt)
1664         a1y_pt = 3*(-self.y0_pt+self.y1_pt)
1665         a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt)
1666         a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt)
1667         a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt
1668         a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt
1669
1670         if parameters[0]!=0:
1671             parameters = [0] + parameters
1672         if parameters[-1]!=1:
1673             parameters = parameters + [1]
1674
1675         result = []
1676
1677         for i in range(len(parameters)-1):
1678             t1 = parameters[i]
1679             dt = parameters[i+1]-t1
1680
1681             # [t1,t2] part
1682             #
1683             # the new coefficients of the [t1,t1+dt] part of the bezier curve
1684             # are then given by expanding
1685             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
1686             #  a3*(t1+dt*u)**3 in u, yielding
1687             #
1688             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
1689             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
1690             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
1691             #   a3*dt**3                         * u**3
1692             #
1693             # from this values we obtain the new control points by inversion
1694             #
1695             # XXX: we could do this more efficiently by reusing for
1696             # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
1697             # Bezier curve
1698
1699             x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1
1700             y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1
1701             x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt
1702             y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt
1703             x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt
1704             y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt
1705             x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt
1706             y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt
1707
1708             result.append(normcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1709
1710         return result
1711
1712     def split(self, params):
1713         if params:
1714             # we need to split
1715             bps = self._split(list(params))
1716
1717             if params[0]==0:
1718                 result = [None]
1719             else:
1720                 bp0 = bps[0]
1721                 result = [normcurve(self.x0_pt, self.y0_pt, bp0.x1_pt, bp0.y1_pt, bp0.x2_pt, bp0.y2_pt, bp0.x3_pt, bp0.y3_pt)]
1722                 bps = bps[1:]
1723
1724             for bp in bps:
1725                 result.append(normcurve(bp.x0_pt, bp.y0_pt, bp.x1_pt, bp.y1_pt, bp.x2_pt, bp.y2_pt, bp.x3_pt, bp.y3_pt))
1726
1727             if params[-1]==1:
1728                 result.append(None)
1729         else:
1730             result = []
1731         return result
1732
1733     def tangentvector_pt(self, param):
1734         tvectx = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
1735                   2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt        )*param +
1736                     (-3*self.x0_pt+3*self.x1_pt                  ))
1737         tvecty = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
1738                   2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt        )*param +
1739                     (-3*self.y0_pt+3*self.y1_pt                  ))
1740         return (tvectx, tvecty)
1741
1742     def trafo(self, param):
1743         tx_pt, ty_pt = self.at_pt(param)
1744         tdx_pt, tdy_pt = self.tangentvector_pt(param)
1745         return trafo.translate_pt(tx_pt, ty_pt)*trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt)))
1746
1747     def transform(self, trafo):
1748         self.x0_pt, self.y0_pt = trafo._apply(self.x0_pt, self.y0_pt)
1749         self.x1_pt, self.y1_pt = trafo._apply(self.x1_pt, self.y1_pt)
1750         self.x2_pt, self.y2_pt = trafo._apply(self.x2_pt, self.y2_pt)
1751         self.x3_pt, self.y3_pt = trafo._apply(self.x3_pt, self.y3_pt)
1752
1753     def transformed(self, trafo):
1754         return normcurve(*(trafo._apply(self.x0_pt, self.y0_pt)+
1755                            trafo._apply(self.x1_pt, self.y1_pt)+
1756                            trafo._apply(self.x2_pt, self.y2_pt)+
1757                            trafo._apply(self.x3_pt, self.y3_pt)))
1758
1759     def outputPS(self, file):
1760         file.write("%g %g %g %g %g %g curveto\n" % (self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt))
1761
1762     def outputPDF(self, file):
1763         file.write("%f %f %f %f %f %f c\n" % (self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt))
1764
1765 #
1766 # normpaths are made up of normsubpaths, which represent connected line segments
1767 #
1768
1769 class normsubpath:
1770
1771     """sub path of a normalized path
1772
1773     A subpath consists of a list of normpathitems, i.e., lines and bcurves
1774     and can either be closed or not.
1775
1776     Some invariants, which have to be obeyed:
1777     - All normpathitems have to be longer than epsilon pts.
1778     - The last point of a normpathitem and the first point of the next
1779     element have to be equal.
1780     - When the path is closed, the last normpathitem has to be a
1781     normline and the last point of this normline has to be equal
1782     to the first point of the first normpathitem, except when
1783     this normline would be too short.
1784     """
1785
1786     __slots__ = "normpathitems", "closed", "epsilon", "startx_pt", "starty_pt", "skippedlastitem"
1787
1788     def __init__(self, normpathitems=[], closed=0, epsilon=1e-5):
1789         self.epsilon = epsilon
1790         # start point of the normsubpath, needed when short (i.e. shorter than epsilon)
1791         # normpathitems are inserted at the beginning
1792         self.startx_pt = self.starty_pt = None
1793         # If one or more items appended to the normsubpath have been
1794         # skipped (because their total length was shorter than
1795         # epsilon), we remember this fact because we later have to
1796         # modify the next normpathitem
1797         self.skippedlastitem = 0
1798
1799         self.normpathitems = []
1800         self.closed = 0
1801         for normpathitem in normpathitems:
1802             self.append(normpathitem)
1803
1804         if closed:
1805             self.close()
1806
1807     def __str__(self):
1808         return "subpath(%s, [%s])" % (self.closed and "closed" or "open",
1809                                     ", ".join(map(str, self.normpathitems)))
1810
1811     def append(self, normpathitem):
1812         if self.closed:
1813             raise PathException("Cannot append to closed normsubpath")
1814         if self.startx_pt is None:
1815             # first normpathitem in normsubpath has to set the start point of the normsubpath
1816             lastx_pt = self.startx_pt = normpathitem.x0_pt
1817             lasty_pt = self.starty_pt = normpathitem.y0_pt
1818         elif self.normpathitems:
1819             lastx_pt, lasty_pt = self.normpathitems[-1].end_pt()
1820         else:
1821             lastx_pt = self.startx_pt
1822             lasty_pt = self.starty_pt
1823
1824         newendx_pt, newendy_pt = normpathitem.end_pt()
1825         if (math.hypot(newendx_pt-lastx_pt, newendy_pt-lasty_pt) >= self.epsilon or
1826             normpathitem.arclen_pt(self.epsilon) >= self.epsilon):
1827             if self.skippedlastitem:
1828                 if isinstance(normpathitem, normline):
1829                     normpathitem = normline(lastx_pt, lasty_pt, normpathitem.x1_pt, normpathitem.y1_pt)
1830                 else:
1831                     normpathitem = normcurve(lastx_pt, lasty_pt,
1832                                              normpathitem.x1_pt, normpathitem.y1_pt,
1833                                              normpathitem.x2_pt, normpathitem.y2_pt,
1834                                              normpathitem.x3_pt, normpathitem.y3_pt)
1835             self.normpathitems.append(normpathitem)
1836             self.skippedlastitem = 0
1837         else:
1838             self.skippedlastitem = 1
1839
1840     def arclen_pt(self):
1841         """returns total arc length of normsubpath in pts with accuracy epsilon"""
1842         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normpathitems])
1843
1844     def _arclentoparam_pt(self, lengths):
1845         """returns [t, l] where t are parameter value(s) matching given length(s)
1846         and l is the total length of the normsubpath
1847         The parameters are with respect to the normsubpath: t in [0, self.range()]
1848         lengths that are < 0 give parameter 0"""
1849
1850         allarclen = 0
1851         allparams = [0] * len(lengths)
1852         rests = lengths[:]
1853
1854         for pitem in self.normpathitems:
1855             params, arclen = pitem._arclentoparam_pt(rests, self.epsilon)
1856             allarclen += arclen
1857             for i in range(len(rests)):
1858                 if rests[i] >= 0:
1859                     rests[i] -= arclen
1860                     allparams[i] += params[i]
1861
1862         return (allparams, allarclen)
1863
1864     def at_pt(self, param):
1865         """return coordinates in pts of sub path at parameter value param
1866
1867         The parameter param must be smaller or equal to the number of
1868         segments in the normpath, otherwise None is returned.
1869         """
1870         try:
1871             return self.normpathitems[int(param-self.epsilon)].at_pt(param-int(param-self.epsilon))
1872         except:
1873             raise PathException("parameter value param out of range")
1874
1875     def bbox(self):
1876         if self.normpathitems:
1877             abbox = self.normpathitems[0].bbox()
1878             for anormpathitem in self.normpathitems[1:]:
1879                 abbox += anormpathitem.bbox()
1880             return abbox
1881         else:
1882             return None
1883
1884     def begin_pt(self):
1885         return self.normpathitems[0].begin_pt()
1886
1887     def close(self):
1888         if self.closed:
1889             raise PathException("Cannot close already closed normsubpath")
1890         if not self.normpathitems:
1891             if self.startx_pt is None:
1892                 raise PathException("Cannot close empty normsubpath")
1893             else:
1894                 raise PathException("Normsubpath too short, cannot be closed")
1895         self.closed = 1
1896
1897     def curvradius_pt(self, param):
1898         try:
1899             return self.normpathitems[int(param-self.epsilon)].curvradius_pt(param-int(param-self.epsilon))
1900         except:
1901             raise PathException("parameter value param out of range")
1902
1903     def end_pt(self):
1904         return self.normpathitems[-1].end_pt()
1905
1906     def intersect(self, other):
1907         """intersect self with other normsubpath
1908
1909         returns a tuple of lists consisting of the parameter values
1910         of the intersection points of the corresponding normsubpath
1911
1912         """
1913         intersections = ([], [])
1914         epsilon = min(self.epsilon, other.epsilon)
1915         # Intersect all subpaths of self with the subpaths of other
1916         for t_a, pitem_a  in enumerate(self.normpathitems):
1917             for t_b, pitem_b in enumerate(other.normpathitems):
1918                 for intersection in pitem_a.intersect(pitem_b, epsilon):
1919                     # check whether an intersection occurs at the end
1920                     # of a closed subpath. If yes, we don't include it
1921                     # in the list of intersections to prevent a
1922                     # duplication of intersection points
1923                     if not ((self.closed and self.range()-intersection[0]-t_a<epsilon) or
1924                             (other.closed and other.range()-intersection[1]-t_b<epsilon)):
1925                         intersections[0].append(intersection[0]+t_a)
1926                         intersections[1].append(intersection[1]+t_b)
1927         return intersections
1928
1929     def range(self):
1930         """return maximal parameter value, i.e. number of line/curve segments"""
1931         return len(self.normpathitems)
1932
1933     def reverse(self):
1934         self.normpathitems.reverse()
1935         for npitem in self.normpathitems:
1936             npitem.reverse()
1937
1938     def reversed(self):
1939         nnormpathitems = []
1940         for i in range(len(self.normpathitems)):
1941             nnormpathitems.append(self.normpathitems[-(i+1)].reversed())
1942         return normsubpath(nnormpathitems, self.closed)
1943
1944     def split(self, params):
1945         """split normsubpath at list of parameter values params and return list
1946         of normsubpaths
1947
1948         The parameter list params has to be sorted. Note that each element of
1949         the resulting list is an open normsubpath.
1950         """
1951
1952         if min(params) < -self.epsilon or max(params) > self.range()+self.epsilon:
1953             raise PathException("parameter for split of subpath out of range")
1954
1955         result = []
1956         npitems = None
1957         for t, pitem in enumerate(self.normpathitems):
1958             # determine list of splitting parameters relevant for pitem
1959             nparams = []
1960             for nt in params:
1961                 if t+1 >= nt:
1962                     nparams.append(nt-t)
1963                     params = params[1:]
1964
1965             # now we split the path at the filtered parameter values
1966             # This yields a list of normpathitems and possibly empty
1967             # segments marked by None
1968             splitresult = pitem.split(nparams)
1969             if splitresult:
1970                 # first split?
1971                 if npitems is None:
1972                     if splitresult[0] is None:
1973                         # mark split at the beginning of the normsubpath
1974                         result = [None]
1975                     else:
1976                         result.append(normsubpath([splitresult[0]], 0))
1977                 else:
1978                     npitems.append(splitresult[0])
1979                     result.append(normsubpath(npitems, 0))
1980                 for npitem in splitresult[1:-1]:
1981                     result.append(normsubpath([npitem], 0))
1982                 if len(splitresult)>1 and splitresult[-1] is not None:
1983                     npitems = [splitresult[-1]]
1984                 else:
1985                     npitems = []
1986             else:
1987                 if npitems is None:
1988                     npitems = [pitem]
1989                 else:
1990                     npitems.append(pitem)
1991
1992         if npitems:
1993             result.append(normsubpath(npitems, 0))
1994         else:
1995             # mark split at the end of the normsubpath
1996             result.append(None)
1997
1998         # join last and first segment together if the normsubpath was originally closed
1999         if self.closed:
2000             if result[0] is None:
2001                 result = result[1:]
2002             elif result[-1] is None:
2003                 result = result[:-1]
2004             else:
2005                 result[-1].normpathitems.extend(result[0].normpathitems)
2006                 result = result[1:]
2007         return result
2008
2009     def tangent(self, param, length=None):
2010         tx_pt, ty_pt = self.at_pt(param)
2011         try:
2012             tdx_pt, tdy_pt = self.normpathitems[int(param-self.epsilon)].tangentvector_pt(param-int(param-self.epsilon))
2013         except:
2014             raise PathException("parameter value param out of range")
2015         tlen = math.hypot(tdx_pt, tdy_pt)
2016         if not (length is None or tlen==0):
2017             sfactor = unit.topt(length)/tlen
2018             tdx_pt *= sfactor
2019             tdy_pt *= sfactor
2020         return line_pt(tx_pt, ty_pt, tx_pt+tdx_pt, ty_pt+tdy_pt)
2021
2022     def trafo(self, param):
2023         try:
2024             return self.normpathitems[int(param-self.epsilon)].trafo(param-int(param-self.epsilon))
2025         except:
2026             raise PathException("parameter value param out of range")
2027
2028     def transform(self, trafo):
2029         """transform sub path according to trafo"""
2030         for pitem in self.normpathitems:
2031             pitem.transform(trafo)
2032
2033     def transformed(self, trafo):
2034         """return sub path transformed according to trafo"""
2035         nnormpathitems = []
2036         for pitem in self.normpathitems:
2037             nnormpathitems.append(pitem.transformed(trafo))
2038         return normsubpath(nnormpathitems, self.closed)
2039
2040     def outputPS(self, file):
2041         # if the normsubpath is closed, we must not output a normline at
2042         # the end
2043         if not self.normpathitems:
2044             return
2045         if self.closed and isinstance(self.normpathitems[-1], normline):
2046             normpathitems = self.normpathitems[:-1]
2047         else:
2048             normpathitems = self.normpathitems
2049         if normpathitems:
2050             file.write("%g %g moveto\n" % self.begin_pt())
2051             for anormpathitem in normpathitems:
2052                 anormpathitem.outputPS(file)
2053         if self.closed:
2054             file.write("closepath\n")
2055
2056     def outputPDF(self, file):
2057         # if the normsubpath is closed, we must not output a normline at
2058         # the end
2059         if not self.normpathitems:
2060             return
2061         if self.closed and isinstance(self.normpathitems[-1], normline):
2062             normpathitems = self.normpathitems[:-1]
2063         else:
2064             normpathitems = self.normpathitems
2065         if normpathitems:
2066             file.write("%f %f m\n" % self.begin_pt())
2067             for anormpathitem in normpathitems:
2068                 anormpathitem.outputPDF(file)
2069         if self.closed:
2070             file.write("h\n")
2071
2072 #
2073 # the normpath class
2074 #
2075
2076 class normpath(path):
2077
2078     """normalized path
2079
2080     A normalized path consists of a list of normalized sub paths.
2081
2082     """
2083
2084     def __init__(self, arg=[], epsilon=1e-5):
2085         """ construct a normpath from another normpath passed as arg,
2086         a path or a list of normsubpaths. An accuracy of epsilon pts
2087         is used for numerical calculations.
2088         """
2089
2090         self.epsilon = epsilon
2091         if isinstance(arg, normpath):
2092             self.subpaths = arg.subpaths[:]
2093             return
2094         elif isinstance(arg, path):
2095             # split path in sub paths
2096             self.subpaths = []
2097             currentsubpathitems = []
2098             context = _pathcontext()
2099             for pitem in arg.path:
2100                 for npitem in pitem._normalized(context):
2101                     if isinstance(npitem, moveto_pt):
2102                         if currentsubpathitems:
2103                             # append open sub path
2104                             self.subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
2105                         # start new sub path
2106                         currentsubpathitems = []
2107                     elif isinstance(npitem, closepath):
2108                         if currentsubpathitems:
2109                             # append closed sub path
2110                             currentsubpathitems.append(normline(context.currentpoint[0], context.currentpoint[1],
2111                                                               context.currentsubpath[0], context.currentsubpath[1]))
2112                         self.subpaths.append(normsubpath(currentsubpathitems, 1, epsilon))
2113                         currentsubpathitems = []
2114                     else:
2115                         currentsubpathitems.append(npitem)
2116                 pitem._updatecontext(context)
2117
2118             if currentsubpathitems:
2119                 # append open sub path
2120                 self.subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
2121         else:
2122             # we expect a list of normsubpaths
2123             self.subpaths = list(arg)
2124
2125     def __add__(self, other):
2126         result = normpath(other)
2127         result.subpaths = self.subpaths + result.subpaths
2128         return result
2129
2130     def __getitem__(self, i):
2131         return self.subpaths[i]
2132
2133     def __iadd__(self, other):
2134         self.subpaths += normpath(other).subpaths
2135         return self
2136
2137     def __nonzero__(self):
2138         return len(self.subpaths)>0
2139
2140     def __str__(self):
2141         return "normpath(%s)" % ", ".join(map(str, self.subpaths))
2142
2143     def _findsubpath(self, param, arclen):
2144         """return a tuple (subpath, rparam), where subpath is the subpath
2145         containing the position specified by either param or arclen and rparam
2146         is the corresponding parameter value in this subpath.
2147         """
2148
2149         if param is not None and arclen is not None:
2150             raise PathException("either param or arclen has to be specified, but not both")
2151
2152         if param is not None:
2153             try:
2154                 subpath, param = param
2155             except TypeError:
2156                 # determine subpath from param
2157                 spt = 0
2158                 for sp in self.subpaths:
2159                     sprange = sp.range()
2160                     if spt <= param <= sprange+spt+self.epsilon:
2161                         return sp, param-spt
2162                     spt += sprange
2163                 raise PathException("parameter value out of range")
2164             try:
2165                 return self.subpaths[subpath], param
2166             except IndexError:
2167                 raise PathException("subpath index out of range")
2168
2169         # we have been passed an arclen (or a tuple (subpath, arclen))
2170         try:
2171             subpath, arclen = arclen
2172         except:
2173             # determine subpath from arclen
2174             param = self.arclentoparam(arclen)
2175             for sp in self.subpaths:
2176                 sprange = sp.range()
2177                 if spt <= param <= sprange+spt+self.epsilon:
2178                     return sp, param-spt
2179                 spt += sprange
2180             raise PathException("parameter value out of range")
2181
2182         try:
2183             sp = self.subpaths[subpath]
2184         except IndexError:
2185             raise PathException("subpath index out of range")
2186         return sp, sp.arclentoparam(arclen)
2187
2188     def append(self, normsubpath):
2189         self.subpaths.append(normsubpath)
2190
2191     def arclen_pt(self):
2192         """returns total arc length of normpath in pts"""
2193         return sum([sp.arclen_pt() for sp in self.subpaths])
2194
2195     def arclen(self):
2196         """returns total arc length of normpath"""
2197         return self.arclen_pt() * unit.t_pt
2198
2199     def arclentoparam_pt(self, lengths):
2200         rests = lengths[:]
2201         allparams = [0] * len(lengths)
2202
2203         for sp in self.subpaths:
2204             # we need arclen for knowing when all the parameters are done
2205             # for lengths that are done: rests[i] is negative
2206             # sp._arclentoparam has to ignore such lengths
2207             params, arclen = sp._arclentoparam_pt(rests)
2208             finis = 0 # number of lengths that are done
2209             for i in range(len(rests)):
2210                 if rests[i] >= 0:
2211                   rests[i] -= arclen
2212                   allparams[i] += params[i]
2213                 else:
2214                     finis += 1
2215             if finis == len(rests): break
2216
2217         if len(lengths) == 1: allparams = allparams[0]
2218         return allparams
2219
2220     def arclentoparam(self, lengths):
2221         """returns the parameter value(s) matching the given length(s)
2222
2223         all given lengths must be positive.
2224         A length greater than the total arclength will give self.range()
2225         """
2226         l = [unit.topt(length) for length in helper.ensuresequence(lengths)]
2227         return self.arclentoparam_pt(l)
2228
2229     def at_pt(self, param=None, arclen=None):
2230         """return coordinates in pts of path at either parameter value param
2231         or arc length arclen.
2232
2233         At discontinuities in the path, the limit from below is returned.
2234         """
2235         sp, param = self._findsubpath(param, arclen)
2236         return sp.at_pt(param)
2237
2238     def at(self, param=None, arclen=None):
2239         """return coordinates of path at either parameter value param
2240         or arc length arclen.
2241
2242         At discontinuities in the path, the limit from below is returned
2243         """
2244         x, y = self.at_pt(param, arclen)
2245         return x * unit.t_pt, y * unit.t_pt
2246
2247     def bbox(self):
2248         abbox = None
2249         for sp in self.subpaths:
2250             nbbox =  sp.bbox()
2251             if abbox is None:
2252                 abbox = nbbox
2253             elif nbbox:
2254                 abbox += nbbox
2255         return abbox
2256
2257     def begin_pt(self):
2258         """return coordinates of first point of first subpath in path (in pts)"""
2259         if self.subpaths:
2260             return self.subpaths[0].begin_pt()
2261         else:
2262             raise PathException("cannot return first point of empty path")
2263
2264     def begin(self):
2265         """return coordinates of first point of first subpath in path"""
2266         x_pt, y_pt = self.begin_pt()
2267         return x_pt * unit.t_pt, y_pt * unit.t_pt
2268
2269     def curvradius_pt(self, param=None, arclen=None):
2270         """Returns the curvature radius in pts (or None if infinite)
2271         at parameter param or arc length arclen.  This is the inverse
2272         of the curvature at this parameter
2273
2274         Please note that this radius can be negative or positive,
2275         depending on the sign of the curvature"""
2276         sp, param = self._findsubpath(param, arclen)
2277         return sp.curvradius_pt(param)
2278
2279     def curvradius(self, param=None, arclen=None):
2280         """Returns the curvature radius (or None if infinite) at
2281         parameter param or arc length arclen.  This is the inverse of
2282         the curvature at this parameter
2283
2284         Please note that this radius can be negative or positive,
2285         depending on the sign of the curvature"""
2286         radius = self.curvradius_pt(param, arclen)
2287         if radius is not None:
2288             radius = radius * unit.t_pt
2289         return radius
2290
2291     def end_pt(self):
2292         """return coordinates of last point of last subpath in path (in pts)"""
2293         if self.subpaths:
2294             return self.subpaths[-1].end_pt()
2295         else:
2296             raise PathException("cannot return last point of empty path")
2297
2298     def end(self):
2299         """return coordinates of last point of last subpath in path"""
2300         x_pt, y_pt = self.end_pt()
2301         return x_pt * unit.t_pt, y_pt * unit.t_pt
2302
2303     def join(self, other):
2304         if not self.subpaths:
2305             raise PathException("cannot join to end of empty path")
2306         if self.subpaths[-1].closed:
2307             raise PathException("cannot join to end of closed sub path")
2308         other = normpath(other)
2309         if not other.subpaths:
2310             raise PathException("cannot join empty path")
2311
2312         self.subpaths[-1].normpathitems += other.subpaths[0].normpathitems
2313         self.subpaths += other.subpaths[1:]
2314
2315     def joined(self, other):
2316         result = normpath(self.subpaths)
2317         result.join(other)
2318         return result
2319
2320     def intersect(self, other):
2321         """intersect self with other path
2322
2323         returns a tuple of lists consisting of the parameter values
2324         of the intersection points of the corresponding normpath
2325
2326         """
2327         if not isinstance(other, normpath):
2328             other = normpath(other)
2329
2330         # here we build up the result
2331         intersections = ([], [])
2332
2333         # Intersect all subpaths of self with the subpaths of
2334         # other. Here, st_a, st_b are the parameter values
2335         # corresponding to the first point of the subpaths sp_a and
2336         # sp_b, respectively.
2337         st_a = 0
2338         for sp_a in self.subpaths:
2339             st_b =0
2340             for sp_b in other.subpaths:
2341                 for intersection in zip(*sp_a.intersect(sp_b)):
2342                     intersections[0].append(intersection[0]+st_a)
2343                     intersections[1].append(intersection[1]+st_b)
2344                 st_b += sp_b.range()
2345             st_a += sp_a.range()
2346         return intersections
2347
2348     def range(self):
2349         """return maximal value for parameter value param"""
2350         return sum([sp.range() for sp in self.subpaths])
2351
2352     def reverse(self):
2353         """reverse path"""
2354         self.subpaths.reverse()
2355         for sp in self.subpaths:
2356             sp.reverse()
2357
2358     def reversed(self):
2359         """return reversed path"""
2360         nnormpath = normpath()
2361         for i in range(len(self.subpaths)):
2362             nnormpath.subpaths.append(self.subpaths[-(i+1)].reversed())
2363         return nnormpath
2364
2365     def split(self, params):
2366         """split path at parameter values params
2367
2368         Note that the parameter list has to be sorted.
2369
2370         """
2371
2372         # check whether parameter list is really sorted
2373         sortedparams = list(params)
2374         sortedparams.sort()
2375         if sortedparams!=list(params):
2376             raise ValueError("split parameter list params has to be sorted")
2377
2378         # we construct this list of normpaths
2379         result = []
2380
2381         # the currently built up normpath
2382         np = normpath()
2383
2384         t0 = 0
2385         for subpath in self.subpaths:
2386             tf = t0+subpath.range()
2387             if params and tf>=params[0]:
2388                 # split this subpath
2389                 # determine the relevant splitting params
2390                 for i in range(len(params)):
2391                     if params[i]>tf: break
2392                 else:
2393                     i = len(params)
2394
2395                 splitsubpaths = subpath.split([x-t0 for x in params[:i]])
2396                 # handle first element, which may be None, separately
2397                 if splitsubpaths[0] is None:
2398                     if not np.subpaths:
2399                         result.append(None)
2400                     else:
2401                         result.append(np)
2402                         np = normpath()
2403                     splitsubpaths.pop(0)
2404
2405                 for sp in splitsubpaths[:-1]:
2406                     np.subpaths.append(sp)
2407                     result.append(np)
2408                     np = normpath()
2409
2410                 # handle last element which may be None, separately
2411                 if splitsubpaths:
2412                     if splitsubpaths[-1] is None:
2413                         if np.subpaths:
2414                             result.append(np)
2415                             np = normpath()
2416                     else:
2417                         np.subpaths.append(splitsubpaths[-1])
2418
2419                 params = params[i:]
2420             else:
2421                 # append whole subpath to current normpath
2422                 np.subpaths.append(subpath)
2423             t0 = tf
2424
2425         if np.subpaths:
2426             result.append(np)
2427         else:
2428             # mark split at the end of the normsubpath
2429             result.append(None)
2430
2431         return result
2432
2433     def tangent(self, param=None, arclen=None, length=None):
2434         """return tangent vector of path at either parameter value param
2435         or arc length arclen.
2436
2437         At discontinuities in the path, the limit from below is returned.
2438         If length is not None, the tangent vector will be scaled to
2439         the desired length.
2440         """
2441         sp, param = self._findsubpath(param, arclen)
2442         return sp.tangent(param, length)
2443
2444     def transform(self, trafo):
2445         """transform path according to trafo"""
2446         for sp in self.subpaths:
2447             sp.transform(trafo)
2448
2449     def transformed(self, trafo):
2450         """return path transformed according to trafo"""
2451         return normpath([sp.transformed(trafo) for sp in self.subpaths])
2452
2453     def trafo(self, param=None, arclen=None):
2454         """return transformation at either parameter value param or arc length arclen"""
2455         sp, param = self._findsubpath(param, arclen)
2456         return sp.trafo(param)
2457
2458     def outputPS(self, file):
2459         for sp in self.subpaths:
2460             sp.outputPS(file)
2461
2462     def outputPDF(self, file):
2463         for sp in self.subpaths:
2464             sp.outputPDF(file)