pyx/path.py

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