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     def x_pt(self, t):
 667         return (((  self.x3_pt-3*self.x2_pt+3*self.x1_pt-self.x0_pt)*t +
 668                   3*self.x0_pt-6*self.x1_pt+3*self.x2_pt)*t +
 669                   3*self.x1_pt-3*self.x0_pt)*t + self.x0_pt
 670
 671     def xdot_pt(self, t):
 672         return ((3*self.x3_pt-9*self.x2_pt+9*self.x1_pt-3*self.x0_pt)*t +
 673                  6*self.x0_pt-12*self.x1_pt+6*self.x2_pt)*t + 3*self.x1_pt - 3*self.x0_pt
 674
 675     def xddot_pt(self, t):
 676         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
 677
 678     def xdddot_pt(self, t):
 679         return 6*self.x3_pt-18*self.x2_pt+18*self.x1_pt-6*self.x0_pt
 680
 681     def y_pt(self, t):
 682         return (((  self.y3_pt-3*self.y2_pt+3*self.y1_pt-self.y0_pt)*t +
 683                   3*self.y0_pt-6*self.y1_pt+3*self.y2_pt)*t +
 684                   3*self.y1_pt-3*self.y0_pt)*t + self.y0_pt
 685
 686     def ydot_pt(self, t):
 687         return ((3*self.y3_pt-9*self.y2_pt+9*self.y1_pt-3*self.y0_pt)*t +
 688                  6*self.y0_pt-12*self.y1_pt+6*self.y2_pt)*t + 3*self.y1_pt - 3*self.y0_pt
 689
 690     def yddot_pt(self, t):
 691         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
 692
 693     def ydddot_pt(self, t):
 694         return 6*self.y3_pt-18*self.y2_pt+18*self.y1_pt-6*self.y0_pt
 695
 696
 697 ################################################################################
 698 # normsubpath
 699 ################################################################################
 700
 701 class normsubpath:
 702
 703     """sub path of a normalized path
 704
 705     A subpath consists of a list of normsubpathitems, i.e., normlines_pt and
 706     normcurves_pt and can either be closed or not.
 707
 708     Some invariants, which have to be obeyed:
 709     - All normsubpathitems have to be longer than epsilon pts.
 710     - At the end there may be a normline (stored in self.skippedline) whose
 711       length is shorter than epsilon -- it has to be taken into account
 712       when adding further normsubpathitems
 713     - The last point of a normsubpathitem and the first point of the next
 714       element have to be equal.
 715     - When the path is closed, the last point of last normsubpathitem has
 716       to be equal to the first point of the first normsubpathitem.
 717     - epsilon might be none, disallowing any numerics, but allowing for
 718       arbitrary short paths. This is used in pdf output, where all paths need
 719       to be transformed to normpaths.
 720     """
 721
 722     __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline"
 723
 724     def __init__(self, normsubpathitems=[], closed=0, epsilon=_marker):
 725         """construct a normsubpath"""
 726         if epsilon is _marker:
 727             epsilon = _epsilon
 728         self.epsilon = epsilon
 729         # If one or more items appended to the normsubpath have been
 730         # skipped (because their total length was shorter than epsilon),
 731         # we remember this fact by a line because we have to take it
 732         # properly into account when appending further normsubpathitems
 733         self.skippedline = None
 734
 735         self.normsubpathitems = []
 736         self.closed = 0
 737
 738         # a test (might be temporary)
 739         for anormsubpathitem in normsubpathitems:
 740             assert isinstance(anormsubpathitem, normsubpathitem), "only list of normsubpathitem instances allowed"
 741
 742         self.extend(normsubpathitems)
 743
 744         if closed:
 745             self.close()
 746
 747     def __getitem__(self, i):
 748         """return normsubpathitem i"""
 749         return self.normsubpathitems[i]
 750
 751     def __len__(self):
 752         """return number of normsubpathitems"""
 753         return len(self.normsubpathitems)
 754
 755     def __str__(self):
 756         l = ", ".join(map(str, self.normsubpathitems))
 757         if self.closed:
 758             return "normsubpath([%s], closed=1)" % l
 759         else:
 760             return "normsubpath([%s])" % l
 761
 762     def _distributeparams(self, params):
 763         """return a dictionary mapping normsubpathitemindices to a tuple
 764         of a paramindices and normsubpathitemparams.
 765
 766         normsubpathitemindex specifies a normsubpathitem containing
 767         one or several positions.  paramindex specify the index of the
 768         param in the original list and normsubpathitemparam is the
 769         parameter value in the normsubpathitem.
 770         """
 771
 772         result = {}
 773         for i, param in enumerate(params):
 774             if param > 0:
 775                 index = int(param)
 776                 if index > len(self.normsubpathitems) - 1:
 777                     index = len(self.normsubpathitems) - 1
 778             else:
 779                 index = 0
 780             result.setdefault(index, ([], []))
 781             result[index][0].append(i)
 782             result[index][1].append(param - index)
 783         return result
 784
 785     def append(self, anormsubpathitem):
 786         """append normsubpathitem
 787
 788         Fails on closed normsubpath.
 789         """
 790         if self.epsilon is None:
 791             self.normsubpathitems.append(anormsubpathitem)
 792         else:
 793             # consitency tests (might be temporary)
 794             assert isinstance(anormsubpathitem, normsubpathitem), "only normsubpathitem instances allowed"
 795             if self.skippedline:
 796                 assert math.hypot(*[x-y for x, y in zip(self.skippedline.atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match"
 797             elif self.normsubpathitems:
 798                 assert math.hypot(*[x-y for x, y in zip(self.normsubpathitems[-1].atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match"
 799
 800             if self.closed:
 801                 raise NormpathException("Cannot append to closed normsubpath")
 802
 803             if self.skippedline:
 804                 xs_pt, ys_pt = self.skippedline.atbegin_pt()
 805             else:
 806                 xs_pt, ys_pt = anormsubpathitem.atbegin_pt()
 807             xe_pt, ye_pt = anormsubpathitem.atend_pt()
 808
 809             if (math.hypot(xe_pt-xs_pt, ye_pt-ys_pt) >= self.epsilon or
 810                 anormsubpathitem.arclen_pt(self.epsilon) >= self.epsilon):
 811                 if self.skippedline:
 812                     anormsubpathitem = anormsubpathitem.modifiedbegin_pt(xs_pt, ys_pt)
 813                 self.normsubpathitems.append(anormsubpathitem)
 814                 self.skippedline = None
 815             else:
 816                 self.skippedline = normline_pt(xs_pt, ys_pt, xe_pt, ye_pt)
 817
 818     def arclen_pt(self):
 819         """return arc length in pts"""
 820         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normsubpathitems])
 821
 822     def _arclentoparam_pt(self, lengths_pt):
 823         """return a tuple of params and the total length arc length in pts"""
 824         # work on a copy which is counted down to negative values
 825         lengths_pt = lengths_pt[:]
 826         results = [None] * len(lengths_pt)
 827
 828         totalarclen = 0
 829         for normsubpathindex, normsubpathitem in enumerate(self.normsubpathitems):
 830             params, arclen = normsubpathitem._arclentoparam_pt(lengths_pt, self.epsilon)
 831             for i in range(len(results)):
 832                 if results[i] is None:
 833                     lengths_pt[i] -= arclen
 834                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpathitems) - 1:
 835                         # overwrite the results until the length has become negative
 836                         results[i] = normsubpathindex + params[i]
 837             totalarclen += arclen
 838
 839         return results, totalarclen
 840
 841     def arclentoparam_pt(self, lengths_pt):
 842         """return a tuple of params"""
 843         return self._arclentoparam_pt(lengths_pt)[0]
 844
 845     def at_pt(self, params):
 846         """return coordinates at params in pts"""
 847         result = [None] * len(params)
 848         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
 849             for index, point_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].at_pt(params)):
 850                 result[index] = point_pt
 851         return result
 852
 853     def atbegin_pt(self):
 854         """return coordinates of first point in pts"""
 855         if not self.normsubpathitems and self.skippedline:
 856             return self.skippedline.atbegin_pt()
 857         return self.normsubpathitems[0].atbegin_pt()
 858
 859     def atend_pt(self):
 860         """return coordinates of last point in pts"""
 861         if self.skippedline:
 862             return self.skippedline.atend_pt()
 863         return self.normsubpathitems[-1].atend_pt()
 864
 865     def bbox(self):
 866         """return bounding box of normsubpath"""
 867         if self.normsubpathitems:
 868             abbox = self.normsubpathitems[0].bbox()
 869             for anormpathitem in self.normsubpathitems[1:]:
 870                 abbox += anormpathitem.bbox()
 871             return abbox
 872         else:
 873             return None
 874
 875     def close(self):
 876         """close subnormpath
 877
 878         Fails on closed normsubpath.
 879         """
 880         if self.closed:
 881             raise NormpathException("Cannot close already closed normsubpath")
 882         if not self.normsubpathitems:
 883             if self.skippedline is None:
 884                 raise NormpathException("Cannot close empty normsubpath")
 885             else:
 886                 raise NormpathException("Normsubpath too short, cannot be closed")
 887
 888         xs_pt, ys_pt = self.normsubpathitems[-1].atend_pt()
 889         xe_pt, ye_pt = self.normsubpathitems[0].atbegin_pt()
 890         self.append(normline_pt(xs_pt, ys_pt, xe_pt, ye_pt))
 891         self.flushskippedline()
 892         self.closed = 1
 893
 894     def copy(self):
 895         """return copy of normsubpath"""
 896         # Since normsubpathitems are never modified inplace, we just
 897         # need to copy the normsubpathitems list. We do not pass the
 898         # normsubpathitems to the constructor to not repeat the checks
 899         # for minimal length of each normsubpathitem.
 900         result = normsubpath(epsilon=self.epsilon)
 901         result.normsubpathitems = self.normsubpathitems[:]
 902         result.closed = self.closed
 903
 904         # We can share the reference to skippedline, since it is a
 905         # normsubpathitem as well and thus not modified in place either.
 906         result.skippedline = self.skippedline
 907
 908         return result
 909
 910     def curvature_pt(self, params):
 911         """return the curvature at params in 1/pts
 912
 913         The result contain the invalid instance at positions, where the
 914         curvature is undefined."""
 915         result = [None] * len(params)
 916         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
 917             for index, curvature_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].curvature_pt(params)):
 918                 result[index] = curvature_pt
 919         return result
 920
 921     def curveradius_pt(self, params):
 922         """return the curvature radius at params in pts
 923
 924         The curvature radius is the inverse of the curvature. When the
 925         curvature is 0, None is returned. Note that this radius can be negative
 926         or positive, depending on the sign of the curvature."""
 927         result = [None] * len(params)
 928         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
 929             for index, radius_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].curveradius_pt(params)):
 930                 result[index] = radius_pt
 931         return result
 932
 933     def extend(self, normsubpathitems):
 934         """extend path by normsubpathitems
 935
 936         Fails on closed normsubpath.
 937         """
 938         for normsubpathitem in normsubpathitems:
 939             self.append(normsubpathitem)
 940
 941     def flushskippedline(self):
 942         """flush the skippedline, i.e. apply it to the normsubpath
 943
 944         remove the skippedline by modifying the end point of the existing normsubpath
 945         """
 946         while self.skippedline:
 947             try:
 948                 lastnormsubpathitem = self.normsubpathitems.pop()
 949             except IndexError:
 950                 raise ValueError("normsubpath too short to flush the skippedline")
 951             lastnormsubpathitem = lastnormsubpathitem.modifiedend_pt(*self.skippedline.atend_pt())
 952             self.skippedline = None
 953             self.append(lastnormsubpathitem)
 954
 955     def intersect(self, other):
 956         """intersect self with other normsubpath
 957
 958         Returns a tuple of lists consisting of the parameter values
 959         of the intersection points of the corresponding normsubpath.
 960         """
 961         intersections_a = []
 962         intersections_b = []
 963         epsilon = min(self.epsilon, other.epsilon)
 964         # Intersect all subpaths of self with the subpaths of other, possibly including
 965         # one intersection point several times
 966         for t_a, pitem_a  in enumerate(self.normsubpathitems):
 967             for t_b, pitem_b in enumerate(other.normsubpathitems):
 968                 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon):
 969                     intersections_a.append(intersection_a + t_a)
 970                     intersections_b.append(intersection_b + t_b)
 971
 972         # although intersectipns_a are sorted for the different normsubpathitems,
 973         # within a normsubpathitem, the ordering has to be ensured separately:
 974         intersections = zip(intersections_a, intersections_b)
 975         intersections.sort()
 976         intersections_a = [a for a, b in intersections]
 977         intersections_b = [b for a, b in intersections]
 978
 979         # for symmetry reasons we enumerate intersections_a as well, although
 980         # they are already sorted (note we do not need to sort intersections_a)
 981         intersections_a = zip(intersections_a, range(len(intersections_a)))
 982         intersections_b = zip(intersections_b, range(len(intersections_b)))
 983         intersections_b.sort()
 984
 985         # now we search for intersections points which are closer together than epsilon
 986         # This task is handled by the following function
 987         def closepoints(normsubpath, intersections):
 988             split = normsubpath.segments([0] + [intersection for intersection, index in intersections] + [len(normsubpath)])
 989             result = []
 990             if normsubpath.closed:
 991                 # note that the number of segments of a closed path is off by one
 992                 # compared to an open path
 993                 i = 0
 994                 while i < len(split):
 995                     splitnormsubpath = split[i]
 996                     j = i
 997                     while not splitnormsubpath.normsubpathitems: # i.e. while "is short"
 998                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
 999                         if ip1<ip2:
