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 joined(self, other):
1050         """return path consisting of self and other joined together"""
1051         return self.normpath().joined(other)
1052
1053     # << operator also designates joining
1054     __lshift__ = joined
1055
1056     def intersect(self, other):
1057         """intersect normpath corresponding to self with other path"""
1058         return self.normpath().intersect(other)
1059
1060     def normpath(self, epsilon=None):
1061         """converts the path into a normpath"""
1062         # use global epsilon if it is has not been specified
1063         if epsilon is None:
1064             epsilon = _epsilon
1065         # split path in sub paths
1066         subpaths = []
1067         currentsubpathitems = []
1068         context = _pathcontext()
1069         for pitem in self.path:
1070             for npitem in pitem._normalized(context):
1071                 if isinstance(npitem, moveto_pt):
1072                     if currentsubpathitems:
1073                         # append open sub path
1074                         subpaths.append(normsubpath(currentsubpathitems, closed=0, epsilon=epsilon))
1075                     # start new sub path
1076                     currentsubpathitems = []
1077                 elif isinstance(npitem, closepath):
1078                     if currentsubpathitems:
1079                         # append closed sub path
1080                         currentsubpathitems.append(normline(context.currentpoint[0], context.currentpoint[1],
1081                                                             context.currentsubpath[0], context.currentsubpath[1]))
1082                     subpaths.append(normsubpath(currentsubpathitems, closed=1, epsilon=epsilon))
1083                     currentsubpathitems = []
1084                 else:
1085                     currentsubpathitems.append(npitem)
1086             pitem._updatecontext(context)
1087
1088         if currentsubpathitems:
1089             # append open sub path
1090             subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
1091         return normpath(subpaths)
1092
1093     def range(self):
1094         """return maximal value for parameter value t for corr. normpath"""
1095         return self.normpath().range()
1096
1097     def reversed(self):
1098         """return reversed path"""
1099         return self.normpath().reversed()
1100
1101     def split(self, params):
1102         """return corresponding normpaths split at parameter values params"""
1103         return self.normpath().split(params)
1104
1105     def tangent(self, param=None, arclen=None, length=None):
1106         """return tangent vector of path at either parameter value param
1107         or arc length arclen.
1108
1109         At discontinuities in the path, the limit from below is returned.
1110         If length is not None, the tangent vector will be scaled to
1111         the desired length.
1112         """
1113         return self.normpath().tangent(param, arclen, length)
1114
1115     def trafo(self, param=None, arclen=None):
1116         """return transformation at either parameter value param or arc length arclen"""
1117         return self.normpath().trafo(param, arclen)
1118
1119     def transformed(self, trafo):
1120         """return transformed path"""
1121         return self.normpath().transformed(trafo)
1122
1123     def outputPS(self, file):
1124         if not (isinstance(self.path[0], moveto_pt) or
1125                 isinstance(self.path[0], arc_pt) or
1126                 isinstance(self.path[0], arcn_pt)):
1127             raise PathException("first path element must be either moveto, arc, or arcn")
1128         for pitem in self.path:
1129             pitem.outputPS(file)
1130
1131     def outputPDF(self, file):
1132         if not (isinstance(self.path[0], moveto_pt) or
1133                 isinstance(self.path[0], arc_pt) or
1134                 isinstance(self.path[0], arcn_pt)):
1135             raise PathException("first path element must be either moveto, arc, or arcn")
1136         # PDF practically only supports normsubpathitems
1137         context = _pathcontext()
1138         for pitem in self.path:
1139             for npitem in pitem._normalized(context):
1140                 npitem.outputPDF(file)
1141             pitem._updatecontext(context)
1142
1143 ################################################################################
1144 # some special kinds of path, again in two variants
1145 ################################################################################
1146
1147 class line_pt(path):
1148
1149    """straight line from (x1_pt, y1_pt) to (x2_pt, y2_pt) (coordinates in pts)"""
1150
1151    def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt):
1152        path.__init__(self, moveto_pt(x1_pt, y1_pt), lineto_pt(x2_pt, y2_pt))
1153
1154
1155 class curve_pt(path):
1156
1157    """Bezier curve with control points (x0_pt, y1_pt),..., (x3_pt, y3_pt)
1158    (coordinates in pts)"""
1159
1160    def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1161        path.__init__(self,
1162                      moveto_pt(x0_pt, y0_pt),
1163                      curveto_pt(x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1164
1165
1166 class rect_pt(path):
1167
1168    """rectangle at position (x,y) with width and height (coordinates in pts)"""
1169
1170    def __init__(self, x, y, width, height):
1171        path.__init__(self, moveto_pt(x, y),
1172                            lineto_pt(x+width, y),
1173                            lineto_pt(x+width, y+height),
1174                            lineto_pt(x, y+height),
1175                            closepath())
1176
1177
1178 class circle_pt(path):
1179
1180    """circle with center (x,y) and radius"""
1181
1182    def __init__(self, x, y, radius):
1183        path.__init__(self, arc_pt(x, y, radius, 0, 360),
1184                      closepath())
1185
1186
1187 class line(line_pt):
1188
1189    """straight line from (x1, y1) to (x2, y2)"""
1190
1191    def __init__(self, x1, y1, x2, y2):
1192        line_pt.__init__(self,
1193                         unit.topt(x1), unit.topt(y1),
1194                         unit.topt(x2), unit.topt(y2))
1195
1196
1197 class curve(curve_pt):
1198
1199    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
1200
1201    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1202        curve_pt.__init__(self,
1203                          unit.topt(x0), unit.topt(y0),
1204                          unit.topt(x1), unit.topt(y1),
1205                          unit.topt(x2), unit.topt(y2),
1206                          unit.topt(x3), unit.topt(y3))
1207
1208
1209 class rect(rect_pt):
1210
1211    """rectangle at position (x,y) with width and height"""
1212
1213    def __init__(self, x, y, width, height):
1214        rect_pt.__init__(self,
1215                         unit.topt(x), unit.topt(y),
1216                         unit.topt(width), unit.topt(height))
1217
1218
1219 class circle(circle_pt):
1220
1221    """circle with center (x,y) and radius"""
1222
1223    def __init__(self, x, y, radius):
1224        circle_pt.__init__(self,
1225                         unit.topt(x), unit.topt(y),
1226                         unit.topt(radius))
1227
1228 ################################################################################
1229 # normpath and corresponding classes
1230 ################################################################################
1231
1232 # two helper functions for the intersection of normsubpathitems
1233
1234 def _intersectnormcurves(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
1235     """intersect two bpathitems
1236
1237     a and b are bpathitems with parameter ranges [a_t0, a_t1],
1238     respectively [b_t0, b_t1].
1239     epsilon determines when the bpathitems are assumed to be straight
1240
1241     """
1242
1243     # intersection of bboxes is a necessary criterium for intersection
1244     if not a.bbox().intersects(b.bbox()): return []
1245
1246     if not a.isstraight(epsilon):
1247         (aa, ab) = a.midpointsplit()
1248         a_tm = 0.5*(a_t0+a_t1)
1249
1250         if not b.isstraight(epsilon):
1251             (ba, bb) = b.midpointsplit()
1252             b_tm = 0.5*(b_t0+b_t1)
1253
1254             return ( _intersectnormcurves(aa, a_t0, a_tm,
1255                                        ba, b_t0, b_tm, epsilon) +
1256                      _intersectnormcurves(ab, a_tm, a_t1,
1257                                        ba, b_t0, b_tm, epsilon) +
1258                      _intersectnormcurves(aa, a_t0, a_tm,
1259                                        bb, b_tm, b_t1, epsilon) +
1260                      _intersectnormcurves(ab, a_tm, a_t1,
1261                                        bb, b_tm, b_t1, epsilon) )
1262         else:
1263             return ( _intersectnormcurves(aa, a_t0, a_tm,
1264                                        b, b_t0, b_t1, epsilon) +
1265                      _intersectnormcurves(ab, a_tm, a_t1,
1266                                        b, b_t0, b_t1, epsilon) )
1267     else:
1268         if not b.isstraight(epsilon):
1269             (ba, bb) = b.midpointsplit()
1270             b_tm = 0.5*(b_t0+b_t1)
1271
1272             return  ( _intersectnormcurves(a, a_t0, a_t1,
1273                                        ba, b_t0, b_tm, epsilon) +
1274                       _intersectnormcurves(a, a_t0, a_t1,
1275                                        bb, b_tm, b_t1, epsilon) )
1276         else:
1277             # no more subdivisions of either a or b
1278             # => try to intersect a and b as straight line segments
1279
1280             a_deltax = a.x3_pt - a.x0_pt
1281             a_deltay = a.y3_pt - a.y0_pt
1282             b_deltax = b.x3_pt - b.x0_pt
1283             b_deltay = b.y3_pt - b.y0_pt
1284
1285             det = b_deltax*a_deltay - b_deltay*a_deltax
1286
1287             ba_deltax0_pt = b.x0_pt - a.x0_pt
1288             ba_deltay0_pt = b.y0_pt - a.y0_pt
1289
1290             try:
1291                 a_t = ( b_deltax*ba_deltay0_pt - b_deltay*ba_deltax0_pt)/det
1292                 b_t = ( a_deltax*ba_deltay0_pt - a_deltay*ba_deltax0_pt)/det
1293             except ArithmeticError:
1294                 return []
1295
1296             # check for intersections out of bound
1297             if not (0<=a_t<=1 and 0<=b_t<=1): return []
1298
1299             # return rescaled parameters of the intersection
1300             return [ ( a_t0 + a_t * (a_t1 - a_t0),
1301                        b_t0 + b_t * (b_t1 - b_t0) ) ]
1302
1303
1304 def _intersectnormlines(a, b):
1305     """return one-element list constisting either of tuple of
1306     parameters of the intersection point of the two normlines a and b
1307     or empty list if both normlines do not intersect each other"""
1308
1309     a_deltax_pt = a.x1_pt - a.x0_pt
1310     a_deltay_pt = a.y1_pt - a.y0_pt
1311     b_deltax_pt = b.x1_pt - b.x0_pt
1312     b_deltay_pt = b.y1_pt - b.y0_pt
1313
1314     det = 1.0*(b_deltax_pt * a_deltay_pt - b_deltay_pt * a_deltax_pt)
1315
1316     ba_deltax0_pt = b.x0_pt - a.x0_pt
1317     ba_deltay0_pt = b.y0_pt - a.y0_pt
1318
1319     try:
1320         a_t = ( b_deltax_pt * ba_deltay0_pt - b_deltay_pt * ba_deltax0_pt)/det
1321         b_t = ( a_deltax_pt * ba_deltay0_pt - a_deltay_pt * ba_deltax0_pt)/det
1322     except ArithmeticError:
1323         return []
1324
1325     # check for intersections out of bound
1326     if not (0<=a_t<=1 and 0<=b_t<=1): return []
1327
1328     # return parameters of the intersection
1329     return [( a_t, b_t)]
1330
1331 #
1332 # normsubpathitem: normalized element
1333 #
1334
1335 class normsubpathitem:
1336
1337     """element of a normalized sub path"""
1338
1339     def at_pt(self, t):
1340         """returns coordinates of point in pts at parameter t (0<=t<=1) """
1341         pass
1342
1343     def arclen_pt(self, epsilon=1e-5):
1344         """returns arc length of normsubpathitem in pts with given accuracy epsilon"""
1345         pass
1346
1347     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1348         """returns tuple (t,l) with
1349           t the parameter where the arclen of normsubpathitem is length and
1350           l the total arclen
1351
1352         length:  length (in pts) to find the parameter for
1353         epsilon: epsilon controls the accuracy for calculation of the
1354                  length of the Bezier elements
1355         """
1356         # Note: _arclentoparam returns both, parameters and total lengths
1357         # while  arclentoparam returns only parameters
1358         pass
1359
1360     def bbox(self):
1361         """return bounding box of normsubpathitem"""
1362         pass
1363
1364     def curvradius_pt(self, param):
1365         """Returns the curvature radius in pts at parameter param.
1366         This is the inverse of the curvature at this parameter
1367
1368         Please note that this radius can be negative or positive,
1369         depending on the sign of the curvature"""
1370         pass
1371
1372     def intersect(self, other, epsilon=1e-5):
1373         """intersect self with other normsubpathitem"""
1374         pass
1375
1376     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1377         """returns a (new) modified normpath with different start and
1378         end points as provided"""
1379         pass
1380
1381     def reversed(self):
1382         """return reversed normsubpathitem"""
1383         pass
1384
1385     def split(self, parameters):
1386         """splits normsubpathitem
1387
1388         parameters: list of parameter values (0<=t<=1) at which to split
1389
1390         returns None or list of tuple of normsubpathitems corresponding to
1391         the orginal normsubpathitem.
1392
1393         """
1394         pass
1395
1396     def tangentvector_pt(self, t):
1397         """returns tangent vector of normsubpathitem in pts at parameter t (0<=t<=1)"""
1398         pass
1399
1400     def transformed(self, trafo):
1401         """return transformed normsubpathitem according to trafo"""
1402         pass
1403
1404     def outputPS(self, file):
1405         """write PS code corresponding to normsubpathitem to file"""
1406         pass
1407
1408     def outputPS(self, file):
1409         """write PDF code corresponding to normsubpathitem to file"""
1410         pass
1411
1412 #
1413 # there are only two normsubpathitems: normline and normcurve
1414 #
1415
1416 class normline(normsubpathitem):
1417
1418     """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)"""
1419
1420     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt"
1421
1422     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt):
1423          self.x0_pt = x0_pt
1424          self.y0_pt = y0_pt
1425          self.x1_pt = x1_pt
1426          self.y1_pt = y1_pt
1427
1428     def __str__(self):
1429         return "normline(%g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt)
1430
1431     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1432         l = self.arclen_pt(epsilon)
1433         return ([max(min(1.0 * length / l, 1), 0) for length in lengths], l)
1434
1435     def _normcurve(self):
1436         """ return self as equivalent normcurve """
1437         xa_pt = self.x0_pt+(self.x1_pt-self.x0_pt)/3.0
1438         ya_pt = self.y0_pt+(self.y1_pt-self.y0_pt)/3.0
1439         xb_pt = self.x0_pt+2.0*(self.x1_pt-self.x0_pt)/3.0
1440         yb_pt = self.y0_pt+2.0*(self.y1_pt-self.y0_pt)/3.0
1441         return normcurve(self.x0_pt, self.y0_pt, xa_pt, ya_pt, xb_pt, yb_pt, self.x1_pt, self.y1_pt)
1442
1443     def arclen_pt(self,  epsilon=1e-5):
1444         return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
1445
1446     def at_pt(self, t):
1447         return self.x0_pt+(self.x1_pt-self.x0_pt)*t, self.y0_pt+(self.y1_pt-self.y0_pt)*t
1448
1449     def at(self, t):
1450         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
1451
1452     def bbox(self):
1453         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt), min(self.y0_pt, self.y1_pt),
1454                           max(self.x0_pt, self.x1_pt), max(self.y0_pt, self.y1_pt))
1455
1456     def begin_pt(self):
1457         return self.x0_pt, self.y0_pt
1458
1459     def begin(self):
1460         return self.x0_pt * unit.t_pt, self.y0_pt * unit.t_pt
1461
1462     def curvradius_pt(self, param):
1463         return None
1464
1465     def end_pt(self):
1466         return self.x1_pt, self.y1_pt
1467
1468     def end(self):
1469         return self.x1_pt * unit.t_pt, self.y1_pt * unit.t_pt
1470
1471     def intersect(self, other, epsilon=1e-5):
1472         if isinstance(other, normline):
1473             return _intersectnormlines(self, other)
1474         else:
1475             return  _intersectnormcurves(self._normcurve(), 0, 1, other, 0, 1, epsilon)
1476
1477     def isstraight(self, epsilon):
1478         return 1
1479
1480     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1481         if xs_pt is None:
1482             xs_pt = self.x0_pt
1483         if ys_pt is None:
1484             ys_pt = self.y0_pt
1485         if xe_pt is None:
1486             xe_pt = self.x1_pt
1487         if ye_pt is None:
1488             ye_pt = self.y1_pt
1489         return normline(xs_pt, ys_pt, xe_pt, ye_pt)
1490
1491     def reverse(self):
1492         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt = self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1493
1494     def reversed(self):
1495         return normline(self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
1496
1497     def split(self, params):
1498         # just for performance reasons
1499         x0_pt, y0_pt = self.x0_pt, self.y0_pt
1500         x1_pt, y1_pt = self.x1_pt, self.y1_pt
1501
1502         result = []
1503
1504         xl_pt, yl_pt = x0_pt, y0_pt
1505         for t in params + [1]:
1506             xr_pt, yr_pt = x0_pt + (x1_pt-x0_pt)*t, y0_pt + (y1_pt-y0_pt)*t
1507             result.append(normline(xl_pt, yl_pt, xr_pt, yr_pt))
1508             xl_pt, yl_pt = xr_pt, yr_pt
1509
1510         return result
1511
1512     def tangentvector_pt(self, param):
1513         return self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt
1514
1515     def trafo(self, param):
1516         tx_pt, ty_pt = self.at_pt(param)
1517         tdx_pt, tdy_pt = self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt
1518         return trafo.translate_pt(tx_pt, ty_pt)*trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt)))
1519
1520     def transformed(self, trafo):
1521         return normline(*(trafo._apply(self.x0_pt, self.y0_pt) + trafo._apply(self.x1_pt, self.y1_pt)))
1522
1523     def outputPS(self, file):
1524         file.write("%g %g lineto\n" % (self.x1_pt, self.y1_pt))
1525
1526     def outputPDF(self, file):
1527         file.write("%f %f l\n" % (self.x1_pt, self.y1_pt))
1528
1529
1530 class normcurve(normsubpathitem):
1531
1532     """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)"""
1533
1534     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
1535
1536     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1537         self.x0_pt = x0_pt
1538         self.y0_pt = y0_pt
1539         self.x1_pt = x1_pt
1540         self.y1_pt = y1_pt
1541         self.x2_pt = x2_pt
1542         self.y2_pt = y2_pt
1543         self.x3_pt = x3_pt
1544         self.y3_pt = y3_pt
1545
1546     def __str__(self):
1547         return "normcurve(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt,
1548                                                               self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt)
1549
1550     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1551         """computes the parameters [t] of bpathitem where the given lengths (in pts) are assumed
1552         returns ( [parameters], total arclen)
1553         A negative length gives a parameter 0"""
1554
1555         # create the list of accumulated lengths
1556         # and the length of the parameters
1557         seg = self.seglengths(1, epsilon)
1558         arclens = [seg[i][0] for i in range(len(seg))]
1559         Dparams = [seg[i][1] for i in range(len(seg))]
1560         l = len(arclens)
1561         for i in range(1,l):
1562             arclens[i] += arclens[i-1]
1563
1564         # create the list of parameters to be returned
1565         params = []
1566         for length in lengths:
1567             # find the last index that is smaller than length
1568             try:
1569                 lindex = bisect.bisect_left(arclens, length)
1570             except: # workaround for python 2.0
1571                 lindex = bisect.bisect(arclens, length)
1572                 while lindex and (lindex >= len(arclens) or
1573                                   arclens[lindex] >= length):
1574                     lindex -= 1
1575             if lindex == 0:
1576                 param = Dparams[0] * length * 1.0 / arclens[0]
1577             elif lindex < l-1:
1578                 param = Dparams[lindex+1] * (length - arclens[lindex]) * 1.0 / (arclens[lindex+1] - arclens[lindex])
1579                 for i in range(lindex+1):
1580                     param += Dparams[i]
1581             else:
1582                 param = 1 + Dparams[-1] * (length - arclens[-1]) * 1.0 / (arclens[-1] - arclens[-2])
1583
1584             param = max(min(param,1),0)
1585             params.append(param)
1586         return (params, arclens[-1])
1587
1588     def arclen_pt(self, epsilon=1e-5):
1589         """computes arclen of bpathitem in pts using successive midpoint split"""
1590         if self.isstraight(epsilon):
1591             return math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1592         else:
1593             a, b = self.midpointsplit()
1594             return a.arclen_pt(epsilon) + b.arclen_pt(epsilon)
1595
1596     def at_pt(self, t):
1597         xt_pt = ( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t +
1598                   (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt          )*t*t +
1599                   (-3*self.x0_pt+3*self.x1_pt                      )*t +
1600                   self.x0_pt )
1601         yt_pt = ( (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t +
1602                   (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt          )*t*t +
1603                   (-3*self.y0_pt+3*self.y1_pt                      )*t +
1604                   self.y0_pt )
1605         return xt_pt, yt_pt
1606
1607     def at(self, t):
1608         xt_pt, yt_pt = self.at_pt(t)
1609         return xt_pt * unit.t_pt, yt_pt * unit.t_pt
1610
1611     def bbox(self):
1612         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1613                           min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt),
1614                           max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1615                           max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt))
1616
1617     def begin_pt(self):
1618         return self.x0_pt, self.y0_pt
1619
1620     def begin(self):
1621         return self.x0_pt * unit.t_pt, self.y0_pt * unit.t_pt
1622
1623     def curvradius_pt(self, param):
1624         xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) +
1625                  6 * (1-param)*param * (-self.x1_pt + self.x2_pt) +
1626                  3 * param*param * (-self.x2_pt + self.x3_pt) )
1627         ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) +
1628                  6 * (1-param)*param * (-self.y1_pt + self.y2_pt) +
1629                  3 * param*param * (-self.y2_pt + self.y3_pt) )
1630         xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) +
1631                   6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) )
1632         yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) +
1633                   6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) )
1634         return (xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot)
1635
1636     def end_pt(self):
1637         return self.x3_pt, self.y3_pt
1638
1639     def end(self):
1640         return self.x3_pt * unit.t_pt, self.y3_pt * unit.t_pt
1641
1642     def intersect(self, other, epsilon=1e-5):
1643         if isinstance(other, normline):
1644             return  _intersectnormcurves(self, 0, 1, other._normcurve(), 0, 1, epsilon)
1645         else:
1646             return  _intersectnormcurves(self, 0, 1, other, 0, 1, epsilon)
1647
1648     def isstraight(self, epsilon=1e-5):
1649         """check wheter the normcurve is approximately straight"""
1650
1651         # just check, whether the modulus of the difference between
1652         # the length of the control polygon
1653         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1654         # straight line between starting and ending point of the
1655         # normcurve (i.e. |P3-P1|) is smaller the epsilon
1656         return abs(math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt)+
1657                    math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt)+
1658                    math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt)-
1659                    math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt))<epsilon
1660
1661     def midpointsplit(self):
1662         """splits bpathitem at midpoint returning bpath with two bpathitems"""
1663
1664         # for efficiency reason, we do not use self.split(0.5)!
1665
1666         # first, we have to calculate the  midpoints between adjacent
1667         # control points
1668         x01_pt = 0.5*(self.x0_pt + self.x1_pt)
1669         y01_pt = 0.5*(self.y0_pt + self.y1_pt)
1670         x12_pt = 0.5*(self.x1_pt + self.x2_pt)
1671         y12_pt = 0.5*(self.y1_pt + self.y2_pt)
1672         x23_pt = 0.5*(self.x2_pt + self.x3_pt)
1673         y23_pt = 0.5*(self.y2_pt + self.y3_pt)
1674
1675         # In the next iterative step, we need the midpoints between 01 and 12
1676         # and between 12 and 23
1677         x01_12_pt = 0.5*(x01_pt + x12_pt)
1678         y01_12_pt = 0.5*(y01_pt + y12_pt)
1679         x12_23_pt = 0.5*(x12_pt + x23_pt)
1680         y12_23_pt = 0.5*(y12_pt + y23_pt)
1681
1682         # Finally the midpoint is given by
1683         xmidpoint_pt = 0.5*(x01_12_pt + x12_23_pt)
1684         ymidpoint_pt = 0.5*(y01_12_pt + y12_23_pt)
1685
1686         return (normcurve(self.x0_pt, self.y0_pt,
1687                           x01_pt, y01_pt,
1688                           x01_12_pt, y01_12_pt,
1689                           xmidpoint_pt, ymidpoint_pt),
1690                 normcurve(xmidpoint_pt, ymidpoint_pt,
1691                           x12_23_pt, y12_23_pt,
1692                           x23_pt, y23_pt,
1693                           self.x3_pt, self.y3_pt))
1694
1695     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1696         if xs_pt is None:
1697             xs_pt = self.x0_pt
1698         if ys_pt is None:
1699             ys_pt = self.y0_pt
1700         if xe_pt is None:
1701             xe_pt = self.x3_pt
1702         if ye_pt is None:
1703             ye_pt = self.y3_pt
1704         return normcurve(xs_pt, ys_pt,
1705                          self.x1_pt, self.y1_pt,
1706                          self.x2_pt, self.y2_pt,
1707                          xe_pt, ye_pt)
1708
1709     def reverse(self):
1710         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt = \
1711         self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1712
1713     def reversed(self):
1714         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)
1715
1716     def seglengths(self, paraminterval, epsilon=1e-5):
1717         """returns the list of segment line lengths (in pts) of the normcurve
1718            together with the length of the parameterinterval"""
1719
1720         # lower and upper bounds for the arclen
1721         lowerlen = math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1722         upperlen = ( math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt) +
1723                      math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt) +
1724                      math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt) )
1725
1726         # instead of isstraight method:
1727         if abs(upperlen-lowerlen)<epsilon:
1728             return [( 0.5*(upperlen+lowerlen), paraminterval )]
1729         else:
1730             a, b = self.midpointsplit()
1731             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
1732
1733     def split(self, params):
1734         """return list of normcurves corresponding to split at parameters"""
1735
1736         # first, we calculate the coefficients corresponding to our
1737         # original bezier curve. These represent a useful starting
1738         # point for the following change of the polynomial parameter
1739         a0x_pt = self.x0_pt
1740         a0y_pt = self.y0_pt
1741         a1x_pt = 3*(-self.x0_pt+self.x1_pt)
1742         a1y_pt = 3*(-self.y0_pt+self.y1_pt)
1743         a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt)
1744         a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt)
1745         a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt
1746         a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt
1747
1748         params = [0] + params + [1]
1749         result = []
1750
1751         for i in range(len(params)-1):
1752             t1 = params[i]
1753             dt = params[i+1]-t1
1754
1755             # [t1,t2] part
1756             #
1757             # the new coefficients of the [t1,t1+dt] part of the bezier curve
1758             # are then given by expanding
1759             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
1760             #  a3*(t1+dt*u)**3 in u, yielding
1761             #
1762             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
1763             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
1764             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
1765             #   a3*dt**3                         * u**3
1766             #
1767             # from this values we obtain the new control points by inversion
1768             #
1769             # XXX: we could do this more efficiently by reusing for
1770             # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
1771             # Bezier curve
1772
1773             x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1
1774             y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1
1775             x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt
1776             y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt
1777             x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt
1778             y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt
1779             x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt
1780             y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt
1781
1782             result.append(normcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1783
1784         return result
1785
1786     def tangentvector_pt(self, param):
1787         tvectx = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
1788                   2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt        )*param +
1789                     (-3*self.x0_pt+3*self.x1_pt                  ))
1790         tvecty = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
1791                   2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt        )*param +
1792                     (-3*self.y0_pt+3*self.y1_pt                  ))
1793         return (tvectx, tvecty)
1794
1795     def trafo(self, param):
1796         tx_pt, ty_pt = self.at_pt(param)
1797         tdx_pt, tdy_pt = self.tangentvector_pt(param)
1798         return trafo.translate_pt(tx_pt, ty_pt)*trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt)))
1799
1800     def transform(self, trafo):
1801         self.x0_pt, self.y0_pt = trafo._apply(self.x0_pt, self.y0_pt)
1802         self.x1_pt, self.y1_pt = trafo._apply(self.x1_pt, self.y1_pt)
1803         self.x2_pt, self.y2_pt = trafo._apply(self.x2_pt, self.y2_pt)
1804         self.x3_pt, self.y3_pt = trafo._apply(self.x3_pt, self.y3_pt)
1805
1806     def transformed(self, trafo):
1807         return normcurve(*(trafo._apply(self.x0_pt, self.y0_pt)+
1808                            trafo._apply(self.x1_pt, self.y1_pt)+
1809                            trafo._apply(self.x2_pt, self.y2_pt)+
1810                            trafo._apply(self.x3_pt, self.y3_pt)))
1811
1812     def outputPS(self, file):
1813         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))
1814
1815     def outputPDF(self, file):
1816         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))
1817
1818 #
1819 # normpaths are made up of normsubpaths, which represent connected line segments
1820 #
1821
1822 class normsubpath:
1823
1824     """sub path of a normalized path
1825
1826     A subpath consists of a list of normsubpathitems, i.e., lines and bcurves
1827     and can either be closed or not.
1828
1829     Some invariants, which have to be obeyed:
1830     - All normsubpathitems have to be longer than epsilon pts.
1831     - At the end there may be a normline (stored in self.skippedline) whose
1832       length is shorter than epsilon
1833     - The last point of a normsubpathitem and the first point of the next
1834     element have to be equal.
1835     - When the path is closed, the last point of last normsubpathitem has
1836       to be equal to the first point of the first normsubpathitem.
1837     """
1838
1839     __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline"
1840
1841     def __init__(self, normsubpathitems=[], closed=0, epsilon=1e-5):
1842         self.epsilon = epsilon
1843         # If one or more items appended to the normsubpath have been
1844         # skipped (because their total length was shorter than
1845         # epsilon), we remember this fact by a line because we have to
1846         # take it properly into account when appending further subnormpathitems
1847         self.skippedline = None
1848
1849         self.normsubpathitems = []
1850         self.closed = 0
1851
1852         # a test (might be temporary)
1853         for anormsubpathitem in normsubpathitems:
1854             assert isinstance(anormsubpathitem, normsubpathitem), "only list of normsubpathitem instances allowed"
1855
1856         self.extend(normsubpathitems)
1857
1858         if closed:
1859             self.close()
1860
1861     def __add__(self, other):
1862         # we take self.epsilon as accuracy for the resulting subnormpath
1863         result = subnormpath(self.normpathitems, self.closed, self.epsilon)
1864         result += other
1865         return result
1866
1867     def __getitem__(self, i):
1868         return self.normsubpathitems[i]
1869
1870     def __iadd__(self, other):
1871         if other.closed:
1872             raise PathException("Cannot extend normsubpath by closed normsubpath")
1873         self.extend(other.normsubpathitems)
1874         return self
1875
1876     def __len__(self):
1877         return len(self.normsubpathitems)
1878
1879     def __str__(self):
1880         return "subpath(%s, [%s])" % (self.closed and "closed" or "open",
1881                                     ", ".join(map(str, self.normsubpathitems)))
1882
1883     def _distributeparams(self, params):
1884         """Creates a list tuples (normsubpathitem, itemparams),
1885         where itemparams are the parameter values corresponding
1886         to params in normsubpathitem. For the first normsubpathitem
1887         itemparams fulfil param < 1, for the last normsubpathitem
1888         itemparams fulfil 0 <= param, and for all other
1889         normsubpathitems itemparams fulfil 0 <= param < 1.
1890         Note that params have to be sorted.
1891         """
1892         if self.isshort():
1893             if params:
1894                 raise PathException("Cannot select parameters for a short normsubpath")
1895             return []
1896         result = []
1897         paramindex = 0
1898         for index, normsubpathitem in enumerate(self.normsubpathitems[:-1]):
1899             oldparamindex = paramindex
1900             while paramindex < len(params) and params[paramindex] < index + 1:
1901                 paramindex += 1
1902             result.append((normsubpathitem, [param - index for param in params[oldparamindex: paramindex]]))
1903         result.append((self.normsubpathitems[-1],
1904                        [param - len(self.normsubpathitems) + 1 for param in params[paramindex:]]))
1905         return result
1906
1907     def _findnormsubpathitem(self, param):
1908         """Finds the normsubpathitem for the given parameter and
1909         returns a tuple containing this item and the parameter
1910         converted to the range of the item. An out of bound parameter
1911         is handled like in _distributeparams."""
1912         if not self.normsubpathitems:
1913             raise PathException("Cannot select parameters for a short normsubpath")
1914         if param > 0:
1915             index = int(param)
1916             if index > len(self.normsubpathitems) - 1:
1917                 index = len(self.normsubpathitems) - 1
1918         else:
1919             index = 0
1920         return self.normsubpathitems[index], param - index
1921
1922     def append(self, anormsubpathitem):
1923         assert isinstance(anormsubpathitem, normsubpathitem), "only normsubpathitem instances allowed"
1924
1925         if self.closed:
1926             raise PathException("Cannot append to closed normsubpath")
1927
1928         if self.skippedline:
1929             xs_pt, ys_pt = self.skippedline.begin_pt()
1930         else:
1931             xs_pt, ys_pt = anormsubpathitem.begin_pt()
1932         xe_pt, ye_pt = anormsubpathitem.end_pt()
1933
1934         if (math.hypot(xe_pt-xs_pt, ye_pt-ys_pt) >= self.epsilon or
1935             anormsubpathitem.arclen_pt(self.epsilon) >= self.epsilon):
1936             if self.skippedline:
1937                 anormsubpathitem = anormsubpathitem.modified(xs_pt=xs_pt, ys_pt=ys_pt)
1938             self.normsubpathitems.append(anormsubpathitem)
1939             self.skippedline = None
1940         else:
1941             self.skippedline = normline(xs_pt, ys_pt, xe_pt, ye_pt)
1942
1943     def arclen_pt(self):
1944         """returns total arc length of normsubpath in pts with accuracy epsilon"""
1945         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normsubpathitems])
1946
1947     def arclen(self):
1948         """returns total arc length of normsubpath"""
1949         return self.arclen_pt() * unit.t_pt
1950
1951     def _arclentoparam_pt(self, lengths):
1952         """returns [t, l] where t are parameter value(s) matching given length(s)
1953         and l is the total length of the normsubpath
1954         The parameters are with respect to the normsubpath: t in [0, self.range()]
1955         lengths that are < 0 give parameter 0"""
1956
1957         allarclen = 0
1958         allparams = [0] * len(lengths)
1959         rests = lengths[:]
1960
1961         for pitem in self.normsubpathitems:
1962             params, arclen = pitem._arclentoparam_pt(rests, self.epsilon)
1963             allarclen += arclen
1964             for i in range(len(rests)):
1965                 if rests[i] >= 0:
1966                     rests[i] -= arclen
1967                     allparams[i] += params[i]
1968
1969         return (allparams, allarclen)
1970
1971     def arclentoparam_pt(self, lengths):
1972         if len(lengths)==1:
1973             return self._arclentoparam_pt(lengths)[0][0]
1974         else:
1975             return self._arclentoparam_pt(lengths)[0]
1976
1977     def arclentoparam(self, lengths):
1978         """returns the parameter value(s) matching the given length(s)
1979
1980         all given lengths must be positive.
1981         A length greater than the total arclength will give self.range()
1982         """
1983         l = [unit.topt(length) for length in helper.ensuresequence(lengths)]
1984         return self.arclentoparam_pt(l)
1985
1986     def at_pt(self, param):
1987         """return coordinates in pts of sub path at parameter value param
1988
1989         The parameter param must be smaller or equal to the number of
1990         segments in the normpath, otherwise None is returned.
1991         """
1992         normsubpathitem, itemparam = self._findnormsubpathitem(param)
1993         return normsubpathitem.at_pt(itemparam)
1994
1995     def at(self, param):
1996         """return coordinates of sub path at parameter value param
1997
1998         The parameter param must be smaller or equal to the number of
1999         segments in the normpath, otherwise None is returned.
2000         """
2001         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2002         return normsubpathitem.at(itemparam)
2003
2004     def bbox(self):
2005         if self.normsubpathitems:
2006             abbox = self.normsubpathitems[0].bbox()
2007             for anormpathitem in self.normsubpathitems[1:]:
2008                 abbox += anormpathitem.bbox()
2009             return abbox
2010         else:
2011             return None
2012
2013     def begin_pt(self):
2014         return self.normsubpathitems[0].begin_pt()
2015
2016     def begin(self):
2017         return self.normsubpathitems[0].begin()
2018
2019     def close(self):
2020         if self.closed:
2021             raise PathException("Cannot close already closed normsubpath")
2022         if not self.normsubpathitems:
2023             if self.skippedline is None:
2024                 raise PathException("Cannot close empty normsubpath")
2025             else:
2026                 raise PathException("Normsubpath too short, cannot be closed")
2027
2028         xs_pt, ys_pt = self.normsubpathitems[-1].end_pt()
2029         xe_pt, ye_pt = self.normsubpathitems[0].begin_pt()
2030         self.append(normline(xs_pt, ys_pt, xe_pt, ye_pt))
2031
2032         # the append might have left a skippedline, which we have to remove
2033         # from the end of the closed path
2034         if self.skippedline:
2035             self.normsubpathitems[-1] = self.normsubpathitems[-1].modified(xe_pt=self.skippedline.x1_pt,
2036                                                                            ye_pt=self.skippedline.y1_pt)
2037             self.skippedline = None
2038
2039         self.closed = 1
2040
2041     def curvradius_pt(self, param):
2042         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2043         return normsubpathitem.curvradius_pt(itemparam)
2044
2045     def end_pt(self):
2046         return self.normsubpathitems[-1].end_pt()
2047
2048     def end(self):
2049         return self.normsubpathitems[-1].end()
2050
2051     def extend(self, normsubpathitems):
2052         for normsubpathitem in normsubpathitems:
2053             self.append(normsubpathitem)
2054
2055     def intersect(self, other):
2056         """intersect self with other normsubpath
2057
2058         returns a tuple of lists consisting of the parameter values
2059         of the intersection points of the corresponding normsubpath
2060
2061         """
2062         intersections_a = []
2063         intersections_b = []
2064         epsilon = min(self.epsilon, other.epsilon)
2065         # Intersect all subpaths of self with the subpaths of other, possibly including
2066         # one intersection point several times
2067         for t_a, pitem_a  in enumerate(self.normsubpathitems):
2068             for t_b, pitem_b in enumerate(other.normsubpathitems):
2069                 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon):
2070                     intersections_a.append(intersection_a + t_a)
2071                     intersections_b.append(intersection_b + t_b)
2072
2073         # although intersectipns_a are sorted for the different normsubpathitems,
2074         # within a normsubpathitem, the ordering has to be ensured separately:
2075         intersections = zip(intersections_a, intersections_b)
2076         intersections.sort()
2077         intersections_a = [a for a, b in intersections]
2078         intersections_b = [b for a, b in intersections]
2079
2080         # for symmetry reasons we enumerate intersections_a as well, although
2081         # they are already sorted (note we do not need to sort intersections_a)
2082         intersections_a = zip(intersections_a, range(len(intersections_a)))
2083         intersections_b = zip(intersections_b, range(len(intersections_b)))
2084         intersections_b.sort()
2085
2086         # now we search for intersections points which are closer together than epsilon
2087         # This task is handled by the following function
2088         def closepoints(normsubpath, intersections):
2089             split = normsubpath.split([intersection for intersection, index in intersections])
2090             result = []
2091             if normsubpath.closed:
2092                 # note that the number of segments of a closed path is off by one
2093                 # compared to an open path
2094                 i = 0
2095                 while i < len(split):
2096                     splitnormsubpath = split[i]
2097                     j = i
2098                     while splitnormsubpath.isshort():
2099                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
2100                         if ip1<ip2:
2101                             result.append((ip1, ip2))
2102                         else:
2103                             result.append((ip2, ip1))
2104                         j += 1
2105                         if j == len(split):
2106                             j = 0
2107                         if j < len(split):
2108                             splitnormsubpath = splitnormsubpath.joined(split[j])
2109                         else:
2110                             break
2111                     i += 1
2112             else:
2113                 i = 1
2114                 while i < len(split)-1:
2115                     splitnormsubpath = split[i]
2116                     j = i
2117                     while splitnormsubpath.isshort():
2118                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
2119                         if ip1<ip2:
2120                             result.append((ip1, ip2))
2121                         else:
2122                             result.append((ip2, ip1))
2123                         j += 1
2124                         if j < len(split)-1:
2125                             splitnormsubpath.join(split[j])
2126                         else:
2127                             break
2128                     i += 1
2129             return result
2130
2131         closepoints_a = closepoints(self, intersections_a)
2132         closepoints_b = closepoints(other, intersections_b)
2133
2134         # map intersection point to lowest point which is equivalent to the
2135         # point
2136         equivalentpoints = list(range(len(intersections_a)))
2137
2138         for closepoint_a in closepoints_a:
2139             for closepoint_b in closepoints_b:
2140                 if closepoint_a == closepoint_b:
2141                     for i in range(closepoint_a[1], len(equivalentpoints)):
2142                         if equivalentpoints[i] == closepoint_a[1]:
2143                             equivalentpoints[i] = closepoint_a[0]
2144
2145         # determine the remaining intersection points
2146         intersectionpoints = {}
2147         for point in equivalentpoints:
2148             intersectionpoints[point] = 1
2149
2150         # build result
2151         result = []
2152         for point in intersectionpoints.keys():
2153             for intersection_a, index_a in intersections_a:
2154                 if index_a == point:
2155                     result_a = intersection_a
2156             for intersection_b, index_b in intersections_b:
2157                 if index_b == point:
2158                     result_b = intersection_b
2159             result.append((result_a, result_b))
2160         # note that the result is sorted in a, since we sorted
2161         # intersections_a in the very beginning
2162
2163         return [x for x, y in result], [y for x, y in result]
2164
2165     def isshort(self):
2166         """return whether the subnormpath is shorter than epsilon"""
2167         return not self.normsubpathitems
2168
2169     def join(self, other):
2170         for othernormpathitem in other.normsubpathitems:
2171             self.append(othernormpathitem)
2172         if other.skippedline is not None:
2173             self.append(other.skippedline)
2174
2175     def joined(self, other):
2176         result = normsubpath(self.normsubpathitems, self.closed, self.epsilon)
2177         result.skippedline = self.skippedline
2178         result.join(other)
2179         return result
2180
2181     def range(self):
2182         """return maximal parameter value, i.e. number of line/curve segments"""
2183         return len(self.normsubpathitems)
2184
2185     def reverse(self):
2186         self.normsubpathitems.reverse()
2187         for npitem in self.normsubpathitems:
2188             npitem.reverse()
2189
2190     def reversed(self):
2191         nnormpathitems = []
2192         for i in range(len(self.normsubpathitems)):
2193             nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed())
2194         return normsubpath(nnormpathitems, self.closed)
2195
2196     def split(self, params):
2197         """split normsubpath at list of parameter values params and return list
2198         of normsubpaths
2199
2200         The parameter list params has to be sorted. Note that each element of
2201         the resulting list is an open normsubpath.
2202         """
2203
2204         result = [normsubpath(epsilon=self.epsilon)]
2205
2206         for normsubpathitem, itemparams in self._distributeparams(params):
2207             splititems = normsubpathitem.split(itemparams)
2208             result[-1].append(splititems[0])
2209             result.extend([normsubpath([splititem], epsilon=self.epsilon) for splititem in splititems[1:]])
2210
2211         if self.closed:
2212             if params:
2213                 # join last and first segment together if the normsubpath was originally closed and it has been split
2214                 result[-1].normsubpathitems.extend(result[0].normsubpathitems)
2215                 result = result[-1:] + result[1:-1]
2216             else:
2217                 # otherwise just close the copied path again
2218                 result[0].close()
2219         return result
2220
2221     def tangent(self, param, length=None):
2222         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2223         tx_pt, ty_pt = normsubpathitem.at_pt(itemparam)
2224         tdx_pt, tdy_pt = normsubpathitem.tangentvector_pt(itemparam)
2225         if length is not None:
2226             sfactor = unit.topt(length)/math.hypot(tdx_pt, tdy_pt)
2227             tdx_pt *= sfactor
2228             tdy_pt *= sfactor
2229         return line_pt(tx_pt, ty_pt, tx_pt+tdx_pt, ty_pt+tdy_pt)
2230
2231     def trafo(self, param):
2232         normsubpathitem, itemparam = self._findnormsubpathitem(param)
2233         return normsubpathitem.trafo(itemparam)
2234
2235     def transform(self, trafo):
2236         """transform sub path according to trafo"""
2237         # note that we have to rebuild the path again since normsubpathitems
2238         # may become shorter than epsilon and/or skippedline may become
2239         # longer than epsilon
2240         normsubpathitems = self.normsubpathitems
2241         closed = self.closed
2242         skippedline = self.skippedline
2243         self.normsubpathitems = []
2244         self.closed = 0
2245         self.skippedline = None
2246         for pitem in normsubpathitems:
2247             self.append(pitem.transformed(trafo))
2248         if closed:
2249             self.close()
2250         elif skippedline is not None:
2251             self.append(skippedline.transformed(trafo))
2252
2253     def transformed(self, trafo):
2254         """return sub path transformed according to trafo"""
2255         nnormsubpath = normsubpath(epsilon=self.epsilon)
2256         for pitem in self.normsubpathitems:
2257             nnormsubpath.append(pitem.transformed(trafo))
2258         if self.closed:
2259             nnormsubpath.close()
2260         elif self.skippedline is not None:
2261             nnormsubpath.append(skippedline.transformed(trafo))
2262         return nnormsubpath
2263
2264     def outputPS(self, file):
2265         # if the normsubpath is closed, we must not output a normline at
2266         # the end
2267         if not self.normsubpathitems:
2268             return
2269         if self.closed and isinstance(self.normsubpathitems[-1], normline):
2270             normsubpathitems = self.normsubpathitems[:-1]
2271         else:
2272             normsubpathitems = self.normsubpathitems
2273         if normsubpathitems:
2274             file.write("%g %g moveto\n" % self.begin_pt())
2275             for anormpathitem in normsubpathitems:
2276                 anormpathitem.outputPS(file)
2277         if self.closed:
2278             file.write("closepath\n")
2279
2280     def outputPDF(self, file):
2281         # if the normsubpath is closed, we must not output a normline at
2282         # the end
2283         if not self.normsubpathitems:
2284             return
2285         if self.closed and isinstance(self.normsubpathitems[-1], normline):
2286             normsubpathitems = self.normsubpathitems[:-1]
2287         else:
2288             normsubpathitems = self.normsubpathitems
2289         if normsubpathitems:
2290             file.write("%f %f m\n" % self.begin_pt())
2291             for anormpathitem in normsubpathitems:
2292                 anormpathitem.outputPDF(file)
2293         if self.closed:
2294             file.write("h\n")
2295
2296 #
2297 # the normpath class
2298 #
2299
2300 class normpath(base.canvasitem):
2301
2302     """normalized path
2303
2304     A normalized path consists of a list of normalized sub paths.
2305
2306     """
2307
2308     def __init__(self, normsubpaths=None):
2309         """ construct a normpath from another normpath passed as arg,
2310         a path or a list of normsubpaths. An accuracy of epsilon pts
2311         is used for numerical calculations.
2312         """
2313         if normsubpaths is None:
2314             self.normsubpaths = []
2315         else:
2316             self.normsubpaths = normsubpaths
2317             for subpath in normsubpaths:
2318                 assert isinstance(subpath, normsubpath), "only list of normsubpath instances allowed"
2319
2320     def __add__(self, other):
2321         result = normpath()
2322         result.normsubpaths = self.normsubpaths + other.normpath().normsubpaths
2323         return result
2324
2325     def __getitem__(self, i):
2326         return self.normsubpaths[i]
2327
2328     def __iadd__(self, other):
2329         self.normsubpaths += other.normpath().normsubpaths
2330         return self
2331
2332     def __len__(self):
2333         return len(self.normsubpaths)
2334
2335     def __str__(self):
2336         return "normpath(%s)" % ", ".join(map(str, self.normsubpaths))
2337
2338     def _findsubpath(self, param, arclen):
2339         """return a tuple (subpath, rparam), where subpath is the subpath
2340         containing the position specified by either param or arclen and rparam
2341         is the corresponding parameter value in this subpath.
2342         """
2343
2344         if param is not None and arclen is not None:
2345             raise PathException("either param or arclen has to be specified, but not both")
2346
2347         if param is not None:
2348             try:
2349                 subpath, param = param
2350             except TypeError:
2351                 # determine subpath from param
2352                 normsubpathindex = 0
2353                 for normsubpath in self.normsubpaths[:-1]:
2354                     normsubpathrange = normsubpath.range()
2355                     if param < normsubpathrange+normsubpathindex:
2356                         return normsubpath, param-normsubpathindex
2357                     normsubpathindex += normsubpathrange
2358                 return self.normsubpaths[-1], param-normsubpathindex
2359             try:
2360                 return self.normsubpaths[subpath], param
2361             except IndexError:
2362                 raise PathException("subpath index out of range")
2363
2364         # we have been passed an arclen (or a tuple (subpath, arclen))
2365         try:
2366             subpath, arclen = arclen
2367         except:
2368             # determine subpath from arclen
2369             param = self.arclentoparam(arclen)
2370             for normsubpath in self.normsubpaths[:-1]:
2371                 normsubpathrange = normsubpath.range()
2372                 if param <= normsubpathrange+normsubpathindex:
2373                     return normsubpath, param-normsubpathindex
2374                 normsubpathindex += normsubpathrange
2375             return self.normsubpaths[-1], param-normsubpathindex
2376
2377         try:
2378             normsubpath = self.normsubpaths[subpath]
2379         except IndexError:
2380             raise PathException("subpath index out of range")
2381         return normsubpath, normsubpath.arclentoparam(arclen)
2382
2383     def append(self, anormsubpath):
2384         assert isinstance(anormsubpath, normsubpath), "only list of normsubpath instance allowed"
2385         self.normsubpaths.append(anormsubpath)
2386
2387     def extend(self, normsubpaths):
2388         for anormsubpath in normsubpaths:
2389             assert isinstance(anormsubpath, normsubpath), "only list of normsubpath instance allowed"
2390         self.normsubpaths.extend(normsubpaths)
2391
2392     def arclen_pt(self):
2393         """returns total arc length of normpath in pts"""
2394         return sum([normsubpath.arclen_pt() for normsubpath in self.normsubpaths])
2395
2396     def arclen(self):
2397         """returns total arc length of normpath"""
2398         return self.arclen_pt() * unit.t_pt
2399
2400     def arclentoparam_pt(self, lengths):
2401         rests = lengths[:]
2402         allparams = [0] * len(lengths)
2403
2404         for normsubpath in self.normsubpaths:
2405             # we need arclen for knowing when all the parameters are done
2406             # for lengths that are done: rests[i] is negative
2407             # normsubpath._arclentoparam has to ignore such lengths
2408             params, arclen = normsubpath._arclentoparam_pt(rests)
2409             finis = 0 # number of lengths that are done
2410             for i in range(len(rests)):
2411                 if rests[i] >= 0:
2412                   rests[i] -= arclen
2413                   allparams[i] += params[i]
2414                 else:
2415                     finis += 1
2416             if finis == len(rests): break
2417
2418         if len(lengths) == 1: allparams = allparams[0]
2419         return allparams
2420
2421     def arclentoparam(self, lengths):
2422         """returns the parameter value(s) matching the given length(s)
2423
2424         all given lengths must be positive.
2425         A length greater than the total arclength will give self.range()
2426         """
2427         l = [unit.topt(length) for length in helper.ensuresequence(lengths)]
2428         return self.arclentoparam_pt(l)
2429
2430     def at_pt(self, param=None, arclen=None):
2431         """return coordinates in pts of path at either parameter value param
2432         or arc length arclen.
2433
2434         At discontinuities in the path, the limit from below is returned.
2435         """
2436         normsubpath, param = self._findsubpath(param, arclen)
2437         return normsubpath.at_pt(param)
2438
2439     def at(self, param=None, arclen=None):
2440         """return coordinates of path at either parameter value param
2441         or arc length arclen.
2442
2443         At discontinuities in the path, the limit from below is returned
2444         """
2445         normsubpath, param = self._findsubpath(param, arclen)
2446         return normsubpath.at(param)
2447
2448     def bbox(self):
2449         abbox = None
2450         for normsubpath in self.normsubpaths:
2451             nbbox =  normsubpath.bbox()
2452             if abbox is None:
2453                 abbox = nbbox
2454             elif nbbox:
2455                 abbox += nbbox
2456         return abbox
2457
2458     def begin_pt(self):
2459         """return coordinates of first point of first subpath in path (in pts)"""
2460         if self.normsubpaths:
2461             return self.normsubpaths[0].begin_pt()
2462         else:
2463             raise PathException("cannot return first point of empty path")
2464
2465     def begin(self):
2466         """return coordinates of first point of first subpath in path"""
2467         if self.normsubpaths:
2468             return self.normsubpaths[0].begin()
2469         else:
2470             raise PathException("cannot return first point of empty path")
2471
2472     def curvradius_pt(self, param=None, arclen=None):
2473         """Returns the curvature radius in pts (or None if infinite)
2474         at parameter param or arc length arclen.  This is the inverse
2475         of the curvature at this parameter
2476
2477         Please note that this radius can be negative or positive,
2478         depending on the sign of the curvature"""
2479         normsubpath, param = self._findsubpath(param, arclen)
2480         return normsubpath.curvradius_pt(param)
2481
2482     def curvradius(self, param=None, arclen=None):
2483         """Returns the curvature radius (or None if infinite) at
2484         parameter param or arc length arclen.  This is the inverse of
2485         the curvature at this parameter
2486
2487         Please note that this radius can be negative or positive,
2488         depending on the sign of the curvature"""
2489         radius = self.curvradius_pt(param, arclen)
2490         if radius is not None:
2491             radius = radius * unit.t_pt
2492         return radius
2493
2494     def end_pt(self):
2495         """return coordinates of last point of last subpath in path (in pts)"""
2496         if self.normsubpaths:
2497             return self.normsubpaths[-1].end_pt()
2498         else:
2499             raise PathException("cannot return last point of empty path")
2500
2501     def end(self):
2502         """return coordinates of last point of last subpath in path"""
2503         if self.normsubpaths:
2504             return self.normsubpaths[-1].end()
2505         else:
2506             raise PathException("cannot return last point of empty path")
2507
2508     def join(self, other):
2509         if not self.normsubpaths:
2510             raise PathException("cannot join to end of empty path")
2511         if self.normsubpaths[-1].closed:
2512             raise PathException("cannot join to end of closed sub path")
2513         other = other.normpath()
2514         if not other.normsubpaths:
2515             raise PathException("cannot join empty path")
2516
2517         self.normsubpaths[-1].normsubpathitems += other.normsubpaths[0].normsubpathitems
2518         self.normsubpaths += other.normsubpaths[1:]
2519
2520     def joined(self, other):
2521         # NOTE we skip a deep copy for performance reasons
2522         result = normpath(self.normsubpaths)
2523         result.join(other)
2524         return result
2525
2526     # << operator also designates joining
2527     __lshift__ = joined
2528
2529     def intersect(self, other):
2530         """intersect self with other path
2531
2532         returns a tuple of lists consisting of the parameter values
2533         of the intersection points of the corresponding normpath
2534
2535         """
2536         other = other.normpath()
2537
2538         # here we build up the result
2539         intersections = ([], [])
2540
2541         # Intersect all normsubpaths of self with the normsubpaths of
2542         # other.
2543         for ia, normsubpath_a in enumerate(self.normsubpaths):
2544             for ib, normsubpath_b in enumerate(other.normsubpaths):
2545                 for intersection in zip(*normsubpath_a.intersect(normsubpath_b)):
2546                     intersections[0].append((ia, intersection[0]))
2547                     intersections[1].append((ib, intersection[1]))
2548         return intersections
2549
2550     def normpath(self):
2551         return self
2552
2553     def range(self):
2554         """return maximal value for parameter value param"""
2555         return sum([normsubpath.range() for normsubpath in self.normsubpaths])
2556
2557     def reverse(self):
2558         """reverse path"""
2559         self.normsubpaths.reverse()
2560         for normsubpath in self.normsubpaths:
2561             normsubpath.reverse()
2562
2563     def reversed(self):
2564         """return reversed path"""
2565         nnormpath = normpath()
2566         for i in range(len(self.normsubpaths)):
2567             nnormpath.normsubpaths.append(self.normsubpaths[-(i+1)].reversed())
2568         return nnormpath
2569
2570     def split(self, params):
2571         """split path at parameter values params
2572
2573         Note that the parameter list has to be sorted.
2574
2575         """
2576
2577         # check whether parameter list is really sorted
2578         sortedparams = list(params)
2579         sortedparams.sort()
2580         if sortedparams != list(params):
2581             raise ValueError("split parameter list params has to be sorted")
2582
2583         # convert to tuple
2584         tparams = []
2585         for param in params:
2586             tparams.append(self._findsubpath(param, None))
2587
2588         # we construct this list of normpaths
2589         result = []
2590
2591         # the currently built up normpath
2592         np = normpath()
2593
2594         for subpath in self.normsubpaths:
2595             splitnormsubpaths = subpath.split([param for normsubpath, param in tparams if normsubpath is subpath])
2596             np.normsubpaths.append(splitnormsubpaths[0])
2597             for normsubpath in splitnormsubpaths[1:]:
2598                 result.append(np)
2599                 np = normpath([normsubpath])
2600
2601         result.append(np)
2602         return result
2603
2604     def tangent(self, param=None, arclen=None, length=None):
2605         """return tangent vector of path at either parameter value param
2606         or arc length arclen.
2607
2608         At discontinuities in the path, the limit from below is returned.
2609         If length is not None, the tangent vector will be scaled to
2610         the desired length.
2611         """
2612         normsubpath, param = self._findsubpath(param, arclen)
2613         return normsubpath.tangent(param, length)
2614
2615     def transform(self, trafo):
2616         """transform path according to trafo"""
2617         for normsubpath in self.normsubpaths:
2618             normsubpath.transform(trafo)
2619
2620     def transformed(self, trafo):
2621         """return path transformed according to trafo"""
2622         return normpath([normsubpath.transformed(trafo) for normsubpath in self.normsubpaths])
2623
2624     def trafo(self, param=None, arclen=None):
2625         """return transformation at either parameter value param or arc length arclen"""
2626         normsubpath, param = self._findsubpath(param, arclen)
2627         return normsubpath.trafo(param)
2628
2629     def outputPS(self, file):
2630         for normsubpath in self.normsubpaths:
2631             normsubpath.outputPS(file)
2632
2633     def outputPDF(self, file):
2634         for normsubpath in self.normsubpaths:
2635             normsubpath.outputPDF(file)
2636