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