1000                             result.append((ip1, ip2))
1001                         else:
1002                             result.append((ip2, ip1))
1003                         j += 1
1004                         if j == len(split):
1005                             j = 0
1006                         if j < len(split):
1007                             splitnormsubpath = splitnormsubpath.joined(split[j])
1008                         else:
1009                             break
1010                     i += 1
1011             else:
1012                 i = 1
1013                 while i < len(split)-1:
1014                     splitnormsubpath = split[i]
1015                     j = i
1016                     while not splitnormsubpath.normsubpathitems: # i.e. while "is short"
1017                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
1018                         if ip1<ip2:
1019                             result.append((ip1, ip2))
1020                         else:
1021                             result.append((ip2, ip1))
1022                         j += 1
1023                         if j < len(split)-1:
1024                             splitnormsubpath = splitnormsubpath.joined(split[j])
1025                         else:
1026                             break
1027                     i += 1
1028             return result
1029
1030         closepoints_a = closepoints(self, intersections_a)
1031         closepoints_b = closepoints(other, intersections_b)
1032
1033         # map intersection point to lowest point which is equivalent to the
1034         # point
1035         equivalentpoints = list(range(len(intersections_a)))
1036
1037         for closepoint_a in closepoints_a:
1038             for closepoint_b in closepoints_b:
1039                 if closepoint_a == closepoint_b:
1040                     for i in range(closepoint_a[1], len(equivalentpoints)):
1041                         if equivalentpoints[i] == closepoint_a[1]:
1042                             equivalentpoints[i] = closepoint_a[0]
1043
1044         # determine the remaining intersection points
1045         intersectionpoints = {}
1046         for point in equivalentpoints:
1047             intersectionpoints[point] = 1
1048
1049         # build result
1050         result = []
1051         intersectionpointskeys = intersectionpoints.keys()
1052         intersectionpointskeys.sort()
1053         for point in intersectionpointskeys:
1054             for intersection_a, index_a in intersections_a:
1055                 if index_a == point:
1056                     result_a = intersection_a
1057             for intersection_b, index_b in intersections_b:
1058                 if index_b == point:
1059                     result_b = intersection_b
1060             result.append((result_a, result_b))
1061         # note that the result is sorted in a, since we sorted
1062         # intersections_a in the very beginning
1063
1064         return [x for x, y in result], [y for x, y in result]
1065
1066     def join(self, other):
1067         """join other normsubpath inplace
1068
1069         Fails on closed normsubpath. Fails to join closed normsubpath.
1070         """
1071         if other.closed:
1072             raise NormpathException("Cannot join closed normsubpath")
1073
1074         # insert connection line
1075         x0_pt, y0_pt = self.atend_pt()
1076         x1_pt, y1_pt = other.atbegin_pt()
1077         self.append(normline_pt(x0_pt, y0_pt, x1_pt, y1_pt))
1078
1079         # append other normsubpathitems
1080         self.extend(other.normsubpathitems)
1081         if other.skippedline:
1082             self.append(other.skippedline)
1083
1084     def joined(self, other):
1085         """return joined self and other
1086
1087         Fails on closed normsubpath. Fails to join closed normsubpath.
1088         """
1089         result = self.copy()
1090         result.join(other)
1091         return result
1092
1093     def _paramtoarclen_pt(self, params):
1094         """return a tuple of arc lengths and the total arc length in pts"""
1095         result = [None] * len(params)
1096         totalarclen_pt = 0
1097         distributeparams = self._distributeparams(params)
1098         for normsubpathitemindex in range(len(self.normsubpathitems)):
1099             if distributeparams.has_key(normsubpathitemindex):
1100                 indices, params = distributeparams[normsubpathitemindex]
1101                 arclens_pt, normsubpathitemarclen_pt = self.normsubpathitems[normsubpathitemindex]._paramtoarclen_pt(params, self.epsilon)
1102                 for index, arclen_pt in zip(indices, arclens_pt):
1103                     result[index] = totalarclen_pt + arclen_pt
1104                 totalarclen_pt += normsubpathitemarclen_pt
1105             else:
1106                 totalarclen_pt += self.normsubpathitems[normsubpathitemindex].arclen_pt(self.epsilon)
1107         return result, totalarclen_pt
1108
1109     def pathitems(self):
1110         """return list of pathitems"""
1111         if not self.normsubpathitems:
1112             return []
1113
1114         # remove trailing normline_pt of closed subpaths
1115         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
1116             normsubpathitems = self.normsubpathitems[:-1]
1117         else:
1118             normsubpathitems = self.normsubpathitems
1119
1120         result = [path.moveto_pt(*self.atbegin_pt())]
1121         for normsubpathitem in normsubpathitems:
1122             result.append(normsubpathitem.pathitem())
1123         if self.closed:
1124             result.append(path.closepath())
1125         return result
1126
1127     def reversed(self):
1128         """return reversed normsubpath"""
1129         nnormpathitems = []
1130         for i in range(len(self.normsubpathitems)):
1131             nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed())
1132         return normsubpath(nnormpathitems, self.closed, self.epsilon)
1133
1134     def rotation(self, params):
1135         """return rotations at params"""
1136         result = [None] * len(params)
1137         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
1138             for index, rotation in zip(indices, self.normsubpathitems[normsubpathitemindex].rotation(params)):
1139                 result[index] = rotation
1140         return result
1141
1142     def segments(self, params):
1143         """return segments of the normsubpath
1144
1145         The returned list of normsubpaths for the segments between
1146         the params. params need to contain at least two values.
1147
1148         For a closed normsubpath the last segment result is joined to
1149         the first one when params starts with 0 and ends with len(self).
1150         or params starts with len(self) and ends with 0. Thus a segments
1151         operation on a closed normsubpath might properly join those the
1152         first and the last part to take into account the closed nature of
1153         the normsubpath. However, for intermediate parameters, closepath
1154         is not taken into account, i.e. when walking backwards you do not
1155         loop over the closepath forwardly. The special values 0 and
1156         len(self) for the first and the last parameter should be given as
1157         integers, i.e. no finite precision is used when checking for
1158         equality."""
1159
1160         if len(params) < 2:
1161             raise ValueError("at least two parameters needed in segments")
1162
1163         result = [normsubpath(epsilon=self.epsilon)]
1164
1165         # instead of distribute the parameters, we need to keep their
1166         # order and collect parameters for the needed segments of
1167         # normsubpathitem with index collectindex
1168         collectparams = []
1169         collectindex = None
1170         for param in params:
1171             # calculate index and parameter for corresponding normsubpathitem
1172             if param > 0:
1173                 index = int(param)
1174                 if index > len(self.normsubpathitems) - 1:
1175                     index = len(self.normsubpathitems) - 1
1176                 param -= index
1177             else:
1178                 index = 0
1179             if index != collectindex:
1180                 if collectindex is not None:
1181                     # append end point depening on the forthcoming index
1182                     if index > collectindex:
1183                         collectparams.append(1)
1184                     else:
1185                         collectparams.append(0)
1186                     # get segments of the normsubpathitem and add them to the result
1187                     segments = self.normsubpathitems[collectindex].segments(collectparams)
1188                     result[-1].append(segments[0])
1189                     result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]])
1190                     # add normsubpathitems and first segment parameter to close the
1191                     # gap to the forthcoming index
1192                     if index > collectindex:
1193                         for i in range(collectindex+1, index):
1194                             result[-1].append(self.normsubpathitems[i])
1195                         collectparams = [0]
1196                     else:
1197                         for i in range(collectindex-1, index, -1):
1198                             result[-1].append(self.normsubpathitems[i].reversed())
1199                         collectparams = [1]
1200                 collectindex = index
1201             collectparams.append(param)
1202         # add remaining collectparams to the result
1203         segments = self.normsubpathitems[collectindex].segments(collectparams)
1204         result[-1].append(segments[0])
1205         result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]])
1206
1207         if self.closed:
1208             # join last and first segment together if the normsubpath was
1209             # originally closed and first and the last parameters are the
1210             # beginning and end points of the normsubpath
1211             if ( ( params[0] == 0 and params[-1] == len(self.normsubpathitems) ) or
1212                  ( params[-1] == 0 and params[0] == len(self.normsubpathitems) ) ):
1213                 result[-1].normsubpathitems.extend(result[0].normsubpathitems)
1214                 result = result[-1:] + result[1:-1]
1215
1216         return result
1217
1218     def trafo(self, params):
1219         """return transformations at params"""
1220         result = [None] * len(params)
1221         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
1222             for index, trafo in zip(indices, self.normsubpathitems[normsubpathitemindex].trafo(params)):
1223                 result[index] = trafo
1224         return result
1225
1226     def transformed(self, trafo):
1227         """return transformed path"""
1228         nnormsubpath = normsubpath(epsilon=self.epsilon)
1229         for pitem in self.normsubpathitems:
1230             nnormsubpath.append(pitem.transformed(trafo))
1231         if self.closed:
1232             nnormsubpath.close()
1233         elif self.skippedline is not None:
1234             nnormsubpath.append(self.skippedline.transformed(trafo))
1235         return nnormsubpath
1236
1237     def outputPS(self, file, writer, context):
1238         # if the normsubpath is closed, we must not output a normline at
1239         # the end
1240         if not self.normsubpathitems:
1241             return
1242         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
1243             assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt"
1244             normsubpathitems = self.normsubpathitems[:-1]
1245         else:
1246             normsubpathitems = self.normsubpathitems
1247         file.write("%g %g moveto\n" % self.atbegin_pt())
1248         for anormsubpathitem in normsubpathitems:
1249             anormsubpathitem.outputPS(file, writer, context)
1250         if self.closed:
1251             file.write("closepath\n")
1252
1253     def outputPDF(self, file, writer, context):
1254         # if the normsubpath is closed, we must not output a normline at
1255         # the end
1256         if not self.normsubpathitems:
1257             return
1258         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
1259             assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt"
1260             normsubpathitems = self.normsubpathitems[:-1]
1261         else:
1262             normsubpathitems = self.normsubpathitems
1263         file.write("%f %f m\n" % self.atbegin_pt())
1264         for anormsubpathitem in normsubpathitems:
1265             anormsubpathitem.outputPDF(file, writer, context)
1266         if self.closed:
1267             file.write("h\n")
1268
1269
1270 ################################################################################
1271 # normpath
1272 ################################################################################
1273
1274 class normpathparam:
1275
1276     """parameter of a certain point along a normpath"""
1277
1278     __slots__ = "normpath", "normsubpathindex", "normsubpathparam"
1279
1280     def __init__(self, normpath, normsubpathindex, normsubpathparam):
1281         self.normpath = normpath
1282         self.normsubpathindex = normsubpathindex
1283         self.normsubpathparam = normsubpathparam
1284         float(normsubpathparam)
1285
1286     def __str__(self):
1287         return "normpathparam(%s, %s, %s)" % (self.normpath, self.normsubpathindex, self.normsubpathparam)
1288
1289     def __add__(self, other):
1290         if isinstance(other, normpathparam):
1291             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1292             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) +
1293                                                   other.normpath.paramtoarclen_pt(other))
1294         else:
1295             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) + unit.topt(other))
1296
1297     __radd__ = __add__
1298
1299     def __sub__(self, other):
1300         if isinstance(other, normpathparam):
1301             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1302             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) -
1303                                                   other.normpath.paramtoarclen_pt(other))
1304         else:
1305             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) - unit.topt(other))
1306
1307     def __rsub__(self, other):
1308         # other has to be a length in this case
1309         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self) + unit.topt(other))
1310
1311     def __mul__(self, factor):
1312         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) * factor)
1313
1314     __rmul__ = __mul__
1315
1316     def __div__(self, divisor):
1317         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) / divisor)
1318
1319     def __neg__(self):
1320         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self))
1321
1322     def __cmp__(self, other):
1323         if isinstance(other, normpathparam):
1324             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
1325             return cmp((self.normsubpathindex, self.normsubpathparam), (other.normsubpathindex, other.normsubpathparam))
1326         else:
1327             return cmp(self.normpath.paramtoarclen_pt(self), unit.topt(other))
1328
1329     def arclen_pt(self):
1330         """return arc length in pts corresponding to the normpathparam """
1331         return self.normpath.paramtoarclen_pt(self)
1332
1333     def arclen(self):
1334         """return arc length corresponding to the normpathparam """
1335         return self.normpath.paramtoarclen(self)
1336
1337
1338 def _valueorlistmethod(method):
1339     """Creates a method which takes a single argument or a list and
1340     returns a single value or a list out of method, which always
1341     works on lists."""
1342
1343     def wrappedmethod(self, valueorlist, *args, **kwargs):
1344         try:
1345             for item in valueorlist:
1346                 break
1347         except:
1348             return method(self, [valueorlist], *args, **kwargs)[0]
1349         return method(self, valueorlist, *args, **kwargs)
1350     return wrappedmethod
1351
1352
1353 class normpath(canvas.canvasitem):
1354
1355     """normalized path
1356
1357     A normalized path consists of a list of normsubpaths.
1358     """
1359
1360     def __init__(self, normsubpaths=None):
1361         """construct a normpath from a list of normsubpaths"""
1362
1363         if normsubpaths is None:
1364             self.normsubpaths = [] # make a fresh list
1365         else:
1366             self.normsubpaths = normsubpaths
1367             for subpath in normsubpaths:
1368                 assert isinstance(subpath, normsubpath), "only list of normsubpath instances allowed"
1369
1370     def __add__(self, other):
1371         """create new normpath out of self and other"""
1372         result = self.copy()
1373         result += other
1374         return result
1375
1376     def __iadd__(self, other):
1377         """add other inplace"""
1378         for normsubpath in other.normpath().normsubpaths:
1379             self.normsubpaths.append(normsubpath.copy())
1380         return self
1381
1382     def __getitem__(self, i):
1383         """return normsubpath i"""
1384         return self.normsubpaths[i]
1385
1386     def __len__(self):
1387         """return the number of normsubpaths"""
1388         return len(self.normsubpaths)
1389
1390     def __str__(self):
1391         return "normpath([%s])" % ", ".join(map(str, self.normsubpaths))
1392
1393     def _convertparams(self, params, convertmethod):
1394         """return params with all non-normpathparam arguments converted by convertmethod
1395
1396         usecases:
1397         - self._convertparams(params, self.arclentoparam_pt)
1398         - self._convertparams(params, self.arclentoparam)
1399         """
1400
1401         converttoparams = []
1402         convertparamindices = []
1403         for i, param in enumerate(params):
1404             if not isinstance(param, normpathparam):
1405                 converttoparams.append(param)
1406                 convertparamindices.append(i)
1407         if converttoparams:
1408             params = params[:]
1409             for i, param in zip(convertparamindices, convertmethod(converttoparams)):
1410                 params[i] = param
1411         return params
1412
1413     def _distributeparams(self, params):
1414         """return a dictionary mapping subpathindices to a tuple of a paramindices and subpathparams
1415
1416         subpathindex specifies a subpath containing one or several positions.
1417         paramindex specify the index of the normpathparam in the original list and
1418         subpathparam is the parameter value in the subpath.
1419         """
1420
1421         result = {}
1422         for i, param in enumerate(params):
1423             assert param.normpath is self, "normpathparam has to belong to this path"
1424             result.setdefault(param.normsubpathindex, ([], []))
1425             result[param.normsubpathindex][0].append(i)
1426             result[param.normsubpathindex][1].append(param.normsubpathparam)
1427         return result
1428
1429     def append(self, item):
1430         """append a normsubpath by a normsubpath or a pathitem"""
1431         if isinstance(item, normsubpath):
1432             # the normsubpaths list can be appended by a normsubpath only
1433             self.normsubpaths.append(item)
1434         elif isinstance(item, path.pathitem):
1435             # ... but we are kind and allow for regular path items as well
1436             # in order to make a normpath to behave more like a regular path
1437             context = path.context(*(self.normsubpaths[-1].atend_pt() +
1438                                      self.normsubpaths[-1].atbegin_pt()))
1439             item.updatenormpath(self, context)
1440
1441     def arclen_pt(self):
1442         """return arc length in pts"""
1443         return sum([normsubpath.arclen_pt() for normsubpath in self.normsubpaths])
1444
1445     def arclen(self):
1446         """return arc length"""
1447         return self.arclen_pt() * unit.t_pt
1448
1449     def _arclentoparam_pt(self, lengths_pt):
1450         """return the params matching the given lengths_pt"""
1451         # work on a copy which is counted down to negative values
1452         lengths_pt = lengths_pt[:]
1453         results = [None] * len(lengths_pt)
1454
1455         for normsubpathindex, normsubpath in enumerate(self.normsubpaths):
1456             params, arclen = normsubpath._arclentoparam_pt(lengths_pt)
1457             done = 1
1458             for i, result in enumerate(results):
1459                 if results[i] is None:
1460                     lengths_pt[i] -= arclen
1461                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpaths) - 1:
1462                         # overwrite the results until the length has become negative
1463                         results[i] = normpathparam(self, normsubpathindex, params[i])
1464                     done = 0
1465             if done:
1466                 break
1467
1468         return results
1469
1470     def arclentoparam_pt(self, lengths_pt):
1471         """return the param(s) matching the given length(s)_pt in pts"""
1472         pass
1473     arclentoparam_pt = _valueorlistmethod(_arclentoparam_pt)
1474
1475     def arclentoparam(self, lengths):
1476         """return the param(s) matching the given length(s)"""
1477         return self._arclentoparam_pt([unit.topt(l) for l in lengths])
1478     arclentoparam = _valueorlistmethod(arclentoparam)
1479
1480     def _at_pt(self, params):
1481         """return coordinates of normpath in pts at params"""
1482         result = [None] * len(params)
1483         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1484             for index, point_pt in zip(indices, self.normsubpaths[normsubpathindex].at_pt(params)):
1485                 result[index] = point_pt
1486         return result
1487
1488     def at_pt(self, params):
1489         """return coordinates of normpath in pts at param(s) or lengths in pts"""
1490         return self._at_pt(self._convertparams(params, self.arclentoparam_pt))
1491     at_pt = _valueorlistmethod(at_pt)
1492
1493     def at(self, params):
1494         """return coordinates of normpath at param(s) or arc lengths"""
1495         return [(x_pt * unit.t_pt, y_pt * unit.t_pt)
1496                 for x_pt, y_pt in self._at_pt(self._convertparams(params, self.arclentoparam))]
1497     at = _valueorlistmethod(at)
1498
1499     def atbegin_pt(self):
1500         """return coordinates of the beginning of first subpath in normpath in pts"""
1501         if self.normsubpaths:
1502             return self.normsubpaths[0].atbegin_pt()
1503         else:
1504             raise NormpathException("cannot return first point of empty path")
1505
1506     def atbegin(self):
1507         """return coordinates of the beginning of first subpath in normpath"""
1508         x, y = self.atbegin_pt()
1509         return x * unit.t_pt, y * unit.t_pt
1510
1511     def atend_pt(self):
1512         """return coordinates of the end of last subpath in normpath in pts"""
1513         if self.normsubpaths:
1514             return self.normsubpaths[-1].atend_pt()
1515         else:
1516             raise NormpathException("cannot return last point of empty path")
1517
1518     def atend(self):
1519         """return coordinates of the end of last subpath in normpath"""
1520         x, y = self.atend_pt()
1521         return x * unit.t_pt, y * unit.t_pt
1522
1523     def bbox(self):
1524         """return bbox of normpath"""
1525         abbox = None
1526         for normsubpath in self.normsubpaths:
1527             nbbox =  normsubpath.bbox()
1528             if abbox is None:
1529                 abbox = nbbox
1530             elif nbbox:
1531                 abbox += nbbox
1532         return abbox
1533
1534     def begin(self):
1535         """return param corresponding of the beginning of the normpath"""
1536         if self.normsubpaths:
1537             return normpathparam(self, 0, 0)
1538         else:
1539             raise NormpathException("empty path")
1540
1541     def copy(self):
1542         """return copy of normpath"""
1543         result = normpath()
1544         for normsubpath in self.normsubpaths:
1545             result.append(normsubpath.copy())
1546         return result
1547
1548     def _curvature_pt(self, params):
1549         """return the curvature in 1/pts at params in pts
1550
1551         The curvature radius is the inverse of the curvature. When the
1552         curvature is 0, None is returned. Note that this radius can be negative
1553         or positive, depending on the sign of the curvature."""
1554
1555         result = [None] * len(params)
1556         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1557             for index, curvature_pt in zip(indices, self.normsubpaths[normsubpathindex].curvature_pt(params)):
1558                 result[index] = curvature_pt
1559         return result
1560
1561     def curvature_pt(self, params):
1562         """return the curvature in 1/pt at param(s) or arc length(s) in pts
1563
1564         The curvature radius is the inverse of the curvature. When the
1565         curvature is 0, None is returned. Note that this radius can be negative
1566         or positive, depending on the sign of the curvature."""
1567
1568         return self._curveradius_pt(self._convertparams(params, self.arclentoparam_pt))
1569     curvature_pt = _valueorlistmethod(curvature_pt)
1570
1571     def _curveradius_pt(self, params):
1572         """return the curvature radius at params in pts
1573
1574         The curvature radius is the inverse of the curvature. When the
1575         curvature is 0, None is returned. Note that this radius can be negative
1576         or positive, depending on the sign of the curvature."""
1577
1578         result = [None] * len(params)
1579         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1580             for index, radius_pt in zip(indices, self.normsubpaths[normsubpathindex].curveradius_pt(params)):
1581                 result[index] = radius_pt
1582         return result
1583
1584     def curveradius_pt(self, params):
1585         """return the curvature radius in pts at param(s) or arc length(s) in pts
1586
1587         The curvature radius is the inverse of the curvature. When the
1588         curvature is 0, None is returned. Note that this radius can be negative
1589         or positive, depending on the sign of the curvature."""
1590
1591         return self._curveradius_pt(self._convertparams(params, self.arclentoparam_pt))
1592     curveradius_pt = _valueorlistmethod(curveradius_pt)
1593
1594     def curveradius(self, params):
1595         """return the curvature radius at param(s) or arc length(s)
1596
1597         The curvature radius is the inverse of the curvature. When the
1598         curvature is 0, None is returned. Note that this radius can be negative
1599         or positive, depending on the sign of the curvature."""
1600
1601         result = []
1602         for radius_pt in self._curveradius_pt(self._convertparams(params, self.arclentoparam)):
1603             if radius_pt is not None:
1604                 result.append(radius_pt * unit.t_pt)
1605             else:
1606                 result.append(None)
1607         return result
1608     curveradius = _valueorlistmethod(curveradius)
1609
1610     def end(self):
1611         """return param corresponding of the end of the path"""
1612         if self.normsubpaths:
1613             return normpathparam(self, len(self)-1, len(self.normsubpaths[-1]))
1614         else:
1615             raise NormpathException("empty path")
1616
1617     def extend(self, normsubpaths):
1618         """extend path by normsubpaths or pathitems"""
1619         for anormsubpath in normsubpaths:
1620             # use append to properly handle regular path items as well as normsubpaths
1621             self.append(anormsubpath)
1622
1623     def intersect(self, other):
1624         """intersect self with other path
1625
1626         Returns a tuple of lists consisting of the parameter values
1627         of the intersection points of the corresponding normpath.
1628         """
1629         other = other.normpath()
1630
1631         # here we build up the result
1632         intersections = ([], [])
1633
1634         # Intersect all normsubpaths of self with the normsubpaths of
1635         # other.
1636         for ia, normsubpath_a in enumerate(self.normsubpaths):
1637             for ib, normsubpath_b in enumerate(other.normsubpaths):
1638                 for intersection in zip(*normsubpath_a.intersect(normsubpath_b)):
1639                     intersections[0].append(normpathparam(self, ia, intersection[0]))
1640                     intersections[1].append(normpathparam(other, ib, intersection[1]))
1641         return intersections
1642
1643     def join(self, other):
1644         """join other normsubpath inplace
1645
1646         Both normpaths must contain at least one normsubpath.
1647         The last normsubpath of self will be joined to the first
1648         normsubpath of other.
1649         """
1650         if not self.normsubpaths:
1651             raise NormpathException("cannot join to empty path")
1652         if not other.normsubpaths:
1653             raise PathException("cannot join empty path")
1654         self.normsubpaths[-1].join(other.normsubpaths[0])
1655         self.normsubpaths.extend(other.normsubpaths[1:])
1656
1657     def joined(self, other):
1658         """return joined self and other
1659
1660         Both normpaths must contain at least one normsubpath.
1661         The last normsubpath of self will be joined to the first
1662         normsubpath of other.
1663         """
1664         result = self.copy()
1665         result.join(other.normpath())
1666         return result
1667
1668     # << operator also designates joining
1669     __lshift__ = joined
1670
1671     def normpath(self):
1672         """return a normpath, i.e. self"""
1673         return self
1674
1675     def _paramtoarclen_pt(self, params):
1676         """return arc lengths in pts matching the given params"""
1677         result = [None] * len(params)
1678         totalarclen_pt = 0
1679         distributeparams = self._distributeparams(params)
1680         for normsubpathindex in range(max(distributeparams.keys()) + 1):
1681             if distributeparams.has_key(normsubpathindex):
1682                 indices, params = distributeparams[normsubpathindex]
1683                 arclens_pt, normsubpatharclen_pt = self.normsubpaths[normsubpathindex]._paramtoarclen_pt(params)
1684                 for index, arclen_pt in zip(indices, arclens_pt):
1685                     result[index] = totalarclen_pt + arclen_pt
1686                 totalarclen_pt += normsubpatharclen_pt
1687             else:
1688                 totalarclen_pt += self.normsubpaths[normsubpathindex].arclen_pt()
1689         return result
1690
1691     def paramtoarclen_pt(self, params):
1692         """return arc length(s) in pts matching the given param(s)"""
1693     paramtoarclen_pt = _valueorlistmethod(_paramtoarclen_pt)
1694
1695     def paramtoarclen(self, params):
1696         """return arc length(s) matching the given param(s)"""
1697         return [arclen_pt * unit.t_pt for arclen_pt in self._paramtoarclen_pt(params)]
1698     paramtoarclen = _valueorlistmethod(paramtoarclen)
1699
1700     def path(self):
1701         """return path corresponding to normpath"""
1702         pathitems = []
1703         for normsubpath in self.normsubpaths:
1704             pathitems.extend(normsubpath.pathitems())
1705         return path.path(*pathitems)
1706
1707     def reversed(self):
1708         """return reversed path"""
1709         nnormpath = normpath()
1710         for i in range(len(self.normsubpaths)):
1711             nnormpath.normsubpaths.append(self.normsubpaths[-(i+1)].reversed())
1712         return nnormpath
1713
1714     def _rotation(self, params):
1715         """return rotation at params"""
1716         result = [None] * len(params)
1717         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1718             for index, rotation in zip(indices, self.normsubpaths[normsubpathindex].rotation(params)):
1719                 result[index] = rotation
1720         return result
1721
1722     def rotation_pt(self, params):
1723         """return rotation at param(s) or arc length(s) in pts"""
1724         return self._rotation(self._convertparams(params, self.arclentoparam_pt))
1725     rotation_pt = _valueorlistmethod(rotation_pt)
1726
1727     def rotation(self, params):
1728         """return rotation at param(s) or arc length(s)"""
1729         return self._rotation(self._convertparams(params, self.arclentoparam))
1730     rotation = _valueorlistmethod(rotation)
1731
1732     def _split_pt(self, params):
1733         """split path at params and return list of normpaths"""
1734
1735         # instead of distributing the parameters, we need to keep their
1736         # order and collect parameters for splitting of normsubpathitem
1737         # with index collectindex
1738         collectindex = None
1739         for param in params:
1740             if param.normsubpathindex != collectindex:
1741                 if collectindex is not None:
1742                     # append end point depening on the forthcoming index
1743                     if param.normsubpathindex > collectindex:
1744                         collectparams.append(len(self.normsubpaths[collectindex]))
1745                     else:
1746                         collectparams.append(0)
1747                     # get segments of the normsubpath and add them to the result
1748                     segments = self.normsubpaths[collectindex].segments(collectparams)
1749                     result[-1].append(segments[0])
1750                     result.extend([normpath([segment]) for segment in segments[1:]])
1751                     # add normsubpathitems and first segment parameter to close the
1752                     # gap to the forthcoming index
1753                     if param.normsubpathindex > collectindex:
1754                         for i in range(collectindex+1, param.normsubpathindex):
1755                             result[-1].append(self.normsubpaths[i])
1756                         collectparams = [0]
1757                     else:
1758                         for i in range(collectindex-1, param.normsubpathindex, -1):
1759                             result[-1].append(self.normsubpaths[i].reversed())
1760                         collectparams = [len(self.normsubpaths[param.normsubpathindex])]
1761                 else:
1762                     result = [normpath(self.normsubpaths[:param.normsubpathindex])]
1763                     collectparams = [0]
1764                 collectindex = param.normsubpathindex
1765             collectparams.append(param.normsubpathparam)
1766         # add remaining collectparams to the result
1767         collectparams.append(len(self.normsubpaths[collectindex]))
1768         segments = self.normsubpaths[collectindex].segments(collectparams)
1769         result[-1].append(segments[0])
1770         result.extend([normpath([segment]) for segment in segments[1:]])
1771         result[-1].extend(self.normsubpaths[collectindex+1:])
1772         return result
1773
1774     def split_pt(self, params):
1775         """split path at param(s) or arc length(s) in pts and return list of normpaths"""
1776         try:
1777             for param in params:
1778                 break
1779         except:
1780             params = [params]
1781         return self._split_pt(self._convertparams(params, self.arclentoparam_pt))
1782
1783     def split(self, params):
1784         """split path at param(s) or arc length(s) and return list of normpaths"""
1785         try:
1786             for param in params:
1787                 break
1788         except:
1789             params = [params]
1790         return self._split_pt(self._convertparams(params, self.arclentoparam))
1791
1792     def _tangent(self, params, length_pt):
1793         """return tangent vector of path at params
1794
1795         If length_pt in pts is not None, the tangent vector will be scaled to
1796         the desired length.
1797         """
1798
1799         result = [None] * len(params)
1800         tangenttemplate = path.line_pt(0, 0, length_pt, 0).normpath()
1801         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1802             for index, atrafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
1803                 if atrafo is invalid:
1804                     result[index] = invalid
1805                 else:
1806                     result[index] = tangenttemplate.transformed(atrafo)
1807         return result
1808
1809     def tangent_pt(self, params, length_pt):
1810         """return tangent vector of path at param(s) or arc length(s) in pts
1811
1812         If length in pts is not None, the tangent vector will be scaled to
1813         the desired length.
1814         """
1815         return self._tangent(self._convertparams(params, self.arclentoparam_pt), length_pt)
1816     tangent_pt = _valueorlistmethod(tangent_pt)
1817
1818     def tangent(self, params, length):
1819         """return tangent vector of path at param(s) or arc length(s)
1820
1821         If length is not None, the tangent vector will be scaled to
1822         the desired length.
1823         """
1824         return self._tangent(self._convertparams(params, self.arclentoparam), unit.topt(length))
1825     tangent = _valueorlistmethod(tangent)
1826
1827     def _trafo(self, params):
1828         """return transformation at params"""
1829         result = [None] * len(params)
1830         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
1831             for index, trafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
1832                 result[index] = trafo
1833         return result
1834
1835     def trafo_pt(self, params):
1836         """return transformation at param(s) or arc length(s) in pts"""
1837         return self._trafo(self._convertparams(params, self.arclentoparam_pt))
1838     trafo_pt = _valueorlistmethod(trafo_pt)
1839
1840     def trafo(self, params):
1841         """return transformation at param(s) or arc length(s)"""
1842         return self._trafo(self._convertparams(params, self.arclentoparam))
1843     trafo = _valueorlistmethod(trafo)
1844
1845     def transformed(self, trafo):
1846         """return transformed normpath"""
1847         return normpath([normsubpath.transformed(trafo) for normsubpath in self.normsubpaths])
1848
1849     def outputPS(self, file, writer, context):
1850         for normsubpath in self.normsubpaths:
1851             normsubpath.outputPS(file, writer, context)
1852
1853     def outputPDF(self, file, writer, context):
1854         for normsubpath in self.normsubpaths:
1855             normsubpath.outputPDF(file, writer, context)