pyx/normpath.py

   1 #!/usr/bin/env python
   2 # -*- coding: ISO-8859-1 -*-
   3 #
   4 #
   5 # Copyright (C) 2002-2005 Jörg Lehmann <joergl@users.sourceforge.net>
   6 # Copyright (C) 2003-2004 Michael Schindler <m-schindler@users.sourceforge.net>
   7 # Copyright (C) 2002-2005 André Wobst <wobsta@users.sourceforge.net>
   8 #
   9 # This file is part of PyX (http://pyx.sourceforge.net/).
  10 #
  11 # PyX is free software; you can redistribute it and/or modify
  12 # it under the terms of the GNU General Public License as published by
  13 # the Free Software Foundation; either version 2 of the License, or
  14 # (at your option) any later version.
  15 #
  16 # PyX is distributed in the hope that it will be useful,
  17 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 # GNU General Public License for more details.
  20 #
  21 # You should have received a copy of the GNU General Public License
  22 # along with PyX; if not, write to the Free Software
  23 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  24
  25 from __future__ import nested_scopes
  26
  27 import math
  28 try:
  29     from math import radians, degrees
  30 except ImportError:
  31     # fallback implementation for Python 2.1
  32     def radians(x): return x*math.pi/180
  33     def degrees(x): return x*180/math.pi
  34
  35 import bbox, canvas, helper, path, trafo, unit
  36
  37 try:
  38     sum([])
  39 except NameError:
  40     # fallback implementation for Python 2.2 and below
  41     def sum(list):
  42         return reduce(lambda x, y: x+y, list, 0)
  43
  44 try:
  45     enumerate([])
  46 except NameError:
  47     # fallback implementation for Python 2.2 and below
  48     def enumerate(list):
  49         return zip(xrange(len(list)), list)
  50
  51 # use new style classes when possible
  52 __metaclass__ = type
  53
  54 ################################################################################
  55
  56 # global epsilon (default precision of normsubpaths)
  57 _epsilon = 1e-5
  58
  59 def set(epsilon=None):
  60     global _epsilon
  61     if epsilon is not None:
  62         _epsilon = epsilon
  63
  64
  65 ################################################################################
  66 # normsubpathitems
  67 ################################################################################
  68
  69 class normsubpathitem:
  70
  71     """element of a normalized sub path
  72
  73     Various operations on normsubpathitems might be subject of
  74     approximitions. Those methods get the finite precision epsilon,
  75     which is the accuracy needed expressed as a length in pts.
  76
  77     normsubpathitems should never be modified inplace, since references
  78     might be shared betweeen several normsubpaths.
  79     """
  80
  81     def arclen_pt(self, epsilon):
  82         """return arc length in pts"""
  83         pass
  84
  85     def _arclentoparam_pt(self, lengths_pt, epsilon):
  86         """return a tuple of params and the total length arc length in pts"""
  87         pass
  88
  89     def arclentoparam_pt(self, lengths_pt, epsilon):
  90         """return a tuple of params"""
  91         pass
  92
  93     def at_pt(self, params):
  94         """return coordinates at params in pts"""
  95         pass
  96
  97     def atbegin_pt(self):
  98         """return coordinates of first point in pts"""
  99         pass
 100
 101     def atend_pt(self):
 102         """return coordinates of last point in pts"""
 103         pass
 104
 105     def bbox(self):
 106         """return bounding box of normsubpathitem"""
 107         pass
 108
 109     def cbox(self):
 110         """return control box of normsubpathitem
 111
 112         The control box also fully encloses the normsubpathitem but in the case of a Bezier
 113         curve it is not the minimal box doing so. On the other hand, it is much faster
 114         to calculate.
 115         """
 116         pass
 117
 118     def curveradius_pt(self, params):
 119         """return the curvature radius at params in pts
 120
 121         The curvature radius is the inverse of the curvature. When the
 122         curvature is 0, None is returned. Note that this radius can be negative
 123         or positive, depending on the sign of the curvature."""
 124         pass
 125
 126     def intersect(self, other, epsilon):
 127         """intersect self with other normsubpathitem"""
 128         pass
 129
 130     def modifiedbegin_pt(self, x_pt, y_pt):
 131         """return a normsubpathitem with a modified beginning point"""
 132         pass
 133
 134     def modifiedend_pt(self, x_pt, y_pt):
 135         """return a normsubpathitem with a modified end point"""
 136         pass
 137
 138     def _paramtoarclen_pt(self, param, epsilon):
 139         """return a tuple of arc lengths and the total arc length in pts"""
 140         pass
 141
 142     def pathitem(self):
 143         """return pathitem corresponding to normsubpathitem"""
 144
 145     def reversed(self):
 146         """return reversed normsubpathitem"""
 147         pass
 148
 149     def rotation(self, params):
 150         """return rotation trafos (i.e. trafos without translations) at params"""
 151         pass
 152
 153     def segments(self, params):
 154         """return segments of the normsubpathitem
 155
 156         The returned list of normsubpathitems for the segments between
 157         the params. params needs to contain at least two values.
 158         """
 159         pass
 160
 161     def trafo(self, params):
 162         """return transformations at params"""
 163
 164     def transformed(self, trafo):
 165         """return transformed normsubpathitem according to trafo"""
 166         pass
 167
 168     def outputPS(self, file, writer, context):
 169         """write PS code corresponding to normsubpathitem to file"""
 170         pass
 171
 172     def outputPDF(self, file, writer, context):
 173         """write PDF code corresponding to normsubpathitem to file"""
 174         pass
 175
 176
 177 class normline_pt(normsubpathitem):
 178
 179     """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)"""
 180
 181     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt"
 182
 183     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt):
 184         self.x0_pt = x0_pt
 185         self.y0_pt = y0_pt
 186         self.x1_pt = x1_pt
 187         self.y1_pt = y1_pt
 188
 189     def __str__(self):
 190         return "normline_pt(%g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt)
 191
 192     def _arclentoparam_pt(self, lengths_pt, epsilon):
 193         # do self.arclen_pt inplace for performance reasons
 194         l_pt = math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
 195         return [length_pt/l_pt for length_pt in lengths_pt], l_pt
 196
 197     def arclentoparam_pt(self, lengths_pt, epsilon):
 198         """return a tuple of params"""
 199         return self._arclentoparam_pt(lengths_pt, epsilon)[0]
 200
 201     def arclen_pt(self,  epsilon):
 202         return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
 203
 204     def at_pt(self, params):
 205         return [(self.x0_pt+(self.x1_pt-self.x0_pt)*t, self.y0_pt+(self.y1_pt-self.y0_pt)*t)
 206                 for t in params]
 207
 208     def atbegin_pt(self):
 209         return self.x0_pt, self.y0_pt
 210
 211     def atend_pt(self):
 212         return self.x1_pt, self.y1_pt
 213
 214     def bbox(self):
 215         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt), min(self.y0_pt, self.y1_pt),
 216                             max(self.x0_pt, self.x1_pt), max(self.y0_pt, self.y1_pt))
 217
 218     cbox = bbox
 219
 220     def curveradius_pt(self, params):
 221         return [None] * len(params)
 222
 223     def intersect(self, other, epsilon):
 224         if isinstance(other, normline_pt):
 225             a_deltax_pt = self.x1_pt - self.x0_pt
 226             a_deltay_pt = self.y1_pt - self.y0_pt
 227
 228             b_deltax_pt = other.x1_pt - other.x0_pt
 229             b_deltay_pt = other.y1_pt - other.y0_pt
 230             try:
 231                 det = 1.0 / (b_deltax_pt * a_deltay_pt - b_deltay_pt * a_deltax_pt)
 232             except ArithmeticError:
 233                 return []
 234
 235             ba_deltax0_pt = other.x0_pt - self.x0_pt
 236             ba_deltay0_pt = other.y0_pt - self.y0_pt
 237
 238             a_t = (b_deltax_pt * ba_deltay0_pt - b_deltay_pt * ba_deltax0_pt) * det
 239             b_t = (a_deltax_pt * ba_deltay0_pt - a_deltay_pt * ba_deltax0_pt) * det
 240
 241             # check for intersections out of bound
 242             # TODO: we might allow for a small out of bound errors.
 243             if not (0<=a_t<=1 and 0<=b_t<=1):
 244                 return []
 245
 246             # return parameters of intersection
 247             return [(a_t, b_t)]
 248         else:
 249             return [(s_t, o_t) for o_t, s_t in other.intersect(self, epsilon)]
 250
 251     def modifiedbegin_pt(self, x_pt, y_pt):
 252         return normline_pt(x_pt, y_pt, self.x1_pt, self.y1_pt)
 253
 254     def modifiedend_pt(self, x_pt, y_pt):
 255         return normline_pt(self.x0_pt, self.y0_pt, x_pt, y_pt)
 256
 257     def _paramtoarclen_pt(self, params, epsilon):
 258         totalarclen_pt = self.arclen_pt(epsilon)
 259         arclens_pt = [totalarclen_pt * param for param in params + [1]]
 260         return arclens_pt[:-1], arclens_pt[-1]
 261
 262     def pathitem(self):
 263         return path.lineto_pt(self.x1_pt, self.y1_pt)
 264
 265     def reversed(self):
 266         return normline_pt(self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
 267
 268     def rotation(self, params):
 269         return [trafo.rotate(degrees(math.atan2(self.y1_pt-self.y0_pt, self.x1_pt-self.x0_pt)))]*len(params)
 270
 271     def segments(self, params):
 272         if len(params) < 2:
 273             raise ValueError("at least two parameters needed in segments")
 274         result = []
 275         xl_pt = yl_pt = None
 276         for t in params:
 277             xr_pt = self.x0_pt + (self.x1_pt-self.x0_pt)*t
 278             yr_pt = self.y0_pt + (self.y1_pt-self.y0_pt)*t
 279             if xl_pt is not None:
 280                 result.append(normline_pt(xl_pt, yl_pt, xr_pt, yr_pt))
 281             xl_pt = xr_pt
 282             yl_pt = yr_pt
 283         return result
 284
 285     def trafo(self, params):
 286         rotate = trafo.rotate(degrees(math.atan2(self.y1_pt-self.y0_pt, self.x1_pt-self.x0_pt)))
 287         return [trafo.translate_pt(*at_pt) * rotate
 288                 for param, at_pt in zip(params, self.at_pt(params))]
 289
 290     def transformed(self, trafo):
 291         return normline_pt(*(trafo.apply_pt(self.x0_pt, self.y0_pt) + trafo.apply_pt(self.x1_pt, self.y1_pt)))
 292
 293     def outputPS(self, file, writer, context):
 294         file.write("%g %g lineto\n" % (self.x1_pt, self.y1_pt))
 295
 296     def outputPDF(self, file, writer, context):
 297         file.write("%f %f l\n" % (self.x1_pt, self.y1_pt))
 298
 299
 300 class normcurve_pt(normsubpathitem):
 301
 302     """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)"""
 303
 304     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
 305
 306     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
 307         self.x0_pt = x0_pt
 308         self.y0_pt = y0_pt
 309         self.x1_pt = x1_pt
 310         self.y1_pt = y1_pt
 311         self.x2_pt = x2_pt
 312         self.y2_pt = y2_pt
 313         self.x3_pt = x3_pt
 314         self.y3_pt = y3_pt
 315
 316     def __str__(self):
 317         return "normcurve_pt(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt,
 318                                                                  self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt)
 319
 320     def _midpointsplit(self, epsilon):
 321         """split curve into two parts
 322
 323         Helper method to reduce the complexity of a problem by turning
 324         a normcurve_pt into several normline_pt segments. This method
 325         returns normcurve_pt instances only, when they are not yet straight
 326         enough to be replaceable by normcurve_pt instances. Thus a recursive
 327         midpointsplitting will turn a curve into line segments with the
 328         given precision epsilon.
 329         """
 330
 331         # first, we have to calculate the  midpoints between adjacent
 332         # control points
 333         x01_pt = 0.5*(self.x0_pt + self.x1_pt)
 334         y01_pt = 0.5*(self.y0_pt + self.y1_pt)
 335         x12_pt = 0.5*(self.x1_pt + self.x2_pt)
 336         y12_pt = 0.5*(self.y1_pt + self.y2_pt)
 337         x23_pt = 0.5*(self.x2_pt + self.x3_pt)
 338         y23_pt = 0.5*(self.y2_pt + self.y3_pt)
 339
 340         # In the next iterative step, we need the midpoints between 01 and 12
 341         # and between 12 and 23
 342         x01_12_pt = 0.5*(x01_pt + x12_pt)
 343         y01_12_pt = 0.5*(y01_pt + y12_pt)
 344         x12_23_pt = 0.5*(x12_pt + x23_pt)
 345         y12_23_pt = 0.5*(y12_pt + y23_pt)
 346
 347         # Finally the midpoint is given by
 348         xmidpoint_pt = 0.5*(x01_12_pt + x12_23_pt)
 349         ymidpoint_pt = 0.5*(y01_12_pt + y12_23_pt)
 350
 351         # Before returning the normcurves we check whether we can
 352         # replace them by normlines within an error of epsilon pts.
 353         # The maximal error value is given by the modulus of the
 354         # difference between the length of the control polygon
 355         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|), which consitutes an upper
 356         # bound for the length, and the length of the straight line
 357         # between start and end point of the normcurve (i.e. |P3-P1|),
 358         # which represents a lower bound.
 359         upperlen1 = (math.hypot(x01_pt - self.x0_pt, y01_pt - self.y0_pt) +
 360                      math.hypot(x01_12_pt - x01_pt, y01_12_pt - y01_pt) +
 361                      math.hypot(xmidpoint_pt - x01_12_pt, ymidpoint_pt - y01_12_pt))
 362         lowerlen1 = math.hypot(xmidpoint_pt - self.x0_pt, ymidpoint_pt - self.y0_pt)
 363         if upperlen1-lowerlen1 < epsilon:
 364             c1 = normline_pt(self.x0_pt, self.y0_pt, xmidpoint_pt, ymidpoint_pt)
 365         else:
 366             c1 = normcurve_pt(self.x0_pt, self.y0_pt,
 367                               x01_pt, y01_pt,
 368                               x01_12_pt, y01_12_pt,
 369                               xmidpoint_pt, ymidpoint_pt)
 370
 371         upperlen2 = (math.hypot(x12_23_pt - xmidpoint_pt, y12_23_pt - ymidpoint_pt) +
 372                      math.hypot(x23_pt - x12_23_pt, y23_pt - y12_23_pt) +
 373                      math.hypot(self.x3_pt - x23_pt, self.y3_pt - y23_pt))
 374         lowerlen2 = math.hypot(self.x3_pt - xmidpoint_pt, self.y3_pt - ymidpoint_pt)
 375         if upperlen2-lowerlen2 < epsilon:
 376             c2 = normline_pt(xmidpoint_pt, ymidpoint_pt, self.x3_pt, self.y3_pt)
 377         else:
 378             c2 = normcurve_pt(xmidpoint_pt, ymidpoint_pt,
 379                               x12_23_pt, y12_23_pt,
 380                               x23_pt, y23_pt,
 381                               self.x3_pt, self.y3_pt)
 382
 383         return c1, c2
 384
 385     def _arclentoparam_pt(self, lengths_pt, epsilon):
 386         a, b = self._midpointsplit(epsilon)
 387         params_a, arclen_a_pt = a._arclentoparam_pt(lengths_pt, epsilon)
 388         params_b, arclen_b_pt = b._arclentoparam_pt([length_pt - arclen_a_pt for length_pt in lengths_pt], epsilon)
 389         params = []
 390         for param_a, param_b, length_pt in zip(params_a, params_b, lengths_pt):
 391             if length_pt > arclen_a_pt:
 392                 params.append(0.5+0.5*param_b)
 393             else:
 394                 params.append(0.5*param_a)
 395         return params, arclen_a_pt + arclen_b_pt
 396
 397     def arclentoparam_pt(self, lengths_pt, epsilon):
 398         """return a tuple of params"""
 399         return self._arclentoparam_pt(lengths_pt, epsilon)[0]
 400
 401     def arclen_pt(self, epsilon):
 402         a, b = self._midpointsplit(epsilon)
 403         return a.arclen_pt(epsilon) + b.arclen_pt(epsilon)
 404
 405     def at_pt(self, params):
 406         return [( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t +
 407                   (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt          )*t*t +
 408                   (-3*self.x0_pt+3*self.x1_pt                      )*t +
 409                   self.x0_pt,
 410                   (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t +
 411                   (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt          )*t*t +
 412                   (-3*self.y0_pt+3*self.y1_pt                      )*t +
 413                   self.y0_pt )
 414                 for t in params]
 415
 416     def atbegin_pt(self):
 417         return self.x0_pt, self.y0_pt
 418
 419     def atend_pt(self):
 420         return self.x3_pt, self.y3_pt
 421
 422     def bbox(self):
 423         xmin_pt, xmax_pt = path._bezierpolyrange(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt)
 424         ymin_pt, ymax_pt = path._bezierpolyrange(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt)
 425         return bbox.bbox_pt(xmin_pt, ymin_pt, xmax_pt, ymax_pt)
 426
 427     def cbox(self):
 428         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
 429                             min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt),
 430                             max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
 431                             max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt))
 432
 433     def curveradius_pt(self, params):
 434         result = []
 435         for param in params:
 436             xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) +
 437                      6 * (1-param)*param * (-self.x1_pt + self.x2_pt) +
 438                      3 * param*param * (-self.x2_pt + self.x3_pt) )
 439             ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) +
 440                      6 * (1-param)*param * (-self.y1_pt + self.y2_pt) +
 441                      3 * param*param * (-self.y2_pt + self.y3_pt) )
 442             xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) +
 443                       6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) )
 444             yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) +
 445                       6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) )
 446
 447             try:
 448                 radius = (xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot)
 449             except:
 450                 radius = None
 451
 452             result.append(radius)
 453
 454         return result
 455
 456     def intersect(self, other, epsilon):
 457         # There can be no intersection point, when the control boxes are not
 458         # overlapping. Note that we use the control box instead of the bounding
 459         # box here, because the former can be calculated more efficiently for
 460         # Bezier curves.
 461         if not self.cbox().intersects(other.cbox()):
 462             return []
 463         a, b = self._midpointsplit(epsilon)
 464         # To improve the performance in the general case we alternate the
 465         # splitting process between the two normsubpathitems
 466         return ( [(    0.5*a_t, o_t) for o_t, a_t in other.intersect(a, epsilon)] +
 467                  [(0.5+0.5*b_t, o_t) for o_t, b_t in other.intersect(b, epsilon)] )
 468
 469     def modifiedbegin_pt(self, x_pt, y_pt):
 470         return normcurve_pt(x_pt, y_pt,
 471                             self.x1_pt, self.y1_pt,
 472                             self.x2_pt, self.y2_pt,
 473                             self.x3_pt, self.y3_pt)
 474
 475     def modifiedend_pt(self, x_pt, y_pt):
 476         return normcurve_pt(self.x0_pt, self.y0_pt,
 477                             self.x1_pt, self.y1_pt,
 478                             self.x2_pt, self.y2_pt,
 479                             x_pt, y_pt)
 480
 481     def _paramtoarclen_pt(self, params, epsilon):
 482         arclens_pt = [segment.arclen_pt(epsilon) for segment in self.segments([0] + list(params) + [1])]
 483         for i in range(1, len(arclens_pt)):
 484             arclens_pt[i] += arclens_pt[i-1]
 485         return arclens_pt[:-1], arclens_pt[-1]
 486
 487     def pathitem(self):
 488         return path.curveto_pt(self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt)
 489
 490     def reversed(self):
 491         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)
 492
 493     def rotation(self, params):
 494         result = []
 495         for param in params:
 496             tdx_pt = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
 497                       2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt           )*param +
 498                         (-3*self.x0_pt+3*self.x1_pt                        ))
 499             tdy_pt = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
 500                       2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt           )*param +
 501                         (-3*self.y0_pt+3*self.y1_pt                        ))
 502             result.append(trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt))))
 503         return result
 504
 505     def segments(self, params):
 506         if len(params) < 2:
 507             raise ValueError("at least two parameters needed in segments")
 508
 509         # first, we calculate the coefficients corresponding to our
 510         # original bezier curve. These represent a useful starting
 511         # point for the following change of the polynomial parameter
 512         a0x_pt = self.x0_pt
 513         a0y_pt = self.y0_pt
 514         a1x_pt = 3*(-self.x0_pt+self.x1_pt)
 515         a1y_pt = 3*(-self.y0_pt+self.y1_pt)
 516         a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt)
 517         a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt)
 518         a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt
 519         a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt
 520
 521         result = []
 522
 523         for i in range(len(params)-1):
 524             t1 = params[i]
 525             dt = params[i+1]-t1
 526
 527             # [t1,t2] part
 528             #
 529             # the new coefficients of the [t1,t1+dt] part of the bezier curve
 530             # are then given by expanding
 531             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
 532             #  a3*(t1+dt*u)**3 in u, yielding
 533             #
 534             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
 535             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
 536             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
 537             #   a3*dt**3                         * u**3
 538             #
 539             # from this values we obtain the new control points by inversion
 540             #
 541             # TODO: we could do this more efficiently by reusing for
 542             # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
 543             # Bezier curve
 544
 545             x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1
 546             y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1
 547             x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt
 548             y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt
 549             x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt
 550             y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt
 551             x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt
 552             y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt
 553
 554             result.append(normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
 555
 556         return result
 557
 558     def trafo(self, params):
 559         result = []
 560         for param, at_pt in zip(params, self.at_pt(params)):
 561             tdx_pt = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
 562                       2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt           )*param +
 563                         (-3*self.x0_pt+3*self.x1_pt                        ))
 564             tdy_pt = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
 565                       2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt           )*param +
 566                         (-3*self.y0_pt+3*self.y1_pt                        ))
 567             result.append(trafo.translate_pt(*at_pt) * trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt))))
 568         return result
 569
 570     def transformed(self, trafo):
 571         x0_pt, y0_pt = trafo.apply_pt(self.x0_pt, self.y0_pt)
 572         x1_pt, y1_pt = trafo.apply_pt(self.x1_pt, self.y1_pt)
 573         x2_pt, y2_pt = trafo.apply_pt(self.x2_pt, self.y2_pt)
 574         x3_pt, y3_pt = trafo.apply_pt(self.x3_pt, self.y3_pt)
 575         return normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt)
 576
 577     def outputPS(self, file, writer, context):
 578         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))
 579
 580     def outputPDF(self, file, writer, context):
 581         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))
 582
 583
 584 ################################################################################
 585 # normsubpath
 586 ################################################################################
 587
 588 class normsubpath:
 589
 590     """sub path of a normalized path
 591
 592     A subpath consists of a list of normsubpathitems, i.e., normlines_pt and
 593     normcurves_pt and can either be closed or not.
 594
 595     Some invariants, which have to be obeyed:
 596     - All normsubpathitems have to be longer than epsilon pts.
 597     - At the end there may be a normline (stored in self.skippedline) whose
 598       length is shorter than epsilon -- it has to be taken into account
 599       when adding further normsubpathitems
 600     - The last point of a normsubpathitem and the first point of the next
 601       element have to be equal.
 602     - When the path is closed, the last point of last normsubpathitem has
 603       to be equal to the first point of the first normsubpathitem.
 604     - epsilon might be none, disallowing any numerics, but allowing for
 605       arbitrary short paths. This is used in pdf output, where all paths need
 606       to be transformed to normpaths.
 607     """
 608
 609     __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline"
 610
 611     def __init__(self, normsubpathitems=[], closed=0, epsilon=helper.nodefault):
 612         """construct a normsubpath"""
 613         if epsilon is helper.nodefault:
 614             epsilon = _epsilon
 615         self.epsilon = epsilon
 616         # If one or more items appended to the normsubpath have been
 617         # skipped (because their total length was shorter than epsilon),
 618         # we remember this fact by a line because we have to take it
 619         # properly into account when appending further normsubpathitems
 620         self.skippedline = None
 621
 622         self.normsubpathitems = []
 623         self.closed = 0
 624
 625         # a test (might be temporary)
 626         for anormsubpathitem in normsubpathitems:
 627             assert isinstance(anormsubpathitem, normsubpathitem), "only list of normsubpathitem instances allowed"
 628
 629         self.extend(normsubpathitems)
 630
 631         if closed:
 632             self.close()
 633
 634     def __getitem__(self, i):
 635         """return normsubpathitem i"""
 636         return self.normsubpathitems[i]
 637
 638     def __len__(self):
 639         """return number of normsubpathitems"""
 640         return len(self.normsubpathitems)
 641
 642     def __str__(self):
 643         l = ", ".join(map(str, self.normsubpathitems))
 644         if self.closed:
 645             return "normsubpath([%s], closed=1)" % l
 646         else:
 647             return "normsubpath([%s])" % l
 648
 649     def _distributeparams(self, params):
 650         """return a dictionary mapping normsubpathitemindices to a tuple
 651         of a paramindices and normsubpathitemparams.
 652
 653         normsubpathitemindex specifies a normsubpathitem containing
 654         one or several positions.  paramindex specify the index of the
 655         param in the original list and normsubpathitemparam is the
 656         parameter value in the normsubpathitem.
 657         """
 658
 659         result = {}
 660         for i, param in enumerate(params):
 661             if param > 0:
 662                 index = int(param)
 663                 if index > len(self.normsubpathitems) - 1:
 664                     index = len(self.normsubpathitems) - 1
 665             else:
 666                 index = 0
 667             result.setdefault(index, ([], []))
 668             result[index][0].append(i)
 669             result[index][1].append(param - index)
 670         return result
 671
 672     def append(self, anormsubpathitem):
 673         """append normsubpathitem
 674
 675         Fails on closed normsubpath.
 676         """
 677         if self.epsilon is None:
 678             self.normsubpathitems.append(anormsubpathitem)
 679         else:
 680             # consitency tests (might be temporary)
 681             assert isinstance(anormsubpathitem, normsubpathitem), "only normsubpathitem instances allowed"
 682             if self.skippedline:
 683                 assert math.hypot(*[x-y for x, y in zip(self.skippedline.atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match"
 684             elif self.normsubpathitems:
 685                 assert math.hypot(*[x-y for x, y in zip(self.normsubpathitems[-1].atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match"
 686
 687             if self.closed:
 688                 raise path.PathException("Cannot append to closed normsubpath")
 689
 690             if self.skippedline:
 691                 xs_pt, ys_pt = self.skippedline.atbegin_pt()
 692             else:
 693                 xs_pt, ys_pt = anormsubpathitem.atbegin_pt()
 694             xe_pt, ye_pt = anormsubpathitem.atend_pt()
 695
 696             if (math.hypot(xe_pt-xs_pt, ye_pt-ys_pt) >= self.epsilon or
 697                 anormsubpathitem.arclen_pt(self.epsilon) >= self.epsilon):
 698                 if self.skippedline:
 699                     anormsubpathitem = anormsubpathitem.modifiedbegin_pt(xs_pt, ys_pt)
 700                 self.normsubpathitems.append(anormsubpathitem)
 701                 self.skippedline = None
 702             else:
 703                 self.skippedline = normline_pt(xs_pt, ys_pt, xe_pt, ye_pt)
 704
 705     def arclen_pt(self):
 706         """return arc length in pts"""
 707         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normsubpathitems])
 708
 709     def _arclentoparam_pt(self, lengths_pt):
 710         """return a tuple of params and the total length arc length in pts"""
 711         # work on a copy which is counted down to negative values
 712         lengths_pt = lengths_pt[:]
 713         results = [None] * len(lengths_pt)
 714
 715         totalarclen = 0
 716         for normsubpathindex, normsubpathitem in enumerate(self.normsubpathitems):
 717             params, arclen = normsubpathitem._arclentoparam_pt(lengths_pt, self.epsilon)
 718             for i in range(len(results)):
 719                 if results[i] is None:
 720                     lengths_pt[i] -= arclen
 721                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpathitems) - 1:
 722                         # overwrite the results until the length has become negative
 723                         results[i] = normsubpathindex + params[i]
 724             totalarclen += arclen
 725
 726         return results, totalarclen
 727
 728     def arclentoparam_pt(self, lengths_pt):
 729         """return a tuple of params"""
 730         return self._arclentoparam_pt(lengths_pt)[0]
 731
 732     def at_pt(self, params):
 733         """return coordinates at params in pts"""
 734         result = [None] * len(params)
 735         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
 736             for index, point_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].at_pt(params)):
 737                 result[index] = point_pt
 738         return result
 739
 740     def atbegin_pt(self):
 741         """return coordinates of first point in pts"""
 742         if not self.normsubpathitems and self.skippedline:
 743             return self.skippedline.atbegin_pt()
 744         return self.normsubpathitems[0].atbegin_pt()
 745
 746     def atend_pt(self):
 747         """return coordinates of last point in pts"""
 748         if self.skippedline:
 749             return self.skippedline.atend_pt()
 750         return self.normsubpathitems[-1].atend_pt()
 751
 752     def bbox(self):
 753         """return bounding box of normsubpath"""
 754         if self.normsubpathitems:
 755             abbox = self.normsubpathitems[0].bbox()
 756             for anormpathitem in self.normsubpathitems[1:]:
 757                 abbox += anormpathitem.bbox()
 758             return abbox
 759         else:
 760             return None
 761
 762     def close(self):
 763         """close subnormpath
 764
 765         Fails on closed normsubpath.
 766         """
 767         if self.closed:
 768             raise path.PathException("Cannot close already closed normsubpath")
 769         if not self.normsubpathitems:
 770             if self.skippedline is None:
 771                 raise path.PathException("Cannot close empty normsubpath")
 772             else:
 773                 raise path.PathException("Normsubpath too short, cannot be closed")
 774
 775         xs_pt, ys_pt = self.normsubpathitems[-1].atend_pt()
 776         xe_pt, ye_pt = self.normsubpathitems[0].atbegin_pt()
 777         self.append(normline_pt(xs_pt, ys_pt, xe_pt, ye_pt))
 778         self.flushskippedline()
 779         self.closed = 1
 780
 781     def copy(self):
 782         """return copy of normsubpath"""
 783         # Since normsubpathitems are never modified inplace, we just
 784         # need to copy the normsubpathitems list. We do not pass the
 785         # normsubpathitems to the constructor to not repeat the checks
 786         # for minimal length of each normsubpathitem.
 787         result = normsubpath(epsilon=self.epsilon)
 788         result.normsubpathitems = self.normsubpathitems[:]
 789         result.closed = self.closed
 790
 791         # We can share the reference to skippedline, since it is a
 792         # normsubpathitem as well and thus not modified in place either.
 793         result.skippedline = self.skippedline
 794
 795         return result
 796
 797     def curveradius_pt(self, params):
 798         """return the curvature radius at params in pts
 799
 800         The curvature radius is the inverse of the curvature. When the
 801         curvature is 0, None is returned. Note that this radius can be negative
 802         or positive, depending on the sign of the curvature."""
 803         result = [None] * len(params)
 804         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
 805             for index, radius_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].curveradius_pt(params)):
 806                 result[index] = radius_pt
 807         return result
 808
 809     def extend(self, normsubpathitems):
 810         """extend path by normsubpathitems
 811
 812         Fails on closed normsubpath.
 813         """
 814         for normsubpathitem in normsubpathitems:
 815             self.append(normsubpathitem)
 816
 817     def flushskippedline(self):
 818         """flush the skippedline, i.e. apply it to the normsubpath
 819
 820         remove the skippedline by modifying the end point of the existing normsubpath
 821         """
 822         while self.skippedline:
 823             try:
 824                 lastnormsubpathitem = self.normsubpathitems.pop()
 825             except IndexError:
 826                 raise ValueError("normsubpath too short to flush the skippedline")
 827             lastnormsubpathitem = lastnormsubpathitem.modifiedend_pt(*self.skippedline.atend_pt())
 828             self.skippedline = None
 829             self.append(lastnormsubpathitem)
 830
 831     def intersect(self, other):
 832         """intersect self with other normsubpath
 833
 834         Returns a tuple of lists consisting of the parameter values
 835         of the intersection points of the corresponding normsubpath.
 836         """
 837         intersections_a = []
 838         intersections_b = []
 839         epsilon = min(self.epsilon, other.epsilon)
 840         # Intersect all subpaths of self with the subpaths of other, possibly including
 841         # one intersection point several times
 842         for t_a, pitem_a  in enumerate(self.normsubpathitems):
 843             for t_b, pitem_b in enumerate(other.normsubpathitems):
 844                 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon):
 845                     intersections_a.append(intersection_a + t_a)
 846                     intersections_b.append(intersection_b + t_b)
 847
 848         # although intersectipns_a are sorted for the different normsubpathitems,
 849         # within a normsubpathitem, the ordering has to be ensured separately:
 850         intersections = zip(intersections_a, intersections_b)
 851         intersections.sort()
 852         intersections_a = [a for a, b in intersections]
 853         intersections_b = [b for a, b in intersections]
 854
 855         # for symmetry reasons we enumerate intersections_a as well, although
 856         # they are already sorted (note we do not need to sort intersections_a)
 857         intersections_a = zip(intersections_a, range(len(intersections_a)))
 858         intersections_b = zip(intersections_b, range(len(intersections_b)))
 859         intersections_b.sort()
 860
 861         # now we search for intersections points which are closer together than epsilon
 862         # This task is handled by the following function
 863         def closepoints(normsubpath, intersections):
 864             split = normsubpath.segments([0] + [intersection for intersection, index in intersections] + [len(normsubpath)])
 865             result = []
 866             if normsubpath.closed:
 867                 # note that the number of segments of a closed path is off by one
 868                 # compared to an open path
 869                 i = 0
 870                 while i < len(split):
 871                     splitnormsubpath = split[i]
 872                     j = i
 873                     while not splitnormsubpath.normsubpathitems: # i.e. while "is short"
 874                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
 875                         if ip1<ip2:
 876                             result.append((ip1, ip2))
 877                         else:
 878                             result.append((ip2, ip1))
 879                         j += 1
 880                         if j == len(split):
 881                             j = 0
 882                         if j < len(split):
 883                             splitnormsubpath = splitnormsubpath.joined(split[j])
 884                         else:
 885                             break
 886                     i += 1
 887             else:
 888                 i = 1
 889                 while i < len(split)-1:
 890                     splitnormsubpath = split[i]
 891                     j = i
 892                     while not splitnormsubpath.normsubpathitems: # i.e. while "is short"
 893                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
 894                         if ip1<ip2:
 895                             result.append((ip1, ip2))
 896                         else:
 897                             result.append((ip2, ip1))
 898                         j += 1
 899                         if j < len(split)-1:
 900                             splitnormsubpath = splitnormsubpath.joined(split[j])
 901                         else:
 902                             break
 903                     i += 1
 904             return result
 905
 906         closepoints_a = closepoints(self, intersections_a)
 907         closepoints_b = closepoints(other, intersections_b)
 908
 909         # map intersection point to lowest point which is equivalent to the
 910         # point
 911         equivalentpoints = list(range(len(intersections_a)))
 912
 913         for closepoint_a in closepoints_a:
 914             for closepoint_b in closepoints_b:
 915                 if closepoint_a == closepoint_b:
 916                     for i in range(closepoint_a[1], len(equivalentpoints)):
 917                         if equivalentpoints[i] == closepoint_a[1]:
 918                             equivalentpoints[i] = closepoint_a[0]
 919
 920         # determine the remaining intersection points
 921         intersectionpoints = {}
 922         for point in equivalentpoints:
 923             intersectionpoints[point] = 1
 924
 925         # build result
 926         result = []
 927         intersectionpointskeys = intersectionpoints.keys()
 928         intersectionpointskeys.sort()
 929         for point in intersectionpointskeys:
 930             for intersection_a, index_a in intersections_a:
 931                 if index_a == point:
 932                     result_a = intersection_a
 933             for intersection_b, index_b in intersections_b:
 934                 if index_b == point:
 935                     result_b = intersection_b
 936             result.append((result_a, result_b))
 937         # note that the result is sorted in a, since we sorted
 938         # intersections_a in the very beginning
 939
 940         return [x for x, y in result], [y for x, y in result]
 941
 942     def join(self, other):
 943         """join other normsubpath inplace
 944
 945         Fails on closed normsubpath. Fails to join closed normsubpath.
 946         """
 947         if other.closed:
 948             raise path.PathException("Cannot join closed normsubpath")
 949
 950         # insert connection line
 951         x0_pt, y0_pt = self.atend_pt()
 952         x1_pt, y1_pt = other.atbegin_pt()
 953         self.append(normline_pt(x0_pt, y0_pt, x1_pt, y1_pt))
 954
 955         # append other normsubpathitems
 956         self.extend(other.normsubpathitems)
 957         if other.skippedline:
 958             self.append(other.skippedline)
 959
 960     def joined(self, other):
 961         """return joined self and other
 962
 963         Fails on closed normsubpath. Fails to join closed normsubpath.
 964         """
 965         result = self.copy()
 966         result.join(other)
 967         return result
 968
 969     def _paramtoarclen_pt(self, params):
 970         """return a tuple of arc lengths and the total arc length in pts"""
 971         result = [None] * len(params)
 972         totalarclen_pt = 0
 973         distributeparams = self._distributeparams(params)
 974         for normsubpathitemindex in range(len(self.normsubpathitems)):
 975             if distributeparams.has_key(normsubpathitemindex):
 976                 indices, params = distributeparams[normsubpathitemindex]
 977                 arclens_pt, normsubpathitemarclen_pt = self.normsubpathitems[normsubpathitemindex]._paramtoarclen_pt(params, self.epsilon)
 978                 for index, arclen_pt in zip(indices, arclens_pt):
 979                     result[index] = totalarclen_pt + arclen_pt
 980                 totalarclen_pt += normsubpathitemarclen_pt
 981             else:
 982                 totalarclen_pt += self.normsubpathitems[normsubpathitemindex].arclen_pt(self.epsilon)
 983         return result, totalarclen_pt
 984
 985     def pathitems(self):
 986         """return list of pathitems"""
 987         if not self.normsubpathitems:
 988             return []
 989
 990         # remove trailing normline_pt of closed subpaths
 991         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
 992             normsubpathitems = self.normsubpathitems[:-1]
 993         else:
 994             normsubpathitems = self.normsubpathitems
 995
 996         result = [path.moveto_pt(*self.atbegin_pt())]
 997         for normsubpathitem in normsubpathitems:
 998             result.append(normsubpathitem.pathitem())
 999         if self.closed:
