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