pyx/path.py

   1 #!/usr/bin/env python
   2 # -*- coding: ISO-8859-1 -*-
   3 #
   4 #
   5 # Copyright (C) 2002-2004 Jörg Lehmann <joergl@users.sourceforge.net>
   6 # Copyright (C) 2003-2004 Michael Schindler <m-schindler@users.sourceforge.net>
   7 # Copyright (C) 2002-2004 André Wobst <wobsta@users.sourceforge.net>
   8 #
   9 # This file is part of PyX (http://pyx.sourceforge.net/).
  10 #
  11 # PyX is free software; you can redistribute it and/or modify
  12 # it under the terms of the GNU General Public License as published by
  13 # the Free Software Foundation; either version 2 of the License, or
  14 # (at your option) any later version.
  15 #
  16 # PyX is distributed in the hope that it will be useful,
  17 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 # GNU General Public License for more details.
  20 #
  21 # You should have received a copy of the GNU General Public License
  22 # along with PyX; if not, write to the Free Software
  23 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24
  25 # TODO: - glue -> glue & glued
  26 #       - nocurrentpoint exception?
  27 #       - correct bbox for curveto and bpathel
  28 #         (maybe we still need the current bbox implementation (then maybe called
  29 #          cbox = control box) for bpathel for the use during the
  30 #          intersection of bpaths)
  31 #       - correct behaviour of closepath() in reversed()
  32
  33 import copy, math, string, bisect
  34 from math import cos, sin, pi
  35 try:
  36     from math import radians, degrees
  37 except ImportError:
  38     # fallback implementation for Python 2.1 and below
  39     def radians(x): return x*pi/180
  40     def degrees(x): return x*180/pi
  41 import base, bbox, trafo, unit, helper
  42
  43 ################################################################################
  44 # helper classes and routines for Bezier curves
  45 ################################################################################
  46
  47 #
  48 # bcurve_pt: Bezier curve segment with four control points (coordinates in pts)
  49 #
  50
  51 class bcurve_pt:
  52
  53     """element of Bezier path (coordinates in pts)"""
  54
  55     def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
  56         self.x0 = x0
  57         self.y0 = y0
  58         self.x1 = x1
  59         self.y1 = y1
  60         self.x2 = x2
  61         self.y2 = y2
  62         self.x3 = x3
  63         self.y3 = y3
  64
  65     def __str__(self):
  66         return "%g %g moveto %g %g %g %g %g %g curveto" % \
  67                ( self.x0, self.y0,
  68                  self.x1, self.y1,
  69                  self.x2, self.y2,
  70                  self.x3, self.y3 )
  71
  72     def __getitem__(self, t):
  73         """return pathel at parameter value t (0<=t<=1)"""
  74         assert 0 <= t <= 1, "parameter t of pathel out of range [0,1]"
  75         return ( unit.t_pt((  -self.x0+3*self.x1-3*self.x2+self.x3)*t*t*t +
  76                            ( 3*self.x0-6*self.x1+3*self.x2        )*t*t +
  77                            (-3*self.x0+3*self.x1                  )*t +
  78                                self.x0) ,
  79                  unit.t_pt((  -self.y0+3*self.y1-3*self.y2+self.y3)*t*t*t +
  80                            ( 3*self.y0-6*self.y1+3*self.y2        )*t*t +
  81                            (-3*self.y0+3*self.y1                  )*t +
  82                                self.y0)
  83                )
  84
  85     pos = __getitem__
  86
  87     def bbox(self):
  88         return bbox._bbox(min(self.x0, self.x1, self.x2, self.x3),
  89                           min(self.y0, self.y1, self.y2, self.y3),
  90                           max(self.x0, self.x1, self.x2, self.x3),
  91                           max(self.y0, self.y1, self.y2, self.y3))
  92
  93     def isStraight(self, epsilon=1e-5):
  94         """check wheter the bcurve_pt is approximately straight"""
  95
  96         # just check, whether the modulus of the difference between
  97         # the length of the control polygon
  98         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
  99         # straight line between starting and ending point of the
 100         # bcurve_pt (i.e. |P3-P1|) is smaller the epsilon
 101         return abs(math.sqrt((self.x1-self.x0)*(self.x1-self.x0)+
 102                              (self.y1-self.y0)*(self.y1-self.y0)) +
 103                    math.sqrt((self.x2-self.x1)*(self.x2-self.x1)+
 104                              (self.y2-self.y1)*(self.y2-self.y1)) +
 105                    math.sqrt((self.x3-self.x2)*(self.x3-self.x2)+
 106                              (self.y3-self.y2)*(self.y3-self.y2)) -
 107                    math.sqrt((self.x3-self.x0)*(self.x3-self.x0)+
 108                              (self.y3-self.y0)*(self.y3-self.y0)))<epsilon
 109
 110     def split(self, parameters):
 111         """return list of bcurve_pt corresponding to split at parameters"""
 112
 113         # first, we calculate the coefficients corresponding to our
 114         # original bezier curve. These represent a useful starting
 115         # point for the following change of the polynomial parameter
 116         a0x = self.x0
 117         a0y = self.y0
 118         a1x = 3*(-self.x0+self.x1)
 119         a1y = 3*(-self.y0+self.y1)
 120         a2x = 3*(self.x0-2*self.x1+self.x2)
 121         a2y = 3*(self.y0-2*self.y1+self.y2)
 122         a3x = -self.x0+3*(self.x1-self.x2)+self.x3
 123         a3y = -self.y0+3*(self.y1-self.y2)+self.y3
 124
 125         if parameters[0]!=0:
 126             parameters = [0] + parameters
 127         if parameters[-1]!=1:
 128             parameters = parameters + [1]
 129
 130         result = []
 131
 132         for i in range(len(parameters)-1):
 133             t1 = parameters[i]
 134             dt = parameters[i+1]-t1
 135
 136             # [t1,t2] part
 137             #
 138             # the new coefficients of the [t1,t1+dt] part of the bezier curve
 139             # are then given by expanding
 140             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
 141             #  a3*(t1+dt*u)**3 in u, yielding
 142             #
 143             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
 144             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
 145             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
 146             #   a3*dt**3                         * u**3
 147             #
 148             # from this values we obtain the new control points by inversion
 149             #
 150             # XXX: we could do this more efficiently by reusing for
 151             # (x0, y0) the control point (x3, y3) from the previous
 152             # Bezier curve
 153
 154             x0 = a0x + a1x*t1 + a2x*t1*t1 + a3x*t1*t1*t1
 155             y0 = a0y + a1y*t1 + a2y*t1*t1 + a3y*t1*t1*t1
 156             x1 = (a1x+2*a2x*t1+3*a3x*t1*t1)*dt/3.0 + x0
 157             y1 = (a1y+2*a2y*t1+3*a3y*t1*t1)*dt/3.0 + y0
 158             x2 = (a2x+3*a3x*t1)*dt*dt/3.0 - x0 + 2*x1
 159             y2 = (a2y+3*a3y*t1)*dt*dt/3.0 - y0 + 2*y1
 160             x3 = a3x*dt*dt*dt + x0 - 3*x1 + 3*x2
 161             y3 = a3y*dt*dt*dt + y0 - 3*y1 + 3*y2
 162
 163             result.append(bcurve_pt(x0, y0, x1, y1, x2, y2, x3, y3))
 164
 165         return result
 166
 167     def MidPointSplit(self):
 168         """splits bpathel at midpoint returning bpath with two bpathels"""
 169
 170         # for efficiency reason, we do not use self.split(0.5)!
 171
 172         # first, we have to calculate the  midpoints between adjacent
 173         # control points
 174         x01 = 0.5*(self.x0+self.x1)
 175         y01 = 0.5*(self.y0+self.y1)
 176         x12 = 0.5*(self.x1+self.x2)
 177         y12 = 0.5*(self.y1+self.y2)
 178         x23 = 0.5*(self.x2+self.x3)
 179         y23 = 0.5*(self.y2+self.y3)
 180
 181         # In the next iterative step, we need the midpoints between 01 and 12
 182         # and between 12 and 23
 183         x01_12 = 0.5*(x01+x12)
 184         y01_12 = 0.5*(y01+y12)
 185         x12_23 = 0.5*(x12+x23)
 186         y12_23 = 0.5*(y12+y23)
 187
 188         # Finally the midpoint is given by
 189         xmidpoint = 0.5*(x01_12+x12_23)
 190         ymidpoint = 0.5*(y01_12+y12_23)
 191
 192         return (bcurve_pt(self.x0, self.y0,
 193                         x01, y01,
 194                         x01_12, y01_12,
 195                         xmidpoint, ymidpoint),
 196                 bcurve_pt(xmidpoint, ymidpoint,
 197                         x12_23, y12_23,
 198                         x23, y23,
 199                         self.x3, self.y3))
 200
 201     def arclength_pt(self, epsilon=1e-5):
 202         """computes arclength of bpathel in pts using successive midpoint split"""
 203         if self.isStraight(epsilon):
 204             return math.sqrt((self.x3-self.x0)*(self.x3-self.x0)+
 205                              (self.y3-self.y0)*(self.y3-self.y0))
 206         else:
 207             (a, b) = self.MidPointSplit()
 208             return a.arclength_pt(epsilon) + b.arclength_pt(epsilon)
 209
 210     def arclength(self, epsilon=1e-5):
 211         """computes arclength of bpathel using successive midpoint split"""
 212         return unit.t_pt(self.arclength_pt(epsilon))
 213
 214     def seglengths(self, paraminterval, epsilon=1e-5):
 215         """returns the list of segment line lengths (in pts) of the bpathel
 216            together with the length of the parameterinterval"""
 217
 218         # lower and upper bounds for the arclength
 219         lowerlen = \
 220             math.sqrt((self.x3-self.x0)*(self.x3-self.x0) + (self.y3-self.y0)*(self.y3-self.y0))
 221         upperlen = \
 222             math.sqrt((self.x1-self.x0)*(self.x1-self.x0) + (self.y1-self.y0)*(self.y1-self.y0)) + \
 223             math.sqrt((self.x2-self.x1)*(self.x2-self.x1) + (self.y2-self.y1)*(self.y2-self.y1)) + \
 224             math.sqrt((self.x3-self.x2)*(self.x3-self.x2) + (self.y3-self.y2)*(self.y3-self.y2))
 225
 226         # instead of isStraight method:
 227         if abs(upperlen-lowerlen)<epsilon:
 228             return [( 0.5*(upperlen+lowerlen), paraminterval )]
 229         else:
 230             (a, b) = self.MidPointSplit()
 231             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
 232
 233     def _lentopar(self, lengths, epsilon=1e-5):
 234         """computes the parameters [t] of bpathel where the given lengths (in pts) are assumed
 235         returns ( [parameter], total arclength)"""
 236
 237         # create the list of accumulated lengths
 238         # and the length of the parameters
 239         cumlengths = self.seglengths(1, epsilon)
 240         l = len(cumlengths)
 241         parlengths = [cumlengths[i][1] for i in range(l)]
 242         cumlengths[0] = cumlengths[0][0]
 243         for i in range(1,l):
 244             cumlengths[i] = cumlengths[i][0] + cumlengths[i-1]
 245
 246         # create the list of parameters to be returned
 247         tt = []
 248         for length in lengths:
 249             # find the last index that is smaller than length
 250             try:
 251                 lindex = bisect.bisect_left(cumlengths, length)
 252             except: # workaround for python 2.0
 253                 lindex = bisect.bisect(cumlengths, length)
 254                 while lindex and (lindex >= len(cumlengths) or
 255                                   cumlengths[lindex] >= length):
 256                     lindex -= 1
 257             if lindex==0:
 258                 t = length * 1.0 / cumlengths[0]
 259                 t *= parlengths[0]
 260             elif lindex>=l-2:
 261                 t = 1
 262             else:
 263                 t = (length - cumlengths[lindex]) * 1.0 / (cumlengths[lindex+1] - cumlengths[lindex])
 264                 t *= parlengths[lindex+1]
 265                 for i in range(lindex+1):
 266                     t += parlengths[i]
 267             t = max(min(t,1),0)
 268             tt.append(t)
 269         return [tt, cumlengths[-1]]
 270
 271 #
 272 # bline_pt: Bezier curve segment corresponding to straight line (coordinates in pts)
 273 #
 274
 275 class bline_pt(bcurve_pt):
 276
 277     """bcurve_pt corresponding to straight line (coordiates in pts)"""
 278
 279     def __init__(self, x0, y0, x1, y1):
 280         xa = x0+(x1-x0)/3.0
 281         ya = y0+(y1-y0)/3.0
 282         xb = x0+2.0*(x1-x0)/3.0
 283         yb = y0+2.0*(y1-y0)/3.0
 284
 285         bcurve_pt.__init__(self, x0, y0, xa, ya, xb, yb, x1, y1)
 286
 287 ################################################################################
 288 # Bezier helper functions
 289 ################################################################################
 290
 291 def _arctobcurve(x, y, r, phi1, phi2):
 292     """generate the best bpathel corresponding to an arc segment"""
 293
 294     dphi=phi2-phi1
 295
 296     if dphi==0: return None
 297
 298     # the two endpoints should be clear
 299     (x0, y0) = ( x+r*cos(phi1), y+r*sin(phi1) )
 300     (x3, y3) = ( x+r*cos(phi2), y+r*sin(phi2) )
 301
 302     # optimal relative distance along tangent for second and third
 303     # control point
 304     l = r*4*(1-cos(dphi/2))/(3*sin(dphi/2))
 305
 306     (x1, y1) = ( x0-l*sin(phi1), y0+l*cos(phi1) )
 307     (x2, y2) = ( x3+l*sin(phi2), y3-l*cos(phi2) )
 308
 309     return bcurve_pt(x0, y0, x1, y1, x2, y2, x3, y3)
 310
 311
 312 def _arctobezierpath(x, y, r, phi1, phi2, dphimax=45):
 313     apath = []
 314
 315     phi1 = radians(phi1)
 316     phi2 = radians(phi2)
 317     dphimax = radians(dphimax)
 318
 319     if phi2<phi1:
 320         # guarantee that phi2>phi1 ...
 321         phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
 322     elif phi2>phi1+2*pi:
 323         # ... or remove unnecessary multiples of 2*pi
 324         phi2 = phi2 - (math.floor((phi2-phi1)/(2*pi))-1)*2*pi
 325
 326     if r==0 or phi1-phi2==0: return []
 327
 328     subdivisions = abs(int((1.0*(phi1-phi2))/dphimax))+1
 329
 330     dphi=(1.0*(phi2-phi1))/subdivisions
 331
 332     for i in range(subdivisions):
 333         apath.append(_arctobcurve(x, y, r, phi1+i*dphi, phi1+(i+1)*dphi))
 334
 335     return apath
 336
 337
 338 def _bcurveIntersect(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
 339     """intersect two bpathels
 340
 341     a and b are bpathels with parameter ranges [a_t0, a_t1],
 342     respectively [b_t0, b_t1].
 343     epsilon determines when the bpathels are assumed to be straight
 344
 345     """
 346
 347     # intersection of bboxes is a necessary criterium for intersection
 348     if not a.bbox().intersects(b.bbox()): return ()
 349
 350     if not a.isStraight(epsilon):
 351         (aa, ab) = a.MidPointSplit()
 352         a_tm = 0.5*(a_t0+a_t1)
 353
 354         if not b.isStraight(epsilon):
 355             (ba, bb) = b.MidPointSplit()
 356             b_tm = 0.5*(b_t0+b_t1)
 357
 358             return ( _bcurveIntersect(aa, a_t0, a_tm,
 359                                        ba, b_t0, b_tm, epsilon) +
 360                      _bcurveIntersect(ab, a_tm, a_t1,
 361                                        ba, b_t0, b_tm, epsilon) +
 362                      _bcurveIntersect(aa, a_t0, a_tm,
 363                                        bb, b_tm, b_t1, epsilon) +
 364                      _bcurveIntersect(ab, a_tm, a_t1,
 365                                        bb, b_tm, b_t1, epsilon) )
 366         else:
 367             return ( _bcurveIntersect(aa, a_t0, a_tm,
 368                                        b, b_t0, b_t1, epsilon) +
 369                      _bcurveIntersect(ab, a_tm, a_t1,
 370                                        b, b_t0, b_t1, epsilon) )
 371     else:
 372         if not b.isStraight(epsilon):
 373             (ba, bb) = b.MidPointSplit()
 374             b_tm = 0.5*(b_t0+b_t1)
 375
 376             return  ( _bcurveIntersect(a, a_t0, a_t1,
 377                                        ba, b_t0, b_tm, epsilon) +
 378                       _bcurveIntersect(a, a_t0, a_t1,
 379                                        bb, b_tm, b_t1, epsilon) )
 380         else:
 381             # no more subdivisions of either a or b
 382             # => try to intersect a and b as straight line segments
 383
 384             a_deltax = a.x3 - a.x0
 385             a_deltay = a.y3 - a.y0
 386             b_deltax = b.x3 - b.x0
 387             b_deltay = b.y3 - b.y0
 388
 389             det = b_deltax*a_deltay - b_deltay*a_deltax
 390
 391             ba_deltax0 = b.x0 - a.x0
 392             ba_deltay0 = b.y0 - a.y0
 393
 394             try:
 395                 a_t = ( b_deltax*ba_deltay0 - b_deltay*ba_deltax0)/det
 396                 b_t = ( a_deltax*ba_deltay0 - a_deltay*ba_deltax0)/det
 397             except ArithmeticError:
 398                 return ()
 399
 400             # check for intersections out of bound
 401             if not (0<=a_t<=1 and 0<=b_t<=1): return ()
 402
 403             # return rescaled parameters of the intersection
 404             return ( ( a_t0 + a_t * (a_t1 - a_t0),
 405                        b_t0 + b_t * (b_t1 - b_t0) ),
 406                    )
 407
 408 def _bcurvesIntersect(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
 409     """ returns list of intersection points for list of bpathels """
 410
 411     bbox_a = a[0].bbox()
 412     for aa in a[1:]:
 413         bbox_a += aa.bbox()
 414     bbox_b = b[0].bbox()
 415     for bb in b[1:]:
 416         bbox_b += bb.bbox()
 417
 418     if not bbox_a.intersects(bbox_b): return ()
 419
 420     if a_t0+1!=a_t1:
 421         a_tm = (a_t0+a_t1)/2
 422         aa = a[:a_tm-a_t0]
 423         ab = a[a_tm-a_t0:]
 424
 425         if b_t0+1!=b_t1:
 426             b_tm = (b_t0+b_t1)/2
 427             ba = b[:b_tm-b_t0]
 428             bb = b[b_tm-b_t0:]
 429
 430             return ( _bcurvesIntersect(aa, a_t0, a_tm,
 431                                        ba, b_t0, b_tm, epsilon) +
 432                      _bcurvesIntersect(ab, a_tm, a_t1,
 433                                        ba, b_t0, b_tm, epsilon) +
 434                      _bcurvesIntersect(aa, a_t0, a_tm,
 435                                        bb, b_tm, b_t1, epsilon) +
 436                      _bcurvesIntersect(ab, a_tm, a_t1,
 437                                        bb, b_tm, b_t1, epsilon) )
 438         else:
 439             return ( _bcurvesIntersect(aa, a_t0, a_tm,
 440                                        b, b_t0, b_t1, epsilon) +
 441                      _bcurvesIntersect(ab, a_tm, a_t1,
 442                                        b, b_t0, b_t1, epsilon) )
 443     else:
 444         if b_t0+1!=b_t1:
 445             b_tm = (b_t0+b_t1)/2
 446             ba = b[:b_tm-b_t0]
 447             bb = b[b_tm-b_t0:]
 448
 449             return  ( _bcurvesIntersect(a, a_t0, a_t1,
 450                                        ba, b_t0, b_tm, epsilon) +
 451                       _bcurvesIntersect(a, a_t0, a_t1,
 452                                        bb, b_tm, b_t1, epsilon) )
 453         else:
 454             # no more subdivisions of either a or b
 455             # => intersect bpathel a with bpathel b
 456             assert len(a)==len(b)==1, "internal error"
 457             return _bcurveIntersect(a[0], a_t0, a_t1,
 458                                     b[0], b_t0, b_t1, epsilon)
 459
 460
 461 #
 462 # now comes the real stuff...
 463 #
 464
 465 class PathException(Exception): pass
 466
 467 ################################################################################
 468 # _pathcontext: context during walk along path
 469 ################################################################################
 470
 471 class _pathcontext:
 472
 473     """context during walk along path"""
 474
 475     def __init__(self, currentpoint=None, currentsubpath=None):
 476         """ initialize context
 477
 478         currentpoint:   position of current point
 479         currentsubpath: position of first point of current subpath
 480
 481         """
 482
 483         self.currentpoint = currentpoint
 484         self.currentsubpath = currentsubpath
 485
 486 ################################################################################
 487 # pathel: element of a PS style path
 488 ################################################################################
 489
 490 class pathel(base.PSOp):
 491
 492     """element of a PS style path"""
 493
 494     def _updatecontext(self, context):
 495         """update context of during walk along pathel
 496
 497         changes context in place
 498         """
 499
 500
 501     def _bbox(self, context):
 502         """calculate bounding box of pathel
 503
 504         context: context of pathel
 505
 506         returns bounding box of pathel (in given context)
 507
 508         Important note: all coordinates in bbox, currentpoint, and
 509         currrentsubpath have to be floats (in unit.topt)
 510
 511         """
 512
 513         pass
 514
 515     def _normalized(self, context):
 516         """returns tupel consisting of normalized version of pathel
 517
 518         context: context of pathel
 519
 520         returns list consisting of corresponding normalized pathels
 521         moveto_pt, lineto_pt, curveto_pt, closepath in given context
 522
 523         """
 524
 525         pass
 526
 527     def write(self, file):
 528         """write pathel to file in the context of canvas"""
 529
 530         pass
 531
 532 ################################################################################
 533 # normpathel: normalized element of a PS style path
 534 ################################################################################
 535
 536 class normpathel(pathel):
 537
 538     """normalized element of a PS style path"""
 539
 540     def _at(self, context, t):
 541         """returns coordinates of point in pts at parameter t (0<=t<=1)
 542
 543         context: context of normpathel
 544
 545         """
 546
 547         pass
 548
 549     def _bcurve(self, context):
 550         """convert normpathel to bpathel
 551
 552         context: context of normpathel
 553
 554         return bpathel corresponding to pathel in the given context
 555
 556         """
 557
 558         pass
 559
 560     def _arclength(self, context, epsilon=1e-5):
 561         """returns arc length of normpathel in pts in given context
 562
 563         context: context of normpathel
 564         epsilon: epsilon controls the accuracy for calculation of the
 565                  length of the Bezier elements
 566
 567         """
 568
 569         pass
 570
 571     def _lentopar(self, context, lengths, epsilon=1e-5):
 572         """returns tuple (t,l) with
 573           t the parameter where the arclength of normpathel is length and
 574           l the total arclength
 575
 576         length:  length (in pts) to find the parameter for
 577         context: context of normpathel
 578         epsilon: epsilon controls the accuracy for calculation of the
 579                  length of the Bezier elements
 580         """
 581         # Note: _lentopar returns both, parameters and total lengths
 582         # while  lentopar returns only parameters
 583
 584         pass
 585
 586     def _reversed(self, context):
 587         """return reversed normpathel
 588
 589         context: context of normpathel
 590
 591         """
 592
 593         pass
 594
 595     def _split(self, context, parameters):
 596         """splits normpathel
 597
 598         context: contex of normpathel
 599         parameters: list of parameter values (0<=t<=1) at which to split
 600
 601         returns None or list of tuple of normpathels corresponding to
 602         the orginal normpathel.
 603
 604         """
 605
 606         pass
 607
 608     def _tangent(self, context, t):
 609         """returns tangent vector of _normpathel at parameter t (0<=t<=1)
 610
 611         context: context of normpathel
 612
 613         """
 614
 615         pass
 616
 617
 618     def transformed(self, trafo):
 619         """return transformed normpathel according to trafo"""
 620
 621         pass
 622
 623
 624
 625 # first come the various normpathels. Each one comes in two variants:
 626 #  - one which requires the coordinates to be already in pts (mainly
 627 #    used for internal purposes)
 628 #  - another which accepts arbitrary units
 629
 630
 631 class closepath(normpathel):
 632
 633     """Connect subpath back to its starting point"""
 634
 635     def __str__(self):
 636         return "closepath"
 637
 638     def _updatecontext(self, context):
 639         context.currentpoint = None
 640         context.currentsubpath = None
 641
 642     def _at(self, context, t):
 643         x0, y0 = context.currentpoint
 644         x1, y1 = context.currentsubpath
 645         return (x0+(x1-x0)*t, y0+(y1-y0)*t)
 646
 647     def _bbox(self, context):
 648         x0, y0 = context.currentpoint
 649         x1, y1 = context.currentsubpath
 650
 651         return bbox._bbox(min(x0, x1), min(y0, y1),
 652                           max(x0, x1), max(y0, y1))
 653
 654     def _bcurve(self, context):
 655         x0, y0 = context.currentpoint
 656         x1, y1 = context.currentsubpath
 657
 658         return bline_pt(x0, y0, x1, y1)
 659
 660     def _arclength(self, context, epsilon=1e-5):
 661         x0, y0 = context.currentpoint
 662         x1, y1 = context.currentsubpath
 663
 664         return math.sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1))
 665
 666     def _lentopar(self, context, lengths, epsilon=1e-5):
 667         x0, y0 = context.currentpoint
 668         x1, y1 = context.currentsubpath
 669
 670         l = math.sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1))
 671         return ([max(min(1.0*length/l,1),0) for length in lengths], l)
 672
 673     def _normalized(self, context):
 674         return [closepath()]
 675
 676     def _reversed(self, context):
 677         return None
 678
 679     def _split(self, context, parameters):
 680         x0, y0 = context.currentpoint
 681         x1, y1 = context.currentsubpath
 682
 683         if parameters:
 684             lastpoint = None
 685             result = []
 686
 687             if parameters[0]==0:
 688                 result.append(())
 689                 parameters = parameters[1:]
 690                 lastpoint = x0, y0
 691
 692             if parameters:
 693                 for t in parameters:
 694                     xs, ys = x0 + (x1-x0)*t, y0 + (y1-y0)*t
 695                     if lastpoint is None:
 696                         result.append((lineto_pt(xs, ys),))
 697                     else:
 698                         result.append((moveto_pt(*lastpoint), lineto_pt(xs, ys)))
 699                     lastpoint = xs, ys
 700
 701                 if parameters[-1]!=1:
 702                     result.append((moveto_pt(*lastpoint), lineto_pt(x1, y1)))
 703                 else:
 704                     result.append((moveto_pt(x1, y1),))
 705             else:
 706                 result.append((moveto_pt(x0, y0), lineto_pt(x1, y1)))
 707         else:
 708             result = [(moveto_pt(x0, y0), lineto_pt(x1, y1))]
 709
 710         return result
 711
 712     def _tangent(self, context, t):
 713         x0, y0 = context.currentpoint
 714         x1, y1 = context.currentsubpath
 715         tx, ty = x0 + (x1-x0)*t, y0 + (y1-y0)*t
 716         tvectx, tvecty = x1-x0, y1-y0
 717
 718         return line_pt(tx, ty, tx+tvectx, ty+tvecty)
 719
 720     def write(self, file):
 721         file.write("closepath\n")
 722
 723     def transformed(self, trafo):
 724         return closepath()
 725
 726
 727 class moveto_pt(normpathel):
 728
 729     """Set current point to (x, y) (coordinates in pts)"""
 730
 731     def __init__(self, x, y):
 732          self.x = x
 733          self.y = y
 734
 735     def __str__(self):
 736         return "%g %g moveto" % (self.x, self.y)
 737
 738     def _at(self, context, t):
 739         return None
 740
 741     def _updatecontext(self, context):
 742         context.currentpoint = self.x, self.y
 743         context.currentsubpath = self.x, self.y
 744
 745     def _bbox(self, context):
 746         return None
 747
 748     def _bcurve(self, context):
 749         return None
 750
 751     def _arclength(self, context, epsilon=1e-5):
 752         return 0
 753
 754     def _lentopar(self, context, lengths, epsilon=1e-5):
 755         return ([0]*len(lengths), 0)
 756
 757     def _normalized(self, context):
 758         return [moveto_pt(self.x, self.y)]
 759
 760     def _reversed(self, context):
 761         return None
 762
 763     def _split(self, context, parameters):
 764         return None
 765
 766     def _tangent(self, context, t):
 767         return None
 768
 769     def write(self, file):
 770         file.write("%g %g moveto\n" % (self.x, self.y) )
 771
 772     def transformed(self, trafo):
 773         return moveto_pt(*trafo._apply(self.x, self.y))
 774
 775 class lineto_pt(normpathel):
 776
 777     """Append straight line to (x, y) (coordinates in pts)"""
 778
 779     def __init__(self, x, y):
 780          self.x = x
 781          self.y = y
 782
 783     def __str__(self):
 784         return "%g %g lineto" % (self.x, self.y)
 785
 786     def _updatecontext(self, context):
 787         context.currentsubpath = context.currentsubpath or context.currentpoint
 788         context.currentpoint = self.x, self.y
 789
 790     def _at(self, context, t):
 791         x0, y0 = context.currentpoint
 792         return (x0+(self.x-x0)*t, y0+(self.y-y0)*t)
 793
 794     def _bbox(self, context):
 795         return bbox._bbox(min(context.currentpoint[0], self.x),
 796                           min(context.currentpoint[1], self.y),
 797                           max(context.currentpoint[0], self.x),
 798                           max(context.currentpoint[1], self.y))
 799
 800     def _bcurve(self, context):
 801         return bline_pt(context.currentpoint[0], context.currentpoint[1],
 802                       self.x, self.y)
 803
 804     def _arclength(self, context, epsilon=1e-5):
 805         x0, y0 = context.currentpoint
 806
 807         return math.sqrt((x0-self.x)*(x0-self.x)+(y0-self.y)*(y0-self.y))
 808
 809     def _lentopar(self, context, lengths, epsilon=1e-5):
 810         x0, y0 = context.currentpoint
 811         l = math.sqrt((x0-self.x)*(x0-self.x)+(y0-self.y)*(y0-self.y))
 812
 813         return ([max(min(1.0*length/l,1),0) for length in lengths], l)
 814
 815     def _normalized(self, context):
 816         return [lineto_pt(self.x, self.y)]
 817
 818     def _reversed(self, context):
 819         return lineto_pt(*context.currentpoint)
 820
 821     def _split(self, context, parameters):
 822         x0, y0 = context.currentpoint
 823         x1, y1 = self.x, self.y
 824
 825         if parameters:
 826             lastpoint = None
 827             result = []
 828
 829             if parameters[0]==0:
 830                 result.append(())
 831                 parameters = parameters[1:]
 832                 lastpoint = x0, y0
 833
 834             if parameters:
 835                 for t in parameters:
 836                     xs, ys = x0 + (x1-x0)*t, y0 + (y1-y0)*t
 837                     if lastpoint is None:
 838                         result.append((lineto_pt(xs, ys),))
 839                     else:
 840                         result.append((moveto_pt(*lastpoint), lineto_pt(xs, ys)))
 841                     lastpoint = xs, ys
 842
 843                 if parameters[-1]!=1:
 844                     result.append((moveto_pt(*lastpoint), lineto_pt(x1, y1)))
 845                 else:
 846                     result.append((moveto_pt(x1, y1),))
 847             else:
 848                 result.append((moveto_pt(x0, y0), lineto_pt(x1, y1)))
 849         else:
 850             result = [(moveto_pt(x0, y0), lineto_pt(x1, y1))]
 851
 852         return result
 853
 854     def _tangent(self, context, t):
 855         x0, y0 = context.currentpoint
 856         tx, ty = x0 + (self.x-x0)*t, y0 + (self.y-y0)*t
 857         tvectx, tvecty = self.x-x0, self.y-y0
 858
 859         return line_pt(tx, ty, tx+tvectx, ty+tvecty)
 860
 861     def write(self, file):
 862         file.write("%g %g lineto\n" % (self.x, self.y) )
 863
 864     def transformed(self, trafo):
 865         return lineto_pt(*trafo._apply(self.x, self.y))
 866
 867
 868 class curveto_pt(normpathel):
 869
 870     """Append curveto (coordinates in pts)"""
 871
 872     def __init__(self, x1, y1, x2, y2, x3, y3):
 873         self.x1 = x1
 874         self.y1 = y1
 875         self.x2 = x2
 876         self.y2 = y2
 877         self.x3 = x3
 878         self.y3 = y3
 879
 880     def __str__(self):
 881         return "%g %g %g %g %g %g curveto" % (self.x1, self.y1,
 882                                               self.x2, self.y2,
 883                                               self.x3, self.y3)
 884
 885     def _updatecontext(self, context):
 886         context.currentsubpath = context.currentsubpath or context.currentpoint
 887         context.currentpoint = self.x3, self.y3
 888
 889     def _at(self, context, t):
 890         x0, y0 = context.currentpoint
 891         xt = (  (-x0+3*self.x1-3*self.x2+self.x3)*t*t*t +
 892                (3*x0-6*self.x1+3*self.x2        )*t*t +
 893               (-3*x0+3*self.x1                  )*t +
 894               x0)
 895         yt = (  (-y0+3*self.y1-3*self.y2+self.y3)*t*t*t +
 896                (3*y0-6*self.y1+3*self.y2        )*t*t +
 897               (-3*y0+3*self.y1                  )*t +
 898               y0)
 899         return (xt, yt)
 900
 901     def _bbox(self, context):
 902         return bbox._bbox(min(context.currentpoint[0], self.x1, self.x2, self.x3),
 903                           min(context.currentpoint[1], self.y1, self.y2, self.y3),
 904                           max(context.currentpoint[0], self.x1, self.x2, self.x3),
 905                           max(context.currentpoint[1], self.y1, self.y2, self.y3))
 906
 907     def _bcurve(self, context):
 908         return bcurve_pt(context.currentpoint[0], context.currentpoint[1],
 909                          self.x1, self.y1,
 910                          self.x2, self.y2,
 911                          self.x3, self.y3)
 912
 913     def _arclength(self, context, epsilon=1e-5):
 914         return self._bcurve(context).arclength_pt(epsilon)
 915
 916     def _lentopar(self, context, lengths, epsilon=1e-5):
 917         return self._bcurve(context)._lentopar(lengths, epsilon)
 918
 919     def _normalized(self, context):
 920         return [curveto_pt(self.x1, self.y1,
 921                          self.x2, self.y2,
 922                          self.x3, self.y3)]
 923
 924     def _reversed(self, context):
 925         return curveto_pt(self.x2, self.y2,
 926                         self.x1, self.y1,
 927                         context.currentpoint[0], context.currentpoint[1])
 928
 929     def _split(self, context, parameters):
 930         if parameters:
 931             # we need to split
 932             bps = self._bcurve(context).split(list(parameters))
 933
 934             if parameters[0]==0:
 935                 result = [()]
 936             else:
 937                 bp0 = bps[0]
 938                 result = [(curveto_pt(bp0.x1, bp0.y1, bp0.x2, bp0.y2, bp0.x3, bp0.y3),)]
 939                 bps = bps[1:]
 940
 941             for bp in bps:
 942                 result.append((moveto_pt(bp.x0, bp.y0),
 943                                curveto_pt(bp.x1, bp.y1, bp.x2, bp.y2, bp.x3, bp.y3)))
 944
 945             if parameters[-1]==1:
 946                 result.append((moveto_pt(self.x3, self.y3),))
 947
 948         else:
 949             result = [(curveto_pt(self.x1, self.y1,
 950                                 self.x2, self.y2,
 951                                 self.x3, self.y3),)]
 952         return result
 953
 954     def _tangent(self, context, t):
 955         x0, y0 = context.currentpoint
 956         tpx, tpy = self._at(context, t)
 957         tvectx = (3*(  -x0+3*self.x1-3*self.x2+self.x3)*t*t +
 958                   2*( 3*x0-6*self.x1+3*self.x2        )*t +
 959                     (-3*x0+3*self.x1                  ))
 960         tvecty = (3*(  -y0+3*self.y1-3*self.y2+self.y3)*t*t +
 961                   2*( 3*y0-6*self.y1+3*self.y2        )*t +
 962                     (-3*y0+3*self.y1                  ))
 963         return line_pt(tpx, tpy, tpx+tvectx, tpy+tvecty)
 964
 965     def write(self, file):
 966         file.write("%g %g %g %g %g %g curveto\n" % ( self.x1, self.y1,
 967                                                      self.x2, self.y2,
 968                                                      self.x3, self.y3 ) )
 969
 970     def transformed(self, trafo):
 971         return curveto_pt(*(trafo._apply(self.x1, self.y1)+
 972                           trafo._apply(self.x2, self.y2)+
 973                           trafo._apply(self.x3, self.y3)))
 974
 975 #
 976 # now the versions that convert from user coordinates to pts
 977 #
 978
 979 class moveto(moveto_pt):
 980
 981     """Set current point to (x, y)"""
 982
 983     def __init__(self, x, y):
 984          moveto_pt.__init__(self, unit.topt(x), unit.topt(y))
 985
 986
 987 class lineto(lineto_pt):
 988
 989     """Append straight line to (x, y)"""
 990
 991     def __init__(self, x, y):
 992         lineto_pt.__init__(self, unit.topt(x), unit.topt(y))
 993
 994
 995 class curveto(curveto_pt):
 996
 997     """Append curveto"""
 998
 999     def __init__(self, x1, y1, x2, y2, x3, y3):
