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