1000             result.append(path.closepath())
1001         return result
1002
1003     def reversed(self):
1004         """return reversed normsubpath"""
1005         nnormpathitems = []
1006         for i in range(len(self.normsubpathitems)):
1007             nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed())
1008         return normsubpath(nnormpathitems, self.closed)
1009
1010     def rotation(self, params):
1011         """return rotations at params"""
1012         result = [None] * len(params)
1013         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
1014             for index, rotation in zip(indices, self.normsubpathitems[normsubpathitemindex].rotation(params)):
1015                 result[index] = rotation
1016         return result
1017
1018     def segments(self, params):
1019         """return segments of the normsubpath
1020
1021         The returned list of normsubpaths for the segments between
1022         the params. params need to contain at least two values.
1023
1024         For a closed normsubpath the last segment result is joined to
1025         the first one when params starts with 0 and ends with len(self).
1026         or params starts with len(self) and ends with 0. Thus a segments
1027         operation on a closed normsubpath might properly join those the
1028         first and the last part to take into account the closed nature of
1029         the normsubpath. However, for intermediate parameters, closepath
1030         is not taken into account, i.e. when walking backwards you do not
1031         loop over the closepath forwardly. The special values 0 and
1032         len(self) for the first and the last parameter should be given as
1033         integers, i.e. no finite precision is used when checking for
1034         equality."""
1035
1036         if len(params) < 2:
1037             raise ValueError("at least two parameters needed in segments")
1038
1039         result = [normsubpath(epsilon=self.epsilon)]
1040
1041         # instead of distribute the parameters, we need to keep their
1042         # order and collect parameters for the needed segments of
1043         # normsubpathitem with index collectindex
1044         collectparams = []
1045         collectindex = None
1046         for param in params:
1047             # calculate index and parameter for corresponding normsubpathitem
1048             if param > 0:
1049                 index = int(param)
1050                 if index > len(self.normsubpathitems) - 1:
1051                     index = len(self.normsubpathitems) - 1
1052                 param -= index
1053             else:
1054                 index = 0
1055             if index != collectindex:
1056                 if collectindex is not None:
1057                     # append end point depening on the forthcoming index
1058                     if index > collectindex:
1059                         collectparams.append(1)
1060                     else:
1061                         collectparams.append(0)
1062                     # get segments of the normsubpathitem and add them to the result
1063                     segments = self.normsubpathitems[collectindex].segments(collectparams)
1064                     result[-1].append(segments[0])
1065                     result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]])
1066                     # add normsubpathitems and first segment parameter to close the
1067                     # gap to the forthcoming index
1068                     if index > collectindex:
1069                         for i in range(collectindex+1, index):
1070                             result[-1].append(self.normsubpathitems[i])
1071                         collectparams = [0]
1072                     else:
1073                         for i in range(collectindex-1, index, -1):
1074                             result[-1].append(self.normsubpathitems[i].reversed())
1075                         collectparams = [1]
1076                 collectindex = index
1077             collectparams.append(param)
1078         # add remaining collectparams to the result
1079         segments = self.normsubpathitems[collectindex].segments(collectparams)
1080         result[-1].append(segments[0])
1081         result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]])
1082
1083         if self.closed:
1084             # join last and first segment together if the normsubpath was
1085             # originally closed and first and the last parameters are the
1086             # beginning and end points of the normsubpath
1087             if ( ( params[0] == 0 and params[-1] == len(self.normsubpathitems) ) or
1088                  ( params[-1] == 0 and params[0] == len(self.normsubpathitems) ) ):
1089                 result[-1].normsubpathitems.extend(result[0].normsubpathitems)
1090                 result = result[-1:] + result[1:-1]
1091
1092         return result
1093
1094     def trafo(self, params):
1095         """return transformations at params"""
1096         result = [None] * len(params)
1097         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
1098             for index, trafo in zip(indices, self.normsubpathitems[normsubpathitemindex].trafo(params)):
1099                 result[index] = trafo
1100         return result
1101
1102     def transformed(self, trafo):
1103         """return transformed path"""
1104         nnormsubpath = normsubpath(epsilon=self.epsilon)
1105         for pitem in self.normsubpathitems:
1106             nnormsubpath.append(pitem.transformed(trafo))
1107         if self.closed:
1108             nnormsubpath.close()
1109         elif self.skippedline is not None:
1110             nnormsubpath.append(self.skippedline.transformed(trafo))
1111         return nnormsubpath
1112
1113     def outputPS(self, file, writer, context):
1114         # if the normsubpath is closed, we must not output a normline at
1115         # the end
1116         if not self.normsubpathitems:
1117             return
1118         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
1119             assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt"
1120             normsubpathitems = self.normsubpathitems[:-1]
1121         else:
1122             normsubpathitems = self.normsubpathitems
1123         file.write("%g %g moveto\n" % self.atbegin_pt())
1124         for anormsubpathitem in normsubpathitems:
1125             anormsubpathitem.outputPS(file, writer, context)
1126         if self.closed:
1127             file.write("closepath\n")
1128
1129     def outputPDF(self, file, writer, context):
1130         # if the normsubpath is closed, we must not output a normline at
1131         # the end
1132         if not self.normsubpathitems:
1133             return
1134         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
1135             assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt"
1136             normsubpathitems = self.normsubpathitems[:-1]
1137         else:
1138             normsubpathitems = self.normsubpathitems
1139         file.write("%f %f m\n" % self.atbegin_pt())
1140         for anormsubpathitem in normsubpathitems:
1141             anormsubpathitem.outputPDF(file, writer, context)
1142         if self.closed:
1143             file.write("h\n")
1144
1145
1146 ################################################################################
1147 # normpath
1148 ################################################################################
1149
1150 class normpathparam:
1151
1152     """parameter of a certain point along a normpath"""
1153
1154     __slots__ = "normpath", "normsubpathindex", "normsubpathparam"
1155
1156     def __init__(self, normpath, normsubpathindex, normsubpathparam):
1157         self.normpath = normpath
1158         self.normsubpathindex = normsubpathindex
1159         self.normsubpathparam = normsubpathparam
1160         float(normsubpathparam)
1161
1162     def __str__(self):
1163         return "normpathparam(%s, %s, %s)" % (self.normpath, self.normsubpathindex, self.normsubpathparam)
1164
1165     def __add__(self, other):
1166         if isinstance(other, normpathparam):
1167             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1168             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) +
1169                                                   other.normpath.paramtoarclen_pt(other))
1170         else:
1171             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) + unit.topt(other))
1172
1173     __radd__ = __add__
1174
1175     def __sub__(self, other):
1176         if isinstance(other, normpathparam):
1177             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1178             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) -
1179                                                   other.normpath.paramtoarclen_pt(other))
1180         else:
1181             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) - unit.topt(other))
1182
1183     def __rsub__(self, other):
1184         # other has to be a length in this case
1185         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self) + unit.topt(other))
1186
1187     def __mul__(self, factor):
1188         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) * factor)
1189
1190     __rmul__ = __mul__
1191
1192     def __div__(self, divisor):
1193         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) / divisor)
1194
1195     def __neg__(self):
1196         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self))
1197
1198     def __cmp__(self, other):
1199         if isinstance(other, normpathparam):
1200             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1201             return cmp((self.normsubpathindex, self.normsubpathparam), (other.normsubpathindex, other.normsubpathparam))
1202         else:
1203             return cmp(self.normpath.paramtoarclen_pt(self), unit.topt(other))
1204
1205     def arclen_pt(self):
1206         """return arc length in pts corresponding to the normpathparam """
1207         return self.normpath.paramtoarclen_pt(self)
1208
1209     def arclen(self):
1210         """return arc length corresponding to the normpathparam """
1211         return self.normpath.paramtoarclen(self)
1212
1213
1214 def _valueorlistmethod(method):
1215     """Creates a method which takes a single argument or a list and
1216     returns a single value or a list out of method, which always
1217     works on lists."""
1218
1219     def wrappedmethod(self, valueorlist, *args, **kwargs):
1220         try:
1221             for item in valueorlist:
1222                 break
1223         except:
1224             return method(self, [valueorlist], *args, **kwargs)[0]
1225         return method(self, valueorlist, *args, **kwargs)
1226     return wrappedmethod
1227
1228
1229 class normpath(canvas.canvasitem):
1230
1231     """normalized path
1232
1233     A normalized path consists of a list of normsubpaths.
1234     """
1235
1236     def __init__(self, normsubpaths=None):
1237         """construct a normpath from a list of normsubpaths"""
1238
1239         if normsubpaths is None:
1240             self.normsubpaths = [] # make a fresh list
1241         else:
1242             self.normsubpaths = normsubpaths
1243             for subpath in normsubpaths:
1244                 assert isinstance(subpath, normsubpath), "only list of normsubpath instances allowed"
1245
1246     def __add__(self, other):
1247         """create new normpath out of self and other"""
1248         result = self.copy()
1249         result += other
1250         return result
1251
1252     def __iadd__(self, other):
1253         """add other inplace"""
1254         for normsubpath in other.normpath().normsubpaths:
1255             self.normsubpaths.append(normsubpath.copy())
1256         return self
1257
1258     def __getitem__(self, i):
1259         """return normsubpath i"""
1260         return self.normsubpaths[i]
1261
1262     def __len__(self):
1263         """return the number of normsubpaths"""
1264         return len(self.normsubpaths)
1265
1266     def __str__(self):
1267         return "normpath([%s])" % ", ".join(map(str, self.normsubpaths))
1268
1269     def _convertparams(self, params, convertmethod):
1270         """return params with all non-normpathparam arguments converted by convertmethod
1271
1272         usecases:
1273         - self._convertparams(params, self.arclentoparam_pt)
1274         - self._convertparams(params, self.arclentoparam)
1275         """
1276
1277         converttoparams = []
1278         convertparamindices = []
1279         for i, param in enumerate(params):
1280             if not isinstance(param, normpathparam):
1281                 converttoparams.append(param)
1282                 convertparamindices.append(i)
1283         if converttoparams:
1284             params = params[:]
1285             for i, param in zip(convertparamindices, convertmethod(converttoparams)):
1286                 params[i] = param
1287         return params
1288
1289     def _distributeparams(self, params):
1290         """return a dictionary mapping subpathindices to a tuple of a paramindices and subpathparams
1291
1292         subpathindex specifies a subpath containing one or several positions.
1293         paramindex specify the index of the normpathparam in the original list and
1294         subpathparam is the parameter value in the subpath.
1295         """
1296
1297         result = {}
1298         for i, param in enumerate(params):
1299             assert param.normpath is self, "normpathparam has to belong to this path"
1300             result.setdefault(param.normsubpathindex, ([], []))
1301             result[param.normsubpathindex][0].append(i)
1302             result[param.normsubpathindex][1].append(param.normsubpathparam)
1303         return result
1304
1305     def append(self, item):
1306         """append a normsubpath by a normsubpath or a pathitem"""
1307         if isinstance(item, normsubpath):
1308             # the normsubpaths list can be appended by a normsubpath only
1309             self.normsubpaths.append(item)
1310         elif isinstance(item, path.pathitem):
1311             # ... but we are kind and allow for regular path items as well
1312             # in order to make a normpath to behave more like a regular path
1313             context = path.context(*(self.normsubpaths[-1].atend_pt() +
1314                                      self.normsubpaths[-1].atbegin_pt()))
1315             item.updatenormpath(self, context)
1316
1317     def arclen_pt(self):
1318         """return arc length in pts"""
1319         return sum([normsubpath.arclen_pt() for normsubpath in self.normsubpaths])
1320
1321     def arclen(self):
1322         """return arc length"""
1323         return self.arclen_pt() * unit.t_pt
1324
1325     def _arclentoparam_pt(self, lengths_pt):
1326         """return the params matching the given lengths_pt"""
1327         # work on a copy which is counted down to negative values
1328         lengths_pt = lengths_pt[:]
1329         results = [None] * len(lengths_pt)
1330
1331         for normsubpathindex, normsubpath in enumerate(self.normsubpaths):
1332             params, arclen = normsubpath._arclentoparam_pt(lengths_pt)
1333             done = 1
1334             for i, result in enumerate(results):
1335                 if results[i] is None:
1336                     lengths_pt[i] -= arclen
1337                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpaths) - 1:
1338                         # overwrite the results until the length has become negative
1339                         results[i] = normpathparam(self, normsubpathindex, params[i])
1340                     done = 0
1341             if done:
1342                 break
1343
1344         return results
1345
1346     def arclentoparam_pt(self, lengths_pt):
1347         """return the param(s) matching the given length(s)_pt in pts"""
1348         pass
1349     arclentoparam_pt = _valueorlistmethod(_arclentoparam_pt)
1350
1351     def arclentoparam(self, lengths):
1352         """return the param(s) matching the given length(s)"""
1353         return self._arclentoparam_pt([unit.topt(l) for l in lengths])
1354     arclentoparam = _valueorlistmethod(arclentoparam)
1355
1356     def _at_pt(self, params):
1357         """return coordinates of normpath in pts at params"""
1358         result = [None] * len(params)
1359         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1360             for index, point_pt in zip(indices, self.normsubpaths[normsubpathindex].at_pt(params)):
1361                 result[index] = point_pt
1362         return result
1363
1364     def at_pt(self, params):
1365         """return coordinates of normpath in pts at param(s) or lengths in pts"""
1366         return self._at_pt(self._convertparams(params, self.arclentoparam_pt))
1367     at_pt = _valueorlistmethod(at_pt)
1368
1369     def at(self, params):
1370         """return coordinates of normpath at param(s) or arc lengths"""
1371         return [(x_pt * unit.t_pt, y_pt * unit.t_pt)
1372                 for x_pt, y_pt in self._at_pt(self._convertparams(params, self.arclentoparam))]
1373     at = _valueorlistmethod(at)
1374
1375     def atbegin_pt(self):
1376         """return coordinates of the beginning of first subpath in normpath in pts"""
1377         if self.normsubpaths:
1378             return self.normsubpaths[0].atbegin_pt()
1379         else:
1380             raise path.PathException("cannot return first point of empty path")
1381
1382     def atbegin(self):
1383         """return coordinates of the beginning of first subpath in normpath"""
1384         x, y = self.atbegin_pt()
1385         return x * unit.t_pt, y * unit.t_pt
1386
1387     def atend_pt(self):
1388         """return coordinates of the end of last subpath in normpath in pts"""
1389         if self.normsubpaths:
1390             return self.normsubpaths[-1].atend_pt()
1391         else:
1392             raise path.PathException("cannot return last point of empty path")
1393
1394     def atend(self):
1395         """return coordinates of the end of last subpath in normpath"""
1396         x, y = self.atend_pt()
1397         return x * unit.t_pt, y * unit.t_pt
1398
1399     def bbox(self):
1400         """return bbox of normpath"""
1401         abbox = None
1402         for normsubpath in self.normsubpaths:
1403             nbbox =  normsubpath.bbox()
1404             if abbox is None:
1405                 abbox = nbbox
1406             elif nbbox:
1407                 abbox += nbbox
1408         return abbox
1409
1410     def begin(self):
1411         """return param corresponding of the beginning of the normpath"""
1412         if self.normsubpaths:
1413             return normpathparam(self, 0, 0)
1414         else:
1415             raise path.PathException("empty path")
1416
1417     def copy(self):
1418         """return copy of normpath"""
1419         result = normpath()
1420         for normsubpath in self.normsubpaths:
1421             result.append(normsubpath.copy())
1422         return result
1423
1424     def _curveradius_pt(self, params):
1425         """return the curvature radius at params in pts
1426
1427         The curvature radius is the inverse of the curvature. When the
1428         curvature is 0, None is returned. Note that this radius can be negative
1429         or positive, depending on the sign of the curvature."""
1430
1431         result = [None] * len(params)
1432         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1433             for index, radius_pt in zip(indices, self.normsubpaths[normsubpathindex].curveradius_pt(params)):
1434                 result[index] = radius_pt
1435         return result
1436
1437     def curveradius_pt(self, params):
1438         """return the curvature radius in pts at param(s) or arc length(s) in pts
1439
1440         The curvature radius is the inverse of the curvature. When the
1441         curvature is 0, None is returned. Note that this radius can be negative
1442         or positive, depending on the sign of the curvature."""
1443
1444         return self._curveradius_pt(self._convertparams(params, self.arclentoparam_pt))
1445     curveradius_pt = _valueorlistmethod(curveradius_pt)
1446
1447     def curveradius(self, params):
1448         """return the curvature radius at param(s) or arc length(s)
1449
1450         The curvature radius is the inverse of the curvature. When the
1451         curvature is 0, None is returned. Note that this radius can be negative
1452         or positive, depending on the sign of the curvature."""
1453
1454         result = []
1455         for radius_pt in self._curveradius_pt(self._convertparams(params, self.arclentoparam)):
1456             if radius_pt is not None:
1457                 result.append(radius_pt * unit.t_pt)
1458             else:
1459                 result.append(None)
1460         return result
1461     curveradius = _valueorlistmethod(curveradius)
1462
1463     def end(self):
1464         """return param corresponding of the end of the path"""
1465         if self.normsubpaths:
1466             return normpathparam(self, len(self)-1, len(self.normsubpaths[-1]))
1467         else:
1468             raise path.PathException("empty path")
1469
1470     def extend(self, normsubpaths):
1471         """extend path by normsubpaths or pathitems"""
1472         for anormsubpath in normsubpaths:
1473             # use append to properly handle regular path items as well as normsubpaths
1474             self.append(anormsubpath)
1475
1476     def intersect(self, other):
1477         """intersect self with other path
1478
1479         Returns a tuple of lists consisting of the parameter values
1480         of the intersection points of the corresponding normpath.
1481         """
1482         other = other.normpath()
1483
1484         # here we build up the result
1485         intersections = ([], [])
1486
1487         # Intersect all normsubpaths of self with the normsubpaths of
1488         # other.
1489         for ia, normsubpath_a in enumerate(self.normsubpaths):
1490             for ib, normsubpath_b in enumerate(other.normsubpaths):
1491                 for intersection in zip(*normsubpath_a.intersect(normsubpath_b)):
1492                     intersections[0].append(normpathparam(self, ia, intersection[0]))
1493                     intersections[1].append(normpathparam(other, ib, intersection[1]))
1494         return intersections
1495
1496     def join(self, other):
1497         """join other normsubpath inplace
1498
1499         Both normpaths must contain at least one normsubpath.
1500         The last normsubpath of self will be joined to the first
1501         normsubpath of other.
1502         """
1503         if not self.normsubpaths:
1504             raise path.PathException("cannot join to empty path")
1505         if not other.normsubpaths:
1506             raise PathException("cannot join empty path")
1507         self.normsubpaths[-1].join(other.normsubpaths[0])
1508         self.normsubpaths.extend(other.normsubpaths[1:])
1509
1510     def joined(self, other):
1511         """return joined self and other
1512
1513         Both normpaths must contain at least one normsubpath.
1514         The last normsubpath of self will be joined to the first
1515         normsubpath of other.
1516         """
1517         result = self.copy()
1518         result.join(other.normpath())
1519         return result
1520
1521     # << operator also designates joining
1522     __lshift__ = joined
1523
1524     def normpath(self):
1525         """return a normpath, i.e. self"""
1526         return self
1527
1528     def _paramtoarclen_pt(self, params):
1529         """return arc lengths in pts matching the given params"""
1530         result = [None] * len(params)
1531         totalarclen_pt = 0
1532         distributeparams = self._distributeparams(params)
1533         for normsubpathindex in range(max(distributeparams.keys()) + 1):
1534             if distributeparams.has_key(normsubpathindex):
1535                 indices, params = distributeparams[normsubpathindex]
1536                 arclens_pt, normsubpatharclen_pt = self.normsubpaths[normsubpathindex]._paramtoarclen_pt(params)
1537                 for index, arclen_pt in zip(indices, arclens_pt):
1538                     result[index] = totalarclen_pt + arclen_pt
1539                 totalarclen_pt += normsubpatharclen_pt
1540             else:
1541                 totalarclen_pt += self.normsubpaths[normsubpathindex].arclen_pt()
1542         return result
1543
1544     def paramtoarclen_pt(self, params):
1545         """return arc length(s) in pts matching the given param(s)"""
1546     paramtoarclen_pt = _valueorlistmethod(_paramtoarclen_pt)
1547
1548     def paramtoarclen(self, params):
1549         """return arc length(s) matching the given param(s)"""
1550         return [arclen_pt * unit.t_pt for arclen_pt in self._paramtoarclen_pt(params)]
1551     paramtoarclen = _valueorlistmethod(paramtoarclen)
1552
1553     def path(self):
1554         """return path corresponding to normpath"""
1555         pathitems = []
1556         for normsubpath in self.normsubpaths:
1557             pathitems.extend(normsubpath.pathitems())
1558         return path.path(*pathitems)
1559
1560     def reversed(self):
1561         """return reversed path"""
1562         nnormpath = normpath()
1563         for i in range(len(self.normsubpaths)):
1564             nnormpath.normsubpaths.append(self.normsubpaths[-(i+1)].reversed())
1565         return nnormpath
1566
1567     def _rotation(self, params):
1568         """return rotation at params"""
1569         result = [None] * len(params)
1570         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1571             for index, rotation in zip(indices, self.normsubpaths[normsubpathindex].rotation(params)):
1572                 result[index] = rotation
1573         return result
1574
1575     def rotation_pt(self, params):
1576         """return rotation at param(s) or arc length(s) in pts"""
1577         return self._rotation(self._convertparams(params, self.arclentoparam_pt))
1578     rotation_pt = _valueorlistmethod(rotation_pt)
1579
1580     def rotation(self, params):
1581         """return rotation at param(s) or arc length(s)"""
1582         return self._rotation(self._convertparams(params, self.arclentoparam))
1583     rotation = _valueorlistmethod(rotation)
1584
1585     def _split_pt(self, params):
1586         """split path at params and return list of normpaths"""
1587
1588         # instead of distributing the parameters, we need to keep their
1589         # order and collect parameters for splitting of normsubpathitem
1590         # with index collectindex
1591         collectindex = None
1592         for param in params:
1593             if param.normsubpathindex != collectindex:
1594                 if collectindex is not None:
1595                     # append end point depening on the forthcoming index
1596                     if param.normsubpathindex > collectindex:
1597                         collectparams.append(len(self.normsubpaths[collectindex]))
1598                     else:
1599                         collectparams.append(0)
1600                     # get segments of the normsubpath and add them to the result
1601                     segments = self.normsubpaths[collectindex].segments(collectparams)
1602                     result[-1].append(segments[0])
1603                     result.extend([normpath([segment]) for segment in segments[1:]])
1604                     # add normsubpathitems and first segment parameter to close the
1605                     # gap to the forthcoming index
1606                     if param.normsubpathindex > collectindex:
1607                         for i in range(collectindex+1, param.normsubpathindex):
1608                             result[-1].append(self.normsubpaths[i])
1609                         collectparams = [0]
1610                     else:
1611                         for i in range(collectindex-1, param.normsubpathindex, -1):
1612                             result[-1].append(self.normsubpaths[i].reversed())
1613                         collectparams = [len(self.normsubpaths[param.normsubpathindex])]
1614                 else:
1615                     result = [normpath(self.normsubpaths[:param.normsubpathindex])]
1616                     collectparams = [0]
1617                 collectindex = param.normsubpathindex
1618             collectparams.append(param.normsubpathparam)
1619         # add remaining collectparams to the result
1620         collectparams.append(len(self.normsubpaths[collectindex]))
1621         segments = self.normsubpaths[collectindex].segments(collectparams)
1622         result[-1].append(segments[0])
1623         result.extend([normpath([segment]) for segment in segments[1:]])
1624         result[-1].extend(self.normsubpaths[collectindex+1:])
1625         return result
1626
1627     def split_pt(self, params):
1628         """split path at param(s) or arc length(s) in pts and return list of normpaths"""
1629         try:
1630             for param in params:
1631                 break
1632         except:
1633             params = [params]
1634         return self._split_pt(self._convertparams(params, self.arclentoparam_pt))
1635
1636     def split(self, params):
1637         """split path at param(s) or arc length(s) and return list of normpaths"""
1638         try:
1639             for param in params:
1640                 break
1641         except:
1642             params = [params]
1643         return self._split_pt(self._convertparams(params, self.arclentoparam))
1644
1645     def _tangent(self, params, length=None):
1646         """return tangent vector of path at params
1647
1648         If length is not None, the tangent vector will be scaled to
1649         the desired length.
1650         """
1651
1652         result = [None] * len(params)
1653         tangenttemplate = path.line_pt(0, 0, 1, 0).normpath()
1654         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1655             for index, atrafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
1656                 tangentpath = tangenttemplate.transformed(atrafo)
1657                 if length is not None:
1658                     sfactor = unit.topt(length)/tangentpath.arclen_pt()
1659                     tangentpath = tangentpath.transformed(trafo.scale_pt(sfactor, sfactor, *tangentpath.atbegin_pt()))
1660                 result[index] = tangentpath
1661         return result
1662
1663     def tangent_pt(self, params, length=None):
1664         """return tangent vector of path at param(s) or arc length(s) in pts
1665
1666         If length in pts is not None, the tangent vector will be scaled to
1667         the desired length.
1668         """
1669         return self._tangent(self._convertparams(params, self.arclentoparam_pt), length)
1670     tangent_pt = _valueorlistmethod(tangent_pt)
1671
1672     def tangent(self, params, length=None):
1673         """return tangent vector of path at param(s) or arc length(s)
1674
1675         If length is not None, the tangent vector will be scaled to
1676         the desired length.
1677         """
1678         return self._tangent(self._convertparams(params, self.arclentoparam), length)
1679     tangent = _valueorlistmethod(tangent)
1680
1681     def _trafo(self, params):
1682         """return transformation at params"""
1683         result = [None] * len(params)
1684         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1685             for index, trafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
1686                 result[index] = trafo
1687         return result
1688
1689     def trafo_pt(self, params):
1690         """return transformation at param(s) or arc length(s) in pts"""
1691         return self._trafo(self._convertparams(params, self.arclentoparam_pt))
1692     trafo_pt = _valueorlistmethod(trafo_pt)
1693
1694     def trafo(self, params):
1695         """return transformation at param(s) or arc length(s)"""
1696         return self._trafo(self._convertparams(params, self.arclentoparam))
1697     trafo = _valueorlistmethod(trafo)
1698
1699     def transformed(self, trafo):
1700         """return transformed normpath"""
1701         return normpath([normsubpath.transformed(trafo) for normsubpath in self.normsubpaths])
1702
1703     def outputPS(self, file, writer, context):
1704         for normsubpath in self.normsubpaths:
1705             normsubpath.outputPS(file, writer, context)
1706
1707     def outputPDF(self, file, writer, context):
1708         for normsubpath in self.normsubpaths:
1709             normsubpath.outputPDF(file, writer, context)