pyx/normpath.py

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