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