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