pyx/normpath.py

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