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