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