normpath.py

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