pyx/normpath.py

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