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