pyx/normpath.py

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