pyx/path.py

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