pyx/path.py

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