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