pyx/normpath.py

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