1000         curveto_pt.__init__(self,
1001                           unit.topt(x1), unit.topt(y1),
1002                           unit.topt(x2), unit.topt(y2),
1003                           unit.topt(x3), unit.topt(y3))
1004
1005 #
1006 # now come the pathels, again in two versions
1007 #
1008
1009 class rmoveto_pt(pathel):
1010
1011     """Perform relative moveto (coordinates in pts)"""
1012
1013     def __init__(self, dx, dy):
1014          self.dx = dx
1015          self.dy = dy
1016
1017     def _updatecontext(self, context):
1018         context.currentpoint = (context.currentpoint[0] + self.dx,
1019                                 context.currentpoint[1] + self.dy)
1020         context.currentsubpath = context.currentpoint
1021
1022     def _bbox(self, context):
1023         return None
1024
1025     def _normalized(self, context):
1026         x = context.currentpoint[0]+self.dx
1027         y = context.currentpoint[1]+self.dy
1028
1029         return [moveto_pt(x, y)]
1030
1031     def write(self, file):
1032         file.write("%g %g rmoveto\n" % (self.dx, self.dy) )
1033
1034
1035 class rlineto_pt(pathel):
1036
1037     """Perform relative lineto (coordinates in pts)"""
1038
1039     def __init__(self, dx, dy):
1040          self.dx = dx
1041          self.dy = dy
1042
1043     def _updatecontext(self, context):
1044         context.currentsubpath = context.currentsubpath or context.currentpoint
1045         context.currentpoint = (context.currentpoint[0]+self.dx,
1046                                 context.currentpoint[1]+self.dy)
1047
1048     def _bbox(self, context):
1049         x = context.currentpoint[0] + self.dx
1050         y = context.currentpoint[1] + self.dy
1051         return bbox._bbox(min(context.currentpoint[0], x),
1052                           min(context.currentpoint[1], y),
1053                           max(context.currentpoint[0], x),
1054                           max(context.currentpoint[1], y))
1055
1056     def _normalized(self, context):
1057         x = context.currentpoint[0] + self.dx
1058         y = context.currentpoint[1] + self.dy
1059
1060         return [lineto_pt(x, y)]
1061
1062     def write(self, file):
1063         file.write("%g %g rlineto\n" % (self.dx, self.dy) )
1064
1065
1066 class rcurveto_pt(pathel):
1067
1068     """Append rcurveto (coordinates in pts)"""
1069
1070     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
1071         self.dx1 = dx1
1072         self.dy1 = dy1
1073         self.dx2 = dx2
1074         self.dy2 = dy2
1075         self.dx3 = dx3
1076         self.dy3 = dy3
1077
1078     def write(self, file):
1079         file.write("%g %g %g %g %g %g rcurveto\n" % ( self.dx1, self.dy1,
1080                                                     self.dx2, self.dy2,
1081                                                     self.dx3, self.dy3 ) )
1082
1083     def _updatecontext(self, context):
1084         x3 = context.currentpoint[0]+self.dx3
1085         y3 = context.currentpoint[1]+self.dy3
1086
1087         context.currentsubpath = context.currentsubpath or context.currentpoint
1088         context.currentpoint = x3, y3
1089
1090
1091     def _bbox(self, context):
1092         x1 = context.currentpoint[0]+self.dx1
1093         y1 = context.currentpoint[1]+self.dy1
1094         x2 = context.currentpoint[0]+self.dx2
1095         y2 = context.currentpoint[1]+self.dy2
1096         x3 = context.currentpoint[0]+self.dx3
1097         y3 = context.currentpoint[1]+self.dy3
1098         return bbox._bbox(min(context.currentpoint[0], x1, x2, x3),
1099                           min(context.currentpoint[1], y1, y2, y3),
1100                           max(context.currentpoint[0], x1, x2, x3),
1101                           max(context.currentpoint[1], y1, y2, y3))
1102
1103     def _normalized(self, context):
1104         x2 = context.currentpoint[0]+self.dx1
1105         y2 = context.currentpoint[1]+self.dy1
1106         x3 = context.currentpoint[0]+self.dx2
1107         y3 = context.currentpoint[1]+self.dy2
1108         x4 = context.currentpoint[0]+self.dx3
1109         y4 = context.currentpoint[1]+self.dy3
1110
1111         return [curveto_pt(x2, y2, x3, y3, x4, y4)]
1112
1113 #
1114 # arc, arcn, arct
1115 #
1116
1117 class arc_pt(pathel):
1118
1119     """Append counterclockwise arc (coordinates in pts)"""
1120
1121     def __init__(self, x, y, r, angle1, angle2):
1122         self.x = x
1123         self.y = y
1124         self.r = r
1125         self.angle1 = angle1
1126         self.angle2 = angle2
1127
1128     def _sarc(self):
1129         """Return starting point of arc segment"""
1130         return (self.x+self.r*cos(radians(self.angle1)),
1131                 self.y+self.r*sin(radians(self.angle1)))
1132
1133     def _earc(self):
1134         """Return end point of arc segment"""
1135         return (self.x+self.r*cos(radians(self.angle2)),
1136                 self.y+self.r*sin(radians(self.angle2)))
1137
1138     def _updatecontext(self, context):
1139         if context.currentpoint:
1140             context.currentsubpath = context.currentsubpath or context.currentpoint
1141         else:
1142             # we assert that currentsubpath is also None
1143             context.currentsubpath = self._sarc()
1144
1145         context.currentpoint = self._earc()
1146
1147     def _bbox(self, context):
1148         phi1 = radians(self.angle1)
1149         phi2 = radians(self.angle2)
1150
1151         # starting end end point of arc segment
1152         sarcx, sarcy = self._sarc()
1153         earcx, earcy = self._earc()
1154
1155         # Now, we have to determine the corners of the bbox for the
1156         # arc segment, i.e. global maxima/mimima of cos(phi) and sin(phi)
1157         # in the interval [phi1, phi2]. These can either be located
1158         # on the borders of this interval or in the interior.
1159
1160         if phi2<phi1:
1161             # guarantee that phi2>phi1
1162             phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
1163
1164         # next minimum of cos(phi) looking from phi1 in counterclockwise
1165         # direction: 2*pi*floor((phi1-pi)/(2*pi)) + 3*pi
1166
1167         if phi2<(2*math.floor((phi1-pi)/(2*pi))+3)*pi:
1168             minarcx = min(sarcx, earcx)
1169         else:
1170             minarcx = self.x-self.r
1171
1172         # next minimum of sin(phi) looking from phi1 in counterclockwise
1173         # direction: 2*pi*floor((phi1-3*pi/2)/(2*pi)) + 7/2*pi
1174
1175         if phi2<(2*math.floor((phi1-3.0*pi/2)/(2*pi))+7.0/2)*pi:
1176             minarcy = min(sarcy, earcy)
1177         else:
1178             minarcy = self.y-self.r
1179
1180         # next maximum of cos(phi) looking from phi1 in counterclockwise
1181         # direction: 2*pi*floor((phi1)/(2*pi))+2*pi
1182
1183         if phi2<(2*math.floor((phi1)/(2*pi))+2)*pi:
1184             maxarcx = max(sarcx, earcx)
1185         else:
1186             maxarcx = self.x+self.r
1187
1188         # next maximum of sin(phi) looking from phi1 in counterclockwise
1189         # direction: 2*pi*floor((phi1-pi/2)/(2*pi)) + 1/2*pi
1190
1191         if phi2<(2*math.floor((phi1-pi/2)/(2*pi))+5.0/2)*pi:
1192             maxarcy = max(sarcy, earcy)
1193         else:
1194             maxarcy = self.y+self.r
1195
1196         # Finally, we are able to construct the bbox for the arc segment.
1197         # Note that if there is a currentpoint defined, we also
1198         # have to include the straight line from this point
1199         # to the first point of the arc segment
1200
1201         if context.currentpoint:
1202             return (bbox._bbox(min(context.currentpoint[0], sarcx),
1203                               min(context.currentpoint[1], sarcy),
1204                               max(context.currentpoint[0], sarcx),
1205                               max(context.currentpoint[1], sarcy)) +
1206                     bbox._bbox(minarcx, minarcy, maxarcx, maxarcy)
1207                     )
1208         else:
1209             return  bbox._bbox(minarcx, minarcy, maxarcx, maxarcy)
1210
1211     def _normalized(self, context):
1212         # get starting and end point of arc segment and bpath corresponding to arc
1213         sarcx, sarcy = self._sarc()
1214         earcx, earcy = self._earc()
1215         barc = _arctobezierpath(self.x, self.y, self.r, self.angle1, self.angle2)
1216
1217         # convert to list of curvetos omitting movetos
1218         nbarc = []
1219
1220         for bpathel in barc:
1221             nbarc.append(curveto_pt(bpathel.x1, bpathel.y1,
1222                                   bpathel.x2, bpathel.y2,
1223                                   bpathel.x3, bpathel.y3))
1224
1225         # Note that if there is a currentpoint defined, we also
1226         # have to include the straight line from this point
1227         # to the first point of the arc segment.
1228         # Otherwise, we have to add a moveto at the beginning
1229         if context.currentpoint:
1230             return [lineto_pt(sarcx, sarcy)] + nbarc
1231         else:
1232             return [moveto_pt(sarcx, sarcy)] + nbarc
1233
1234
1235     def write(self, file):
1236         file.write("%g %g %g %g %g arc\n" % ( self.x, self.y,
1237                                             self.r,
1238                                             self.angle1,
1239                                             self.angle2 ) )
1240
1241
1242 class arcn_pt(pathel):
1243
1244     """Append clockwise arc (coordinates in pts)"""
1245
1246     def __init__(self, x, y, r, angle1, angle2):
1247         self.x = x
1248         self.y = y
1249         self.r = r
1250         self.angle1 = angle1
1251         self.angle2 = angle2
1252
1253     def _sarc(self):
1254         """Return starting point of arc segment"""
1255         return (self.x+self.r*cos(radians(self.angle1)),
1256                 self.y+self.r*sin(radians(self.angle1)))
1257
1258     def _earc(self):
1259         """Return end point of arc segment"""
1260         return (self.x+self.r*cos(radians(self.angle2)),
1261                 self.y+self.r*sin(radians(self.angle2)))
1262
1263     def _updatecontext(self, context):
1264         if context.currentpoint:
1265             context.currentsubpath = context.currentsubpath or context.currentpoint
1266         else:  # we assert that currentsubpath is also None
1267             context.currentsubpath = self._sarc()
1268
1269         context.currentpoint = self._earc()
1270
1271     def _bbox(self, context):
1272         # in principle, we obtain bbox of an arcn element from
1273         # the bounding box of the corrsponding arc element with
1274         # angle1 and angle2 interchanged. Though, we have to be carefull
1275         # with the straight line segment, which is added if currentpoint
1276         # is defined.
1277
1278         # Hence, we first compute the bbox of the arc without this line:
1279
1280         a = arc_pt(self.x, self.y, self.r,
1281                  self.angle2,
1282                  self.angle1)
1283
1284         sarc = self._sarc()
1285         arcbb = a._bbox(_pathcontext())
1286
1287         # Then, we repeat the logic from arc.bbox, but with interchanged
1288         # start and end points of the arc
1289
1290         if context.currentpoint:
1291             return  bbox._bbox(min(context.currentpoint[0], sarc[0]),
1292                                min(context.currentpoint[1], sarc[1]),
1293                                max(context.currentpoint[0], sarc[0]),
1294                                max(context.currentpoint[1], sarc[1]))+ arcbb
1295         else:
1296             return arcbb
1297
1298     def _normalized(self, context):
1299         # get starting and end point of arc segment and bpath corresponding to arc
1300         sarcx, sarcy = self._sarc()
1301         earcx, earcy = self._earc()
1302         barc = _arctobezierpath(self.x, self.y, self.r, self.angle2, self.angle1)
1303         barc.reverse()
1304
1305         # convert to list of curvetos omitting movetos
1306         nbarc = []
1307
1308         for bpathel in barc:
1309             nbarc.append(curveto_pt(bpathel.x2, bpathel.y2,
1310                                   bpathel.x1, bpathel.y1,
1311                                   bpathel.x0, bpathel.y0))
1312
1313         # Note that if there is a currentpoint defined, we also
1314         # have to include the straight line from this point
1315         # to the first point of the arc segment.
1316         # Otherwise, we have to add a moveto at the beginning
1317         if context.currentpoint:
1318             return [lineto_pt(sarcx, sarcy)] + nbarc
1319         else:
1320             return [moveto_pt(sarcx, sarcy)] + nbarc
1321
1322
1323     def write(self, file):
1324         file.write("%g %g %g %g %g arcn\n" % ( self.x, self.y,
1325                                              self.r,
1326                                              self.angle1,
1327                                              self.angle2 ) )
1328
1329
1330 class arct_pt(pathel):
1331
1332     """Append tangent arc (coordinates in pts)"""
1333
1334     def __init__(self, x1, y1, x2, y2, r):
1335         self.x1 = x1
1336         self.y1 = y1
1337         self.x2 = x2
1338         self.y2 = y2
1339         self.r  = r
1340
1341     def write(self, file):
1342         file.write("%g %g %g %g %g arct\n" % ( self.x1, self.y1,
1343                                              self.x2, self.y2,
1344                                              self.r ) )
1345     def _path(self, currentpoint, currentsubpath):
1346         """returns new currentpoint, currentsubpath and path consisting
1347         of arc and/or line which corresponds to arct
1348
1349         this is a helper routine for _bbox and _normalized, which both need
1350         this path. Note: we don't want to calculate the bbox from a bpath
1351
1352         """
1353
1354         # direction and length of tangent 1
1355         dx1  = currentpoint[0]-self.x1
1356         dy1  = currentpoint[1]-self.y1
1357         l1   = math.sqrt(dx1*dx1+dy1*dy1)
1358
1359         # direction and length of tangent 2
1360         dx2  = self.x2-self.x1
1361         dy2  = self.y2-self.y1
1362         l2   = math.sqrt(dx2*dx2+dy2*dy2)
1363
1364         # intersection angle between two tangents
1365         alpha = math.acos((dx1*dx2+dy1*dy2)/(l1*l2))
1366
1367         if math.fabs(sin(alpha))>=1e-15 and 1.0+self.r!=1.0:
1368             cotalpha2 = 1.0/math.tan(alpha/2)
1369
1370             # two tangent points
1371             xt1 = self.x1+dx1*self.r*cotalpha2/l1
1372             yt1 = self.y1+dy1*self.r*cotalpha2/l1
1373             xt2 = self.x1+dx2*self.r*cotalpha2/l2
1374             yt2 = self.y1+dy2*self.r*cotalpha2/l2
1375
1376             # direction of center of arc
1377             rx = self.x1-0.5*(xt1+xt2)
1378             ry = self.y1-0.5*(yt1+yt2)
1379             lr = math.sqrt(rx*rx+ry*ry)
1380
1381             # angle around which arc is centered
1382
1383             if rx==0:
1384                 phi=90
1385             elif rx>0:
1386                 phi = degrees(math.atan(ry/rx))
1387             else:
1388                 phi = degrees(math.atan(rx/ry))+180
1389
1390             # half angular width of arc
1391             deltaphi = 90*(1-alpha/pi)
1392
1393             # center position of arc
1394             mx = self.x1-rx*self.r/(lr*sin(alpha/2))
1395             my = self.y1-ry*self.r/(lr*sin(alpha/2))
1396
1397             # now we are in the position to construct the path
1398             p = path(moveto_pt(*currentpoint))
1399
1400             if phi<0:
1401                 p.append(arc_pt(mx, my, self.r, phi-deltaphi, phi+deltaphi))
1402             else:
1403                 p.append(arcn_pt(mx, my, self.r, phi+deltaphi, phi-deltaphi))
1404
1405             return ( (xt2, yt2) ,
1406                      currentsubpath or (xt2, yt2),
1407                      p )
1408
1409         else:
1410             # we need no arc, so just return a straight line to currentpoint to x1, y1
1411             return  ( (self.x1, self.y1),
1412                       currentsubpath or (self.x1, self.y1),
1413                       line_pt(currentpoint[0], currentpoint[1], self.x1, self.y1) )
1414
1415     def _updatecontext(self, context):
1416         r = self._path(context.currentpoint,
1417                        context.currentsubpath)
1418
1419         context.currentpoint, context.currentsubpath = r[:2]
1420
1421     def _bbox(self, context):
1422         return self._path(context.currentpoint,
1423                           context.currentsubpath)[2].bbox()
1424
1425     def _normalized(self, context):
1426         return _normalizepath(self._path(context.currentpoint,
1427                               context.currentsubpath)[2])
1428
1429 #
1430 # the user coordinates versions...
1431 #
1432
1433 class rmoveto(rmoveto_pt):
1434
1435     """Perform relative moveto"""
1436
1437     def __init__(self, dx, dy):
1438         rmoveto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
1439
1440
1441 class rlineto(rlineto_pt):
1442
1443     """Perform relative lineto"""
1444
1445     def __init__(self, dx, dy):
1446         rlineto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
1447
1448
1449 class rcurveto(rcurveto_pt):
1450
1451     """Append rcurveto"""
1452
1453     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
1454         rcurveto_pt.__init__(self,
1455                            unit.topt(dx1), unit.topt(dy1),
1456                            unit.topt(dx2), unit.topt(dy2),
1457                            unit.topt(dx3), unit.topt(dy3))
1458
1459
1460 class arcn(arcn_pt):
1461
1462     """Append clockwise arc"""
1463
1464     def __init__(self, x, y, r, angle1, angle2):
1465         arcn_pt.__init__(self,
1466                        unit.topt(x), unit.topt(y), unit.topt(r),
1467                        angle1, angle2)
1468
1469
1470 class arc(arc_pt):
1471
1472     """Append counterclockwise arc"""
1473
1474     def __init__(self, x, y, r, angle1, angle2):
1475         arc_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r),
1476                       angle1, angle2)
1477
1478
1479 class arct(arct_pt):
1480
1481     """Append tangent arc"""
1482
1483     def __init__(self, x1, y1, x2, y2, r):
1484         arct_pt.__init__(self, unit.topt(x1), unit.topt(y1),
1485                              unit.topt(x2), unit.topt(y2),
1486                              unit.topt(r))
1487
1488 #
1489 # non PS pathels provided mostly for performance reasons
1490 #
1491
1492 class multilineto_pt(pathel):
1493
1494     """Perform multiple linetos (coordinates in pts)"""
1495
1496     def __init__(self, points):
1497          self.points = points
1498
1499     def _updatecontext(self, context):
1500         context.currentsubpath = context.currentsubpath or context.currentpoint
1501         context.currentpoint = self.points[-1]
1502
1503     def _bbox(self, context):
1504         xs = [point[0] for point in self.points]
1505         ys = [point[1] for point in self.points]
1506         return bbox._bbox(min(context.currentpoint[0], *xs),
1507                           min(context.currentpoint[1], *ys),
1508                           max(context.currentpoint[0], *xs),
1509                           max(context.currentpoint[1], *ys))
1510
1511     def _normalized(self, context):
1512         return [lineto_pt(x, y) for x, y in self.points]
1513
1514     def write(self, file):
1515         for x, y in self.points:
1516             file.write("%g %g lineto\n" % (x, y) )
1517
1518
1519 class multicurveto_pt(pathel):
1520
1521     """Perform multiple curvetos (coordinates in pts)"""
1522
1523     def __init__(self, points):
1524          self.points = points
1525
1526     def _updatecontext(self, context):
1527         context.currentsubpath = context.currentsubpath or context.currentpoint
1528         context.currentpoint = self.points[-1]
1529
1530     def _bbox(self, context):
1531         xs = [point[0] for point in self.points] + [point[2] for point in self.points] + [point[2] for point in self.points]
1532         ys = [point[1] for point in self.points] + [point[3] for point in self.points] + [point[5] for point in self.points]
1533         return bbox._bbox(min(context.currentpoint[0], *xs),
1534                           min(context.currentpoint[1], *ys),
1535                           max(context.currentpoint[0], *xs),
1536                           max(context.currentpoint[1], *ys))
1537
1538     def _normalized(self, context):
1539         return [curveto_pt(*point) for point in self.points]
1540
1541     def write(self, file):
1542         for point in self.points:
1543             file.write("%g %g %g %g %g %g curveto\n" % tuple(point))
1544
1545
1546 ################################################################################
1547 # path: PS style path
1548 ################################################################################
1549
1550 class path(base.PSCmd):
1551
1552     """PS style path"""
1553
1554     def __init__(self, *args):
1555         if len(args)==1 and isinstance(args[0], path):
1556             self.path = args[0].path
1557         else:
1558             self.path = list(args)
1559
1560     def __add__(self, other):
1561         return path(*(self.path+other.path))
1562
1563     def __iadd__(self, other):
1564         self.path += other.path
1565         return self
1566
1567     def __getitem__(self, i):
1568         return self.path[i]
1569
1570     def __len__(self):
1571         return len(self.path)
1572
1573     def append(self, pathel):
1574         self.path.append(pathel)
1575
1576     def arclength_pt(self, epsilon=1e-5):
1577         """returns total arc length of path in pts with accuracy epsilon"""
1578         return normpath(self).arclength_pt(epsilon)
1579
1580     def arclength(self, epsilon=1e-5):
1581         """returns total arc length of path with accuracy epsilon"""
1582         return normpath(self).arclength(epsilon)
1583
1584     def lentopar(self, lengths, epsilon=1e-5):
1585         """returns (t,l) with t the parameter value(s) matching given length,
1586         l the total length"""
1587         return normpath(self).lentopar(lengths, epsilon)
1588
1589     def at_pt(self, t):
1590         """return coordinates in pts of corresponding normpath at parameter value t"""
1591         return normpath(self).at_pt(t)
1592
1593     def at(self, t):
1594         """return coordinates of corresponding normpath at parameter value t"""
1595         return normpath(self).at(t)
1596
1597     def bbox(self):
1598         context = _pathcontext()
1599         abbox = None
1600
1601         for pel in self.path:
1602             nbbox =  pel._bbox(context)
1603             pel._updatecontext(context)
1604             if abbox is None:
1605                 abbox = nbbox
1606             elif nbbox:
1607                 abbox += nbbox
1608
1609         return abbox
1610
1611     def begin_pt(self):
1612         """return coordinates of first point of first subpath in path (in pts)"""
1613         return normpath(self).begin_pt()
1614
1615     def begin(self):
1616         """return coordinates of first point of first subpath in path"""
1617         return normpath(self).begin()
1618
1619     def end_pt(self):
1620         """return coordinates of last point of last subpath in path (in pts)"""
1621         return normpath(self).end_pt()
1622
1623     def end(self):
1624         """return coordinates of last point of last subpath in path"""
1625         return normpath(self).end()
1626
1627     def glue(self, other):
1628         """return path consisting of self and other glued together"""
1629         return normpath(self).glue(other)
1630
1631     # << operator also designates glueing
1632     __lshift__ = glue
1633
1634     def intersect(self, other, epsilon=1e-5):
1635         """intersect normpath corresponding to self with other path"""
1636         return normpath(self).intersect(other, epsilon)
1637
1638     def range(self):
1639         """return maximal value for parameter value t for corr. normpath"""
1640         return normpath(self).range()
1641
1642     def reversed(self):
1643         """return reversed path"""
1644         return normpath(self).reversed()
1645
1646     def split(self, parameters):
1647         """return corresponding normpaths split at parameter value t"""
1648         return normpath(self).split(parameters)
1649
1650     def tangent(self, t, length=None):
1651         """return tangent vector at parameter value t of corr. normpath"""
1652         return normpath(self).tangent(t, length)
1653
1654     def transformed(self, trafo):
1655         """return transformed path"""
1656         return normpath(self).transformed(trafo)
1657
1658     def write(self, file):
1659         if not (isinstance(self.path[0], moveto_pt) or
1660                 isinstance(self.path[0], arc_pt) or
1661                 isinstance(self.path[0], arcn_pt)):
1662             raise PathException("first path element must be either moveto, arc, or arcn")
1663         for pel in self.path:
1664             pel.write(file)
1665
1666 ################################################################################
1667 # normpath: normalized PS style path
1668 ################################################################################
1669
1670 # helper routine for the normalization of a path
1671
1672 def _normalizepath(path):
1673     context = _pathcontext()
1674     np = []
1675     for pel in path:
1676         npels = pel._normalized(context)
1677         pel._updatecontext(context)
1678         if npels:
1679             for npel in npels:
1680                 np.append(npel)
1681     return np
1682
1683 # helper routine for the splitting of subpaths
1684
1685 def _splitclosedsubpath(subpath, parameters):
1686     """ split closed subpath at list of parameters (counting from t=0)"""
1687
1688     # first, we open the subpath by replacing the closepath by a lineto_pt
1689     # Note that the first pel must be a moveto_pt
1690     opensubpath = copy.copy(subpath)
1691     opensubpath[-1] = lineto_pt(subpath[0].x, subpath[0].y)
1692
1693     # then we split this open subpath
1694     pieces = _splitopensubpath(opensubpath, parameters)
1695
1696     # finally we glue the first and the last piece together
1697     pieces[0] = pieces[-1] << pieces[0]
1698
1699     # and throw the last piece away
1700     return pieces[:-1]
1701
1702
1703 def _splitopensubpath(subpath, parameters):
1704     """ split open subpath at list of parameters (counting from t=0)"""
1705
1706     context = _pathcontext()
1707     result = []
1708
1709     # first pathel of subpath must be moveto_pt
1710     pel = subpath[0]
1711     pel._updatecontext(context)
1712     np = normpath(pel)
1713     t = 0
1714
1715     for pel in subpath[1:]:
1716         if not parameters or t+1<parameters[0]:
1717             np.path.append(pel)
1718         else:
1719             for i in range(len(parameters)):
1720                 if parameters[i]>t+1: break
1721             else:
1722                 i = len(parameters)
1723
1724             pieces = pel._split(context,
1725                                 [x-t for x in parameters[:i]])
1726
1727             parameters = parameters[i:]
1728
1729             # the first item of pieces finishes np
1730             np.path.extend(pieces[0])
1731             result.append(np)
1732
1733             # the intermediate ones are normpaths by themselves
1734             for np in pieces[1:-1]:
1735                 result.append(normpath(*np))
1736
1737             # we continue to work with the last one
1738             np = normpath(*pieces[-1])
1739
1740         # go further along path
1741         t += 1
1742         pel._updatecontext(context)
1743
1744     if len(np)>0:
1745         result.append(np)
1746
1747     return result
1748
1749
1750 class normpath(path):
1751
1752     """normalized PS style path"""
1753
1754     def __init__(self, *args):
1755         if len(args)==1 and isinstance(args[0], path):
1756             path.__init__(self, *_normalizepath(args[0].path))
1757         else:
1758             path.__init__(self, *_normalizepath(args))
1759
1760     def __add__(self, other):
1761         return normpath(*(self.path+other.path))
1762
1763     def __iadd__(self, other):
1764         self.path += normpath(other).path
1765         return self
1766
1767     def __str__(self):
1768         return string.join(map(str, self.path), "\n")
1769
1770     def _subpaths(self):
1771         """returns list of tuples (subpath, t0, tf, closed),
1772         one for each subpath. Here are
1773
1774         subpath: list of pathels corresponding subpath
1775         t0: parameter value corresponding to begin of subpath
1776         tf: parameter value corresponding to end of subpath
1777         closed: subpath is closed, i.e. ends with closepath
1778
1779         """
1780         t = t0 = 0
1781         result = []
1782         subpath = []
1783
1784         for pel in self.path:
1785             subpath.append(pel)
1786             if isinstance(pel, moveto_pt) and len(subpath)>1:
1787                 result.append((subpath, t0, t, 0))
1788                 subpath = []
1789                 t0 = t
1790             elif isinstance(pel, closepath):
1791                 result.append((subpath, t0, t, 1))
1792                 subpath = []
1793                 t = t
1794                 t += 1
1795             else:
1796                 t += 1
1797
1798         if len(subpath)>1:
1799             result.append((subpath, t0, t-1, 0))
1800
1801         return result
1802
1803     def append(self, pathel):
1804         self.path.append(pathel)
1805         self.path = _normalizepath(self.path)
1806
1807     def arclength_pt(self, epsilon=1e-5):
1808         """returns total arc length of normpath in pts with accuracy epsilon"""
1809         context = _pathcontext()
1810         length = 0
1811         for pel in self.path:
1812             length += pel._arclength(context, epsilon)
1813             pel._updatecontext(context)
1814         return length
1815
1816     def arclength(self, epsilon=1e-5):
1817         """returns total arc length of normpath with accuracy epsilon"""
1818         return unit.t_pt(self.arclength_pt(epsilon))
1819
1820     def lentopar(self, lengths, epsilon=1e-5):
1821         """returns [t,l] with t the parameter value(s) matching given length(s)
1822         and l the total length"""
1823
1824         context = _pathcontext()
1825         l = len(helper.ensuresequence(lengths))
1826
1827         # split the list of lengths apart for positive and negative values
1828         t = [[],[]]
1829         rests = [[],[]] # first the positive then the negative lengths
1830         retrafo = [] # for resorting the rests into lengths
1831         for length in helper.ensuresequence(lengths):
1832             length = unit.topt(length)
1833             if length>=0.0:
1834                 rests[0].append(length)
1835                 retrafo.append( [0, len(rests[0])-1] )
1836                 t[0].append(0)
1837             else:
1838                 rests[1].append(-length)
1839                 retrafo.append( [1, len(rests[1])-1] )
1840                 t[1].append(0)
1841
1842         # go through the positive lengths
1843         for pel in self.path:
1844             # we need arclength for knowing when all the parameters are done
1845             pars, arclength = pel._lentopar(context, rests[0], epsilon)
1846             finis = 0
1847             for i in range(len(rests[0])):
1848                 t[0][i] += pars[i]
1849                 rests[0][i] -= arclength
1850                 if rests[0][i]<0: finis += 1
1851             if finis==len(rests[0]): break
1852             pel._updatecontext(context)
1853
1854         # go through the negative lengths
1855         for pel in self.reversed().path:
1856             pars, arclength = pel._lentopar(context, rests[1], epsilon)
1857             finis = 0
1858             for i in range(len(rests[1])):
1859                 t[1][i] -= pars[i]
1860                 rests[1][i] -= arclength
1861                 if rests[1][i]<0: finis += 1
1862             if finis==len(rests[1]): break
1863             pel._updatecontext(context)
1864
1865         # resort the positive and negative values into one list
1866         tt = [ t[p[0]][p[1]] for p in retrafo ]
1867         if not helper.issequence(lengths): tt = tt[0]
1868
1869         return tt
1870
1871     def at_pt(self, t):
1872         """return coordinates in pts of path at parameter value t
1873
1874         Negative values of t count from the end of the path. The absolute
1875         value of t must be smaller or equal to the number of segments in
1876         the normpath, otherwise None is returned.
1877         At discontinuities in the path, the limit from below is returned
1878
1879         """
1880
1881         if t>=0:
1882             p = self.path
1883         else:
1884             p = self.reversed().path
1885             t = -t
1886
1887         context = _pathcontext()
1888
1889         for pel in p:
1890             if not isinstance(pel, moveto_pt):
1891                 if t>1:
1892                     t -= 1
1893                 else:
1894                     return pel._at(context, t)
1895             pel._updatecontext(context)
1896
1897         return None
1898
1899     def at(self, t):
1900         """return coordinates of path at parameter value t
1901
1902         Negative values of t count from the end of the path. The absolute
1903         value of t must be smaller or equal to the number of segments in
1904         the normpath, otherwise None is returned.
1905         At discontinuities in the path, the limit from below is returned
1906
1907         """
1908         result = self.at_pt(t)
1909         if result:
1910             return unit.t_pt(result[0]), unit.t_pt(result[1])
1911         else:
1912             return result
1913
1914     def begin_pt(self):
1915         """return coordinates of first point of first subpath in path (in pts)"""
1916         return self.at_pt(0)
1917
1918     def begin(self):
1919         """return coordinates of first point of first subpath in path"""
1920         return self.at(0)
1921
1922     def end_pt(self):
1923         """return coordinates of last point of last subpath in path (in pts)"""
1924         return self.reversed().at_pt(0)
1925
1926     def end(self):
1927         """return coordinates of last point of last subpath in path"""
1928         return self.reversed().at(0)
1929
1930     def glue(self, other):
1931         # XXX check for closepath at end and raise Exception
1932         if isinstance(other, normpath):
1933             return normpath(*(self.path+other.path[1:]))
1934         else:
1935             return path(*(self.path+normpath(other).path[1:]))
1936
1937     def intersect(self, other, epsilon=1e-5):
1938         """intersect self with other path
1939
1940         returns a tuple of lists consisting of the parameter values
1941         of the intersection points of the corresponding normpath
1942
1943         """
1944
1945         if not isinstance(other, normpath):
1946             other = normpath(other)
1947
1948         # convert both paths to series of bpathels: bpathels_a and bpathels_b
1949         # store list of parameter values corresponding to sub path ends in
1950         # subpathends_a and subpathends_b
1951         context = _pathcontext()
1952         bpathels_a = []
1953         subpathends_a = []
1954         t = 0
1955         for normpathel in self.path:
1956             bpathel = normpathel._bcurve(context)
1957             if bpathel:
1958                 bpathels_a.append(bpathel)
1959             normpathel._updatecontext(context)
1960             if isinstance(normpathel, closepath):
1961                 subpathends_a.append(t)
1962             t += 1
1963
1964         context = _pathcontext()
1965         bpathels_b = []
1966         subpathends_b = []
1967         t = 0
1968         for normpathel in other.path:
1969             bpathel = normpathel._bcurve(context)
1970             if bpathel:
1971                 bpathels_b.append(bpathel)
1972             normpathel._updatecontext(context)
1973             if isinstance(normpathel, closepath):
1974                 subpathends_b.append(t)
1975             t += 1
1976
1977         intersections = ([], [])
1978         # change grouping order and check whether an intersection
1979         # occurs at the end of a subpath. If yes, don't include
1980         # it in list of intersections to prevent double results
1981         for intersection in  _bcurvesIntersect(bpathels_a, 0, len(bpathels_a),
1982                                                bpathels_b, 0, len(bpathels_b),
1983                                                epsilon):
1984             if not ([subpathend_a
1985                      for subpathend_a in subpathends_a
1986                      if abs(intersection[0]-subpathend_a)<epsilon] or
1987                     [subpathend_b
1988                      for subpathend_b in subpathends_b
1989                      if abs(intersection[1]-subpathend_b)<epsilon]):
1990                 intersections[0].append(intersection[0])
1991                 intersections[1].append(intersection[1])
1992
1993         return intersections
1994
1995         # XXX: the following code is not used, but probably we could
1996         # use it for short lists of bpathels
1997
1998         # alternative implementation (not recursive, probably more efficient
1999         # for short lists bpathel_a and bpathel_b)
2000         t_a = 0
2001         for bpathel_a in bpathels_a:
2002             t_a += 1
2003             t_b = 0
2004             for bpathel_b in bpathels_b:
2005                 t_b += 1
2006                 newintersections = _bcurveIntersect(bpathel_a, t_a-1, t_a,
2007                                                     bpathel_b, t_b-1, t_b, epsilon)
2008
2009                 # change grouping order
2010                 for newintersection in newintersections:
2011                     intersections[0].append(newintersection[0])
2012                     intersections[1].append(newintersection[1])
2013
2014         return intersections
2015
2016     def range(self):
2017         """return maximal value for parameter value t"""
2018
2019         context = _pathcontext()
2020         t=0
2021
2022         for pel in self.path:
2023             if not isinstance(pel, moveto_pt):
2024                 t += 1
2025             pel._updatecontext(context)
2026
2027         return t
2028
2029     def reversed(self):
2030         """return reversed path"""
2031
2032         context = _pathcontext()
2033
2034         # we have to reverse subpath by subpath to get the closepaths right
2035         subpath = []
2036         np = normpath()
2037
2038         # we append a moveto_pt operation at the end to end the last
2039         # subpath explicitely.
2040         for pel in self.path+[moveto_pt(0,0)]:
2041             pelr = pel._reversed(context)
2042             if pelr:
2043                 subpath.append(pelr)
2044
2045             if subpath and isinstance(pel, moveto_pt):
2046                 subpath.append(moveto_pt(*context.currentpoint))
2047                 subpath.reverse()
2048                 np = normpath(*subpath) + np
2049                 subpath = []
2050             elif subpath and isinstance(pel, closepath):
2051                 subpath.append(moveto_pt(*context.currentpoint))
2052                 subpath.reverse()
2053                 subpath.append(closepath())
2054                 np = normpath(*subpath) + np
2055                 subpath = []
2056
2057             pel._updatecontext(context)
2058
2059         return np
2060
2061     def split(self, parameters):
2062         """split path at parameter values parameters
2063
2064         Note that the parameter list has to be sorted.
2065         """
2066
2067         # check whether parameter list is really sorted
2068         sortedparams = list(parameters)
2069         sortedparams.sort()
2070         if sortedparams!=list(parameters):
2071             raise ValueError("split parameters have to be sorted")
2072
2073         context = _pathcontext()
2074         t = 0
2075
2076         # we build up this list of normpaths
2077         result = []
2078
2079         # the currently built up normpath
2080         np = normpath()
2081
2082         for subpath, t0, tf, closed in self._subpaths():
2083             if t0<parameters[0]:
2084                 if tf<parameters[0]:
2085                     # this is trivial, no split has happened
2086                     np.path.extend(subpath)
2087                 else:
2088                     # we have to split this subpath
2089
2090                     # first we determine the relevant splitting
2091                     # parameters
2092                     for i in range(len(parameters)):
2093                         if parameters[i]>tf: break
2094                     else:
2095                         i = len(parameters)
2096
2097                     # the rest we delegate to helper functions
2098                     if closed:
2099                         new = _splitclosedsubpath(subpath,
2100                                                   [x-t0 for x in parameters[:i]])
2101                     else:
2102                         new = _splitopensubpath(subpath,
2103                                                 [x-t0 for x in parameters[:i]])
2104
2105                     np.path.extend(new[0].path)
2106                     result.append(np)
2107                     result.extend(new[1:-1])
2108                     np = new[-1]
2109                     parameters = parameters[i:]
2110
2111         if np:
2112             result.append(np)
2113
2114         return result
2115
2116     def tangent(self, t, length=None):
2117         """return tangent vector of path at parameter value t
2118
2119         Negative values of t count from the end of the path. The absolute
2120         value of t must be smaller or equal to the number of segments in
2121         the normpath, otherwise None is returned.
2122         At discontinuities in the path, the limit from below is returned
2123
2124         if length is not None, the tangent vector will be scaled to
2125         the desired length
2126
2127         """
2128
2129         if t>=0:
2130             p = self.path
2131         else:
2132             p = self.reversed().path
2133
2134         context = _pathcontext()
2135
2136         for pel in p:
2137             if not isinstance(pel, moveto_pt):
2138                 if t>1:
2139                     t -= 1
2140                 else:
2141                     tvec = pel._tangent(context, t)
2142                     tlen = tvec.arclength_pt()
2143                     if length is None or tlen==0:
2144                         return tvec
2145                     else:
2146                         sfactor = unit.topt(length)/tlen
2147                         return tvec.transformed(trafo.scale(sfactor, sfactor, *tvec.begin()))
2148
2149             pel._updatecontext(context)
2150
2151         return None
2152
2153     def transformed(self, trafo):
2154         """return transformed path"""
2155         return normpath(*map(lambda x, trafo=trafo: x.transformed(trafo), self.path))
2156
2157 #
2158 # some special kinds of path, again in two variants
2159 #
2160
2161 # straight lines
2162
2163 class line_pt(normpath):
2164
2165    """straight line from (x1, y1) to (x2, y2) (coordinates in pts)"""
2166
2167    def __init__(self, x1, y1, x2, y2):
2168        normpath.__init__(self, moveto_pt(x1, y1), lineto_pt(x2, y2))
2169
2170
2171 class line(line_pt):
2172
2173    """straight line from (x1, y1) to (x2, y2)"""
2174
2175    def __init__(self, x1, y1, x2, y2):
2176        line_pt.__init__(self,
2177                       unit.topt(x1), unit.topt(y1),
2178                       unit.topt(x2), unit.topt(y2)
2179                       )
2180
2181 # bezier curves
2182
2183 class curve_pt(normpath):
2184
2185    """Bezier curve with control points (x0, y1),..., (x3, y3)
2186    (coordinates in pts)"""
2187
2188    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
2189        normpath.__init__(self,
2190                          moveto_pt(x0, y0),
2191                          curveto_pt(x1, y1, x2, y2, x3, y3))
2192
2193 class curve(curve_pt):
2194
2195    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
2196
2197    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
2198        curve_pt.__init__(self,
2199                        unit.topt(x0), unit.topt(y0),
2200                        unit.topt(x1), unit.topt(y1),
2201                        unit.topt(x2), unit.topt(y2),
2202                        unit.topt(x3), unit.topt(y3)
2203                       )
2204
2205 # rectangles
2206
2207 class rect_pt(normpath):
2208
2209    """rectangle at position (x,y) with width and height (coordinates in pts)"""
2210
2211    def __init__(self, x, y, width, height):
2212        path.__init__(self, moveto_pt(x, y),
2213                            lineto_pt(x+width, y),
2214                            lineto_pt(x+width, y+height),
2215                            lineto_pt(x, y+height),
2216                            closepath())
2217
2218
2219 class rect(rect_pt):
2220
2221    """rectangle at position (x,y) with width and height"""
2222
2223    def __init__(self, x, y, width, height):
2224        rect_pt.__init__(self,
2225                       unit.topt(x), unit.topt(y),
2226                       unit.topt(width), unit.topt(height))
2227
2228 # circles
2229
2230 class circle_pt(path):
2231
2232    """circle with center (x,y) and radius"""
2233
2234    def __init__(self, x, y, radius):
2235        path.__init__(self, arc_pt(x, y, radius, 0, 360),
2236                            closepath())
2237
2238
2239 class circle(circle_pt):
2240
2241    """circle with center (x,y) and radius"""
2242
2243    def __init__(self, x, y, radius):
2244        circle_pt.__init__(self,
2245                         unit.topt(x), unit.topt(y),
2246                         unit.topt(radius))
2247