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