pyx/normpath.py

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