pyx/path.py

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