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     def at_pt(self, t):
1546         xt_pt = ( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t +
1547                   (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt          )*t*t +
1548                   (-3*self.x0_pt+3*self.x1_pt                      )*t +
1549                   self.x0_pt )
1550         yt_pt = ( (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t +
1551                   (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt          )*t*t +
1552                   (-3*self.y0_pt+3*self.y1_pt                      )*t +
1553                   self.y0_pt )
1554         return xt_pt, yt_pt
1555
1556     def bbox(self):
1557         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1558                           min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt),
1559                           max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1560                           max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt))
1561
1562     def begin_pt(self):
1563         return self.x0_pt, self.y0_pt
1564
1565     def curvradius_pt(self, param):
1566         xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) +
1567                  6 * (1-param)*param * (-self.x1_pt + self.x2_pt) +
1568                  3 * param*param * (-self.x2_pt + self.x3_pt) )
1569         ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) +
1570                  6 * (1-param)*param * (-self.y1_pt + self.y2_pt) +
1571                  3 * param*param * (-self.y2_pt + self.y3_pt) )
1572         xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) +
1573                   6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) )
1574         yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) +
1575                   6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) )
1576         return (xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot)
1577
1578     def end_pt(self):
1579         return self.x3_pt, self.y3_pt
1580
1581     def intersect(self, other, epsilon=1e-5):
1582         if isinstance(other, normline):
1583             return  _intersectnormcurves(self, 0, 1, other._normcurve(), 0, 1, epsilon)
1584         else:
1585             return  _intersectnormcurves(self, 0, 1, other, 0, 1, epsilon)
1586
1587     def isstraight(self, epsilon=1e-5):
1588         """check wheter the normcurve is approximately straight"""
1589
1590         # just check, whether the modulus of the difference between
1591         # the length of the control polygon
1592         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1593         # straight line between starting and ending point of the
1594         # normcurve (i.e. |P3-P1|) is smaller the epsilon
1595         return abs(math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt)+
1596                    math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt)+
1597                    math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt)-
1598                    math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt))<epsilon
1599
1600     def midpointsplit(self):
1601         """splits bpathitem at midpoint returning bpath with two bpathitems"""
1602
1603         # for efficiency reason, we do not use self.split(0.5)!
1604
1605         # first, we have to calculate the  midpoints between adjacent
1606         # control points
1607         x01_pt = 0.5*(self.x0_pt + self.x1_pt)
1608         y01_pt = 0.5*(self.y0_pt + self.y1_pt)
1609         x12_pt = 0.5*(self.x1_pt + self.x2_pt)
1610         y12_pt = 0.5*(self.y1_pt + self.y2_pt)
1611         x23_pt = 0.5*(self.x2_pt + self.x3_pt)
1612         y23_pt = 0.5*(self.y2_pt + self.y3_pt)
1613
1614         # In the next iterative step, we need the midpoints between 01 and 12
1615         # and between 12 and 23
1616         x01_12_pt = 0.5*(x01_pt + x12_pt)
1617         y01_12_pt = 0.5*(y01_pt + y12_pt)
1618         x12_23_pt = 0.5*(x12_pt + x23_pt)
1619         y12_23_pt = 0.5*(y12_pt + y23_pt)
1620
1621         # Finally the midpoint is given by
1622         xmidpoint_pt = 0.5*(x01_12_pt + x12_23_pt)
1623         ymidpoint_pt = 0.5*(y01_12_pt + y12_23_pt)
1624
1625         return (normcurve(self.x0_pt, self.y0_pt,
1626                           x01_pt, y01_pt,
1627                           x01_12_pt, y01_12_pt,
1628                           xmidpoint_pt, ymidpoint_pt),
1629                 normcurve(xmidpoint_pt, ymidpoint_pt,
1630                           x12_23_pt, y12_23_pt,
1631                           x23_pt, y23_pt,
1632                           self.x3_pt, self.y3_pt))
1633
1634     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1635         if xs_pt is None:
1636             xs_pt = self.x0_pt
1637         if ys_pt is None:
1638             ys_pt = self.y0_pt
1639         if xe_pt is None:
1640             xe_pt = self.x3_pt
1641         if ye_pt is None:
1642             ye_pt = self.y3_pt
1643         return normcurve(xs_pt, ys_pt,
1644                          self.x1_pt, self.y1_pt,
1645                          self.x2_pt, self.y2_pt,
1646                          xe_pt, ye_pt)
1647
1648     def reverse(self):
1649         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt = \
1650         self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1651
1652     def reversed(self):
1653         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)
1654
1655     def seglengths(self, paraminterval, epsilon=1e-5):
1656         """returns the list of segment line lengths (in pts) of the normcurve
1657            together with the length of the parameterinterval"""
1658
1659         # lower and upper bounds for the arclen
1660         lowerlen = math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1661         upperlen = ( math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt) +
1662                      math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt) +
1663                      math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt) )
1664
1665         # instead of isstraight method:
1666         if abs(upperlen-lowerlen)<epsilon:
1667             return [( 0.5*(upperlen+lowerlen), paraminterval )]
1668         else:
1669             a, b = self.midpointsplit()
1670             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
1671
1672     def split(self, params):
1673         """return list of normcurves corresponding to split at parameters"""
1674
1675         # first, we calculate the coefficients corresponding to our
1676         # original bezier curve. These represent a useful starting
1677         # point for the following change of the polynomial parameter
1678         a0x_pt = self.x0_pt
1679         a0y_pt = self.y0_pt
1680         a1x_pt = 3*(-self.x0_pt+self.x1_pt)
1681         a1y_pt = 3*(-self.y0_pt+self.y1_pt)
1682         a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt)
1683         a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt)
1684         a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt
1685         a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt
1686
1687         params = [0] + params + [1]
1688         result = []
1689
1690         for i in range(len(params)-1):
1691             t1 = params[i]
1692             dt = params[i+1]-t1
1693
1694             # [t1,t2] part
1695             #
1696             # the new coefficients of the [t1,t1+dt] part of the bezier curve
1697             # are then given by expanding
1698             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
1699             #  a3*(t1+dt*u)**3 in u, yielding
1700             #
1701             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
1702             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
1703             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
1704             #   a3*dt**3                         * u**3
1705             #
1706             # from this values we obtain the new control points by inversion
1707             #
1708             # XXX: we could do this more efficiently by reusing for
1709             # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
1710             # Bezier curve
1711
1712             x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1
1713             y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1
1714             x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt
1715             y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt
1716             x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt
1717             y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt
1718             x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt
1719             y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt
1720
1721             result.append(normcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1722
1723         return result
1724
1725     def tangentvector_pt(self, param):
1726         tvectx = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
1727                   2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt        )*param +
1728                     (-3*self.x0_pt+3*self.x1_pt                  ))
1729         tvecty = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
1730                   2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt        )*param +
1731                     (-3*self.y0_pt+3*self.y1_pt                  ))
1732         return (tvectx, tvecty)
1733
1734     def trafo(self, param):
1735         tx_pt, ty_pt = self.at_pt(param)
1736         tdx_pt, tdy_pt = self.tangentvector_pt(param)
1737         return trafo.translate_pt(tx_pt, ty_pt)*trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt)))
1738
1739     def transform(self, trafo):
1740         self.x0_pt, self.y0_pt = trafo._apply(self.x0_pt, self.y0_pt)
1741         self.x1_pt, self.y1_pt = trafo._apply(self.x1_pt, self.y1_pt)
1742         self.x2_pt, self.y2_pt = trafo._apply(self.x2_pt, self.y2_pt)
1743         self.x3_pt, self.y3_pt = trafo._apply(self.x3_pt, self.y3_pt)
1744
1745     def transformed(self, trafo):
1746         return normcurve(*(trafo._apply(self.x0_pt, self.y0_pt)+
1747                            trafo._apply(self.x1_pt, self.y1_pt)+
1748                            trafo._apply(self.x2_pt, self.y2_pt)+
1749                            trafo._apply(self.x3_pt, self.y3_pt)))
1750
1751     def outputPS(self, file):
1752         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))
1753
1754     def outputPDF(self, file):
1755         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))
1756
1757 #
1758 # normpaths are made up of normsubpaths, which represent connected line segments
1759 #
1760
1761 class normsubpath:
1762
1763     """sub path of a normalized path
1764
1765     A subpath consists of a list of normsubpathitems, i.e., lines and bcurves
1766     and can either be closed or not.
1767
1768     Some invariants, which have to be obeyed:
1769     - All normsubpathitems have to be longer than epsilon pts.
1770     - The last point of a normsubpathitem and the first point of the next
1771     element have to be equal.
1772     - When the path is closed, the last point of last normsubpathitem has
1773       to be equal to the first point of the first normsubpathitem.
1774     """
1775
1776     __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline"
1777
1778     def __init__(self, normsubpathitems=[], closed=0, epsilon=1e-5):
1779         self.epsilon = epsilon
1780         # If one or more items appended to the normsubpath have been
1781         # skipped (because their total length was shorter than
1782         # epsilon), we remember this fact by a line because we have to
1783         # take it properly into account when appending further subnormpathitems
1784         self.skippedline = None
1785
1786         self.normsubpathitems = []
1787         self.closed = 0
1788
1789         for normsubpathitem in normsubpathitems:
1790             self.append(normsubpathitem)
1791
1792         if closed:
1793             self.close()
1794
1795     def __str__(self):
1796         return "subpath(%s, [%s])" % (self.closed and "closed" or "open",
1797                                     ", ".join(map(str, self.normsubpathitems)))
1798
1799     def _distributeparams(self, params):
1800         """Creates a list tuples (normsubpathitem, itemparams),
1801         where itemparams are the parameter values corresponding
1802         to params in normsubpathitem. For the first normsubpathitem
1803         itemparams fulfil param < 1, for the last normsubpathitem
1804         itemparams fulfil 0 <= param, and for all other
1805         normsubpathitems itemparams fulfil 0 <= param < 1.
1806         Note that params have to be sorted.
1807         """
1808         if not self.normsubpathitems:
1809             if params:
1810                 raise PathException("Cannot select parameters for a short normsubpath")
1811             return []
1812         result = []
1813         paramindex = 0
1814         for index, normsubpathitem in enumerate(self.normsubpathitems[:-1]):
1815             oldparamindex = paramindex
1816             while paramindex < len(params) and params[paramindex] < index + 1:
1817                 paramindex += 1
1818             result.append((normsubpathitem, [param - index for param in params[oldparamindex: paramindex]]))
1819         result.append((self.normsubpathitems[-1],
1820                        [param - len(self.normsubpathitems) + 1 for param in params[paramindex:]]))
1821         return result
1822
1823     def _findnormsubpathitem(self, param):
1824         """Finds the normsubpathitem for the given parameter and
1825         returns a tuple containing this item and the parameter
1826         converted to the range of the item. An out of bound parameter
1827         is handled like in _distributeparams."""
1828         if not self.normsubpathitems:
1829             raise PathException("Cannot select parameters for a short normsubpath")
1830         if param > 0:
1831             index = int(param)
1832             if index > len(self.normsubpathitems) - 1:
1833                 index = len(self.normsubpathitems) - 1
1834         else:
1835             index = 0
1836         return self.normsubpathitems[index], param - index
1837
1838     def append(self, normsubpathitem):
1839         if self.closed:
1840             raise PathException("Cannot append to closed normsubpath")
1841
1842         if self.skippedline:
1843             xs_pt, ys_pt = self.skippedline.begin_pt()
1844         else:
1845             xs_pt, ys_pt = normsubpathitem.begin_pt()
1846         xe_pt, ye_pt = normsubpathitem.end_pt()
1847
1848         if (math.hypot(xe_pt-xs_pt, ye_pt-ys_pt) >= self.epsilon or
1849             normsubpathitem.arclen_pt(self.epsilon) >= self.epsilon):
1850             if self.skippedline:
1851                 normsubpathitem = normsubpathitem.modified(xs_pt=xs_pt, ys_pt=ys_pt)
1852             self.normsubpathitems.append(normsubpathitem)
1853             self.skippedline = None
1854         else:
1855             self.skippedline = normline(xs_pt, ys_pt, xe_pt, ye_pt)
1856
1857     def arclen_pt(self):
1858         """returns total arc length of normsubpath in pts with accuracy epsilon"""
1859         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normsubpathitems])
1860
1861     def _arclentoparam_pt(self, lengths):
1862         """returns [t, l] where t are parameter value(s) matching given length(s)
1863         and l is the total length of the normsubpath
1864         The parameters are with respect to the normsubpath: t in [0, self.range()]
1865         lengths that are < 0 give parameter 0"""
1866
1867         allarclen = 0
1868         allparams = [0] * len(lengths)
1869         rests = lengths[:]
1870
1871         for pitem in self.normsubpathitems:
1872             params, arclen = pitem._arclentoparam_pt(rests, self.epsilon)
1873             allarclen += arclen
1874             for i in range(len(rests)):
1875                 if rests[i] >= 0:
1876                     rests[i] -= arclen
1877                     allparams[i] += params[i]
1878
1879         return (allparams, allarclen)
1880
1881     def at_pt(self, param):
1882         """return coordinates in pts of sub path at parameter value param
1883
1884         The parameter param must be smaller or equal to the number of
1885         segments in the normpath, otherwise None is returned.
1886         """
1887         normsubpathitem, itemparam = self._findnormsubpathitem(param)
1888         return normsubpathitem.at_pt(itemparam)
1889
1890     def bbox(self):
1891         if self.normsubpathitems:
1892             abbox = self.normsubpathitems[0].bbox()
1893             for anormpathitem in self.normsubpathitems[1:]:
1894                 abbox += anormpathitem.bbox()
1895             return abbox
1896         else:
1897             return None
1898
1899     def begin_pt(self):
1900         return self.normsubpathitems[0].begin_pt()
1901
1902     def close(self):
1903         if self.closed:
1904             raise PathException("Cannot close already closed normsubpath")
1905         if not self.normsubpathitems:
1906             if self.skippedline is None:
1907                 raise PathException("Cannot close empty normsubpath")
1908             else:
1909                 raise PathException("Normsubpath too short, cannot be closed")
1910
1911         xs_pt, ys_pt = self.normsubpathitems[-1].end_pt()
1912         xe_pt, ye_pt = self.normsubpathitems[0].begin_pt()
1913         self.append(normline(xs_pt, ys_pt, xe_pt, ye_pt))
1914
1915         # the append might have left a skippedline, which we have to remove
1916         # from the end of the closed path
1917         if self.skippedline:
1918             self.normsubpathitems[-1] = self.normsubpathitems[-1].modified(xe_pt=self.skippedline.x1_pt,
1919                                                                            ye_pt=self.skippedline.y1_pt)
1920             self.skippedline = None
1921
1922         self.closed = 1
1923
1924     def curvradius_pt(self, param):
1925         normsubpathitem, itemparam = self._findnormsubpathitem(param)
1926         return normsubpathitem.curvradius_pt(itemparam)
1927
1928     def end_pt(self):
1929         return self.normsubpathitems[-1].end_pt()
1930
1931     def intersect(self, other):
1932         """intersect self with other normsubpath
1933
1934         returns a tuple of lists consisting of the parameter values
1935         of the intersection points of the corresponding normsubpath
1936
1937         """
1938         intersections_a = []
1939         intersections_b = []
1940         epsilon = min(self.epsilon, other.epsilon)
1941         # Intersect all subpaths of self with the subpaths of other, possibly including
1942         # one intersection point several times
1943         for t_a, pitem_a  in enumerate(self.normsubpathitems):
1944             for t_b, pitem_b in enumerate(other.normsubpathitems):
1945                 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon):
1946                     intersections_a.append(intersection_a + t_a)
1947                     intersections_b.append(intersection_b + t_b)
1948
1949         # although intersectipns_a are sorted for the different normsubpathitems,
1950         # within a normsubpathitem, the ordering has to be ensured separately:
1951         intersections = zip(intersections_a, intersections_b)
1952         intersections.sort()
1953         intersections_a = [a for a, b in intersections]
1954         intersections_b = [b for a, b in intersections]
1955
1956         # for symmetry reasons we enumerate intersections_a as well, although
1957         # they are already sorted (note we do not need to sort intersections_a)
1958         intersections_a = zip(intersections_a, range(len(intersections_a)))
1959         intersections_b = zip(intersections_b, range(len(intersections_b)))
1960         intersections_b.sort()
1961
1962         # now we search for intersections points which are closer together than epsilon
1963         # This task is handled by the following function
1964         def closepoints(normsubpath, intersections):
1965             split = normsubpath.split([intersection for intersection, index in intersections])
1966             result = []
1967             if normsubpath.closed:
1968                 # note that the number of segments of a closed path is off by one
1969                 # compared to an open path
1970                 i = 0
1971                 while i < len(split):
1972                     splitnormsubpath = split[i]
1973                     j = i
1974                     while splitnormsubpath.isshort():
1975                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
1976                         if ip1<ip2:
1977                             result.append((ip1, ip2))
1978                         else:
1979                             result.append((ip2, ip1))
1980                         j += 1
1981                         if j == len(split):
1982                             j = 0
1983                         if j < len(split):
1984                             splitnormsubpath = splitnormsubpath.joined(split[j])
1985                         else:
1986                             break
1987                     i += 1
1988             else:
1989                 i = 1
1990                 while i < len(split)-1:
1991                     splitnormsubpath = split[i]
1992                     j = i
1993                     while splitnormsubpath.isshort():
1994                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
1995                         if ip1<ip2:
1996                             result.append((ip1, ip2))
1997                         else:
1998                             result.append((ip2, ip1))
1999                         j += 1
2000                         if j < len(split)-1:
2001                             splitnormsubpath.join(split[j])
2002                         else:
2003                             break
2004                     i += 1
2005             return result
2006
2007         closepoints_a = closepoints(self, intersections_a)
2008         closepoints_b = closepoints(other, intersections_b)
2009
2010         # map intersection point to lowest point which is equivalent to the
2011         # point
2012         equivalentpoints = list(range(len(intersections_a)))
2013
2014         for closepoint_a in closepoints_a:
2015             for closepoint_b in closepoints_b:
2016                 if closepoint_a == closepoint_b:
2017                     for i in range(closepoint_a[1], len(equivalentpoints)):
2018                         if equivalentpoints[i] == closepoint_a[1]:
2019                             equivalentpoints[i] = closepoint_a[0]
2020
2021         # determine the remaining intersection points
2022         intersectionpoints = {}
2023         for point in equivalentpoints:
2024             intersectionpoints[point] = 1
2025
2026         # build result
2027         result = []
2028         for point in intersectionpoints.keys():
2029             for intersection_a, index_a in intersections_a:
2030                 if index_a == point:
2031                     result_a = intersection_a
2032             for intersection_b, index_b in intersections_b:
2033                 if index_b == point:
2034                     result_b = intersection_b
2035             result.append((result_a, result_b))
2036         # note that the result is sorted in a, since we sorted
2037         # intersections_a in the very beginning
2038
2039         return [x for x, y in result], [y for x, y in result]
2040
2041     def isshort(self):
2042         """return whether the subnormpath is shorter than epsilon"""
2043         return not self.normsubpathitems
2044
2045     def join(self, other):
2046         for othernormpathitem in other.normsubpathitems:
2047             self.append(othernormpathitem)
2048         if other.skippedline is not None:
2049             self.append(other.skippedline)
2050
2051     def joined(self, other):
2052         result = normsubpath(self.normsubpathitems, self.closed, self.epsilon)
2053         result.skippedline = self.skippedline
2054         result.join(other)
2055         return result
2056
2057     def range(self):
2058         """return maximal parameter value, i.e. number of line/curve segments"""
2059         return len(self.normsubpathitems)
2060
2061     def reverse(self):
2062         self.normsubpathitems.reverse()
2063         for npitem in self.normsubpathitems:
2064             npitem.reverse()
2065
2066     def reversed(self):
2067         nnormpathitems = []
2068         for i in range(len(self.normsubpathitems)):
2069             nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed())
2070         return normsubpath(nnormpathitems, self.closed)
2071
2072     def split(self, params):
2073         """split normsubpath at list of parameter values params and return list
2074         of normsubpaths
2075
2076         The parameter list params has to be sorted. Note that each element of
2077         the resulting list is an open normsubpath.
2078         """
2079
2080         result = [normsubpath(epsilon=self.epsilon)]
2081
2082         for normsubpathitem, itemparams in self._distributeparams(params):
2083             splititems = normsubpathitem.split(itemparams)
2084             result[-1].append(splititems[0])
2085             result.extend([normsubpath([splititem], epsilon=self.epsilon) for splititem in splititems[1:]])
2086
2087         if self.closed:
2088             if params:
2089                 # join last and first segment together if the normsubpath was originally closed and it has been split
2090                 result[-1].normsubpathitems.extend(result[0].normsubpathitems)
2091                 result = result[-1:] + result[1:-1]
2092             else:
2093                 # otherwise just close the copied path again
2094                 result[0].close()
2095         return result
2096
2097     def tangent(self, param, length=None):
2098         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2099         tx_pt, ty_pt = normsubpathitem.at_pt(itemparam)
2100         tdx_pt, tdy_pt = normsubpathitem.tangentvector_pt(itemparam)
2101         if length is not None:
2102             sfactor = unit.topt(length)/math.hypot(tdx_pt, tdy_pt)
2103             tdx_pt *= sfactor
2104             tdy_pt *= sfactor
2105         return line_pt(tx_pt, ty_pt, tx_pt+tdx_pt, ty_pt+tdy_pt)
2106
2107     def trafo(self, param):
2108         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2109         return normsubpathitem.trafo(itemparam)
2110
2111     def transform(self, trafo):
2112         """transform sub path according to trafo"""
2113         # note that we have to rebuild the path again since normsubpathitems
2114         # may become shorter than epsilon and/or skippedline may become
2115         # longer than epsilon
2116         normsubpathitems = self.normsubpathitems
2117         closed = self.closed
2118         skippedline = self.skippedline
2119         self.normsubpathitems = []
2120         self.closed = 0
2121         self.skippedline = None
2122         for pitem in normsubpathitems:
2123             self.append(pitem.transformed(trafo))
2124         if closed:
2125             self.close()
2126         elif skippedline is not None:
2127             self.append(skippedline.transformed(trafo))
2128
2129     def transformed(self, trafo):
2130         """return sub path transformed according to trafo"""
2131         nnormsubpath = normsubpath(epsilon=self.epsilon)
2132         for pitem in self.normsubpathitems:
2133             nnormsubpath.append(pitem.transformed(trafo))
2134         if self.closed:
2135             nnormsubpath.close()
2136         elif self.skippedline is not None:
2137             nnormsubpath.append(skippedline.transformed(trafo))
2138         return nnormsubpath
2139
2140     def outputPS(self, file):
2141         # if the normsubpath is closed, we must not output a normline at
2142         # the end
2143         if not self.normsubpathitems:
2144             return
2145         if self.closed and isinstance(self.normsubpathitems[-1], normline):
2146             normsubpathitems = self.normsubpathitems[:-1]
2147         else:
2148             normsubpathitems = self.normsubpathitems
2149         if normsubpathitems:
2150             file.write("%g %g moveto\n" % self.begin_pt())
2151             for anormpathitem in normsubpathitems:
2152                 anormpathitem.outputPS(file)
2153         if self.closed:
2154             file.write("closepath\n")
2155
2156     def outputPDF(self, file):
2157         # if the normsubpath is closed, we must not output a normline at
2158         # the end
2159         if not self.normsubpathitems:
2160             return
2161         if self.closed and isinstance(self.normsubpathitems[-1], normline):
2162             normsubpathitems = self.normsubpathitems[:-1]
2163         else:
2164             normsubpathitems = self.normsubpathitems
2165         if normsubpathitems:
2166             file.write("%f %f m\n" % self.begin_pt())
2167             for anormpathitem in normsubpathitems:
2168                 anormpathitem.outputPDF(file)
2169         if self.closed:
2170             file.write("h\n")
2171
2172 #
2173 # the normpath class
2174 #
2175
2176 class normpath(path):
2177
2178     """normalized path
2179
2180     A normalized path consists of a list of normalized sub paths.
2181
2182     """
2183
2184     def __init__(self, arg=[], epsilon=1e-5):
2185         """ construct a normpath from another normpath passed as arg,
2186         a path or a list of normsubpaths. An accuracy of epsilon pts
2187         is used for numerical calculations.
2188         """
2189
2190         if isinstance(arg, normpath):
2191             self.subpaths = arg.subpaths[:]
2192             return
2193         elif isinstance(arg, path):
2194             # split path in sub paths
2195             self.subpaths = []
2196             currentsubpathitems = []
2197             context = _pathcontext()
2198             for pitem in arg.path:
2199                 for npitem in pitem._normalized(context):
2200                     if isinstance(npitem, moveto_pt):
2201                         if currentsubpathitems:
2202                             # append open sub path
2203                             self.subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
2204                         # start new sub path
2205                         currentsubpathitems = []
2206                     elif isinstance(npitem, closepath):
2207                         if currentsubpathitems:
2208                             # append closed sub path
2209                             currentsubpathitems.append(normline(context.currentpoint[0], context.currentpoint[1],
2210                                                               context.currentsubpath[0], context.currentsubpath[1]))
2211                         self.subpaths.append(normsubpath(currentsubpathitems, 1, epsilon))
2212                         currentsubpathitems = []
2213                     else:
2214                         currentsubpathitems.append(npitem)
2215                 pitem._updatecontext(context)
2216
2217             if currentsubpathitems:
2218                 # append open sub path
2219                 self.subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
2220         else:
2221             # we expect a list of normsubpaths
2222             self.subpaths = list(arg)
2223
2224     def __add__(self, other):
2225         result = normpath(other)
2226         result.subpaths = self.subpaths + result.subpaths
2227         return result
2228
2229     def __getitem__(self, i):
2230         return self.subpaths[i]
2231
2232     def __iadd__(self, other):
2233         self.subpaths += normpath(other).subpaths
2234         return self
2235
2236     def __nonzero__(self):
2237         return len(self.subpaths)>0
2238
2239     def __str__(self):
2240         return "normpath(%s)" % ", ".join(map(str, self.subpaths))
2241
2242     def _findsubpath(self, param, arclen):
2243         """return a tuple (subpath, rparam), where subpath is the subpath
2244         containing the position specified by either param or arclen and rparam
2245         is the corresponding parameter value in this subpath.
2246         """
2247
2248         if param is not None and arclen is not None:
2249             raise PathException("either param or arclen has to be specified, but not both")
2250
2251         if param is not None:
2252             try:
2253                 subpath, param = param
2254             except TypeError:
2255                 # determine subpath from param
2256                 spt = 0
2257                 for sp in self.subpaths:
2258                     sprange = sp.range()
2259                     if spt <= param < sprange+spt:
2260                         return sp, param-spt
2261                     spt += sprange
2262                 raise PathException("parameter value out of range")
2263             try:
2264                 return self.subpaths[subpath], param
2265             except IndexError:
2266                 raise PathException("subpath index out of range")
2267
2268         # we have been passed an arclen (or a tuple (subpath, arclen))
2269         try:
2270             subpath, arclen = arclen
2271         except:
2272             # determine subpath from arclen
2273             param = self.arclentoparam(arclen)
2274             for sp in self.subpaths:
2275                 sprange = sp.range()
2276                 if spt < param <= sprange+spt:
2277                     return sp, param-spt
2278                 spt += sprange
2279             raise PathException("parameter value out of range")
2280
2281         try:
2282             sp = self.subpaths[subpath]
2283         except IndexError:
2284             raise PathException("subpath index out of range")
2285         return sp, sp.arclentoparam(arclen)
2286
2287     def append(self, normsubpath):
2288         self.subpaths.append(normsubpath)
2289
2290     def extend(self, normsubpaths):
2291         self.subpaths.extend(normsubpaths)
2292
2293
2294     def arclen_pt(self):
2295         """returns total arc length of normpath in pts"""
2296         return sum([sp.arclen_pt() for sp in self.subpaths])
2297
2298     def arclen(self):
2299         """returns total arc length of normpath"""
2300         return self.arclen_pt() * unit.t_pt
2301
2302     def arclentoparam_pt(self, lengths):
2303         rests = lengths[:]
2304         allparams = [0] * len(lengths)
2305
2306         for sp in self.subpaths:
2307             # we need arclen for knowing when all the parameters are done
2308             # for lengths that are done: rests[i] is negative
2309             # sp._arclentoparam has to ignore such lengths
2310             params, arclen = sp._arclentoparam_pt(rests)
2311             finis = 0 # number of lengths that are done
2312             for i in range(len(rests)):
2313                 if rests[i] >= 0:
2314                   rests[i] -= arclen
2315                   allparams[i] += params[i]
2316                 else:
2317                     finis += 1
2318             if finis == len(rests): break
2319
2320         if len(lengths) == 1: allparams = allparams[0]
2321         return allparams
2322
2323     def arclentoparam(self, lengths):
2324         """returns the parameter value(s) matching the given length(s)
2325
2326         all given lengths must be positive.
2327         A length greater than the total arclength will give self.range()
2328         """
2329         l = [unit.topt(length) for length in helper.ensuresequence(lengths)]
2330         return self.arclentoparam_pt(l)
2331
2332     def at_pt(self, param=None, arclen=None):
2333         """return coordinates in pts of path at either parameter value param
2334         or arc length arclen.
2335
2336         At discontinuities in the path, the limit from below is returned.
2337         """
2338         sp, param = self._findsubpath(param, arclen)
2339         return sp.at_pt(param)
2340
2341     def at(self, param=None, arclen=None):
2342         """return coordinates of path at either parameter value param
2343         or arc length arclen.
2344
2345         At discontinuities in the path, the limit from below is returned
2346         """
2347         x, y = self.at_pt(param, arclen)
2348         return x * unit.t_pt, y * unit.t_pt
2349
2350     def bbox(self):
2351         abbox = None
2352         for sp in self.subpaths:
2353             nbbox =  sp.bbox()
2354             if abbox is None:
2355                 abbox = nbbox
2356             elif nbbox:
2357                 abbox += nbbox
2358         return abbox
2359
2360     def begin_pt(self):
2361         """return coordinates of first point of first subpath in path (in pts)"""
2362         if self.subpaths:
2363             return self.subpaths[0].begin_pt()
2364         else:
2365             raise PathException("cannot return first point of empty path")
2366
2367     def begin(self):
2368         """return coordinates of first point of first subpath in path"""
2369         x_pt, y_pt = self.begin_pt()
2370         return x_pt * unit.t_pt, y_pt * unit.t_pt
2371
2372     def curvradius_pt(self, param=None, arclen=None):
2373         """Returns the curvature radius in pts (or None if infinite)
2374         at parameter param or arc length arclen.  This is the inverse
2375         of the curvature at this parameter
2376
2377         Please note that this radius can be negative or positive,
2378         depending on the sign of the curvature"""
2379         sp, param = self._findsubpath(param, arclen)
2380         return sp.curvradius_pt(param)
2381
2382     def curvradius(self, param=None, arclen=None):
2383         """Returns the curvature radius (or None if infinite) at
2384         parameter param or arc length arclen.  This is the inverse of
2385         the curvature at this parameter
2386
2387         Please note that this radius can be negative or positive,
2388         depending on the sign of the curvature"""
2389         radius = self.curvradius_pt(param, arclen)
2390         if radius is not None:
2391             radius = radius * unit.t_pt
2392         return radius
2393
2394     def end_pt(self):
2395         """return coordinates of last point of last subpath in path (in pts)"""
2396         if self.subpaths:
2397             return self.subpaths[-1].end_pt()
2398         else:
2399             raise PathException("cannot return last point of empty path")
2400
2401     def end(self):
2402         """return coordinates of last point of last subpath in path"""
2403         x_pt, y_pt = self.end_pt()
2404         return x_pt * unit.t_pt, y_pt * unit.t_pt
2405
2406     def join(self, other):
2407         if not self.subpaths:
2408             raise PathException("cannot join to end of empty path")
2409         if self.subpaths[-1].closed:
2410             raise PathException("cannot join to end of closed sub path")
2411         other = normpath(other)
2412         if not other.subpaths:
2413             raise PathException("cannot join empty path")
2414
2415         self.subpaths[-1].normsubpathitems += other.subpaths[0].normsubpathitems
2416         self.subpaths += other.subpaths[1:]
2417
2418     def joined(self, other):
2419         # NOTE we skip a deep copy for performance reasons
2420         result = normpath(self.subpaths)
2421         result.join(other)
2422         return result
2423
2424     def intersect(self, other):
2425         """intersect self with other path
2426
2427         returns a tuple of lists consisting of the parameter values
2428         of the intersection points of the corresponding normpath
2429
2430         """
2431         if not isinstance(other, normpath):
2432             other = normpath(other)
2433
2434         # here we build up the result
2435         intersections = ([], [])
2436
2437         # Intersect all subpaths of self with the subpaths of
2438         # other.
2439         for ia, sp_a in enumerate(self.subpaths):
2440             for ib, sp_b in enumerate(other.subpaths):
2441                 for intersection in zip(*sp_a.intersect(sp_b)):
2442                     intersections[0].append((ia, intersection[0]))
2443                     intersections[1].append((ib, intersection[1]))
2444         return intersections
2445
2446     def range(self):
2447         """return maximal value for parameter value param"""
2448         return sum([sp.range() for sp in self.subpaths])
2449
2450     def reverse(self):
2451         """reverse path"""
2452         self.subpaths.reverse()
2453         for sp in self.subpaths:
2454             sp.reverse()
2455
2456     def reversed(self):
2457         """return reversed path"""
2458         nnormpath = normpath()
2459         for i in range(len(self.subpaths)):
2460             nnormpath.subpaths.append(self.subpaths[-(i+1)].reversed())
2461         return nnormpath
2462
2463     def split(self, params):
2464         """split path at parameter values params
2465
2466         Note that the parameter list has to be sorted.
2467
2468         """
2469
2470         # check whether parameter list is really sorted
2471         sortedparams = list(params)
2472         sortedparams.sort()
2473         if sortedparams != list(params):
2474             raise ValueError("split parameter list params has to be sorted")
2475
2476         # convert to tuple
2477         tparams = []
2478         for param in params:
2479             tparams.append(self._findsubpath(param, None))
2480
2481         # we construct this list of normpaths
2482         result = []
2483
2484         # the currently built up normpath
2485         np = normpath()
2486
2487         for subpath in self.subpaths:
2488             splitsubpaths = subpath.split([param for sp, param in tparams if sp is subpath])
2489             np.subpaths.append(splitsubpaths[0])
2490             for sp in splitsubpaths[1:]:
2491                 result.append(np)
2492                 np = normpath([sp])
2493
2494         result.append(np)
2495         return result
2496
2497     def tangent(self, param=None, arclen=None, length=None):
2498         """return tangent vector of path at either parameter value param
2499         or arc length arclen.
2500
2501         At discontinuities in the path, the limit from below is returned.
2502         If length is not None, the tangent vector will be scaled to
2503         the desired length.
2504         """
2505         sp, param = self._findsubpath(param, arclen)
2506         return sp.tangent(param, length)
2507
2508     def transform(self, trafo):
2509         """transform path according to trafo"""
2510         for sp in self.subpaths:
2511             sp.transform(trafo)
2512
2513     def transformed(self, trafo):
2514         """return path transformed according to trafo"""
2515         return normpath([sp.transformed(trafo) for sp in self.subpaths])
2516
2517     def trafo(self, param=None, arclen=None):
2518         """return transformation at either parameter value param or arc length arclen"""
2519         sp, param = self._findsubpath(param, arclen)
2520         return sp.trafo(param)
2521
2522     def outputPS(self, file):
2523         for sp in self.subpaths:
2524             sp.outputPS(file)
2525
2526     def outputPDF(self, file):
2527         for sp in self.subpaths:
2528             sp.outputPDF(file)