normpath.py

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