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