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 class curve(curve_pt):
1216
1217    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
1218
1219    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1220        curve_pt.__init__(self,
1221                          unit.topt(x0), unit.topt(y0),
1222                          unit.topt(x1), unit.topt(y1),
1223                          unit.topt(x2), unit.topt(y2),
1224                          unit.topt(x3), unit.topt(y3))
1225
1226
1227 class rect(rect_pt):
1228
1229    """rectangle at position (x,y) with width and height"""
1230
1231    def __init__(self, x, y, width, height):
1232        rect_pt.__init__(self,
1233                         unit.topt(x), unit.topt(y),
1234                         unit.topt(width), unit.topt(height))
1235
1236
1237 class circle(circle_pt):
1238
1239    """circle with center (x,y) and radius"""
1240
1241    def __init__(self, x, y, radius):
1242        circle_pt.__init__(self,
1243                         unit.topt(x), unit.topt(y),
1244                         unit.topt(radius))
1245
1246 ################################################################################
1247 # normpath and corresponding classes
1248 ################################################################################
1249
1250 # two helper functions for the intersection of normpathels
1251
1252 def _intersectnormcurves(a, a_t0, a_t1, b, b_t0, b_t1, epsilon=1e-5):
1253     """intersect two bpathels
1254
1255     a and b are bpathels with parameter ranges [a_t0, a_t1],
1256     respectively [b_t0, b_t1].
1257     epsilon determines when the bpathels are assumed to be straight
1258
1259     """
1260
1261     # intersection of bboxes is a necessary criterium for intersection
1262     if not a.bbox().intersects(b.bbox()): return []
1263
1264     if not a.isstraight(epsilon):
1265         (aa, ab) = a.midpointsplit()
1266         a_tm = 0.5*(a_t0+a_t1)
1267
1268         if not b.isstraight(epsilon):
1269             (ba, bb) = b.midpointsplit()
1270             b_tm = 0.5*(b_t0+b_t1)
1271
1272             return ( _intersectnormcurves(aa, a_t0, a_tm,
1273                                        ba, b_t0, b_tm, epsilon) +
1274                      _intersectnormcurves(ab, a_tm, a_t1,
1275                                        ba, b_t0, b_tm, epsilon) +
1276                      _intersectnormcurves(aa, a_t0, a_tm,
1277                                        bb, b_tm, b_t1, epsilon) +
1278                      _intersectnormcurves(ab, a_tm, a_t1,
1279                                        bb, b_tm, b_t1, epsilon) )
1280         else:
1281             return ( _intersectnormcurves(aa, a_t0, a_tm,
1282                                        b, b_t0, b_t1, epsilon) +
1283                      _intersectnormcurves(ab, a_tm, a_t1,
1284                                        b, b_t0, b_t1, epsilon) )
1285     else:
1286         if not b.isstraight(epsilon):
1287             (ba, bb) = b.midpointsplit()
1288             b_tm = 0.5*(b_t0+b_t1)
1289
1290             return  ( _intersectnormcurves(a, a_t0, a_t1,
1291                                        ba, b_t0, b_tm, epsilon) +
1292                       _intersectnormcurves(a, a_t0, a_t1,
1293                                        bb, b_tm, b_t1, epsilon) )
1294         else:
1295             # no more subdivisions of either a or b
1296             # => try to intersect a and b as straight line segments
1297
1298             a_deltax = a.x3 - a.x0
1299             a_deltay = a.y3 - a.y0
1300             b_deltax = b.x3 - b.x0
1301             b_deltay = b.y3 - b.y0
1302
1303             det = b_deltax*a_deltay - b_deltay*a_deltax
1304
1305             ba_deltax0 = b.x0 - a.x0
1306             ba_deltay0 = b.y0 - a.y0
1307
1308             try:
1309                 a_t = ( b_deltax*ba_deltay0 - b_deltay*ba_deltax0)/det
1310                 b_t = ( a_deltax*ba_deltay0 - a_deltay*ba_deltax0)/det
1311             except ArithmeticError:
1312                 return []
1313
1314             # check for intersections out of bound
1315             if not (0<=a_t<=1 and 0<=b_t<=1): return []
1316
1317             # return rescaled parameters of the intersection
1318             return [ ( a_t0 + a_t * (a_t1 - a_t0),
1319                        b_t0 + b_t * (b_t1 - b_t0) ) ]
1320
1321
1322 def _intersectnormlines(a, b):
1323     """return one-element list constisting either of tuple of
1324     parameters of the intersection point of the two normlines a and b
1325     or empty list if both normlines do not intersect each other"""
1326
1327     a_deltax = a.x1 - a.x0
1328     a_deltay = a.y1 - a.y0
1329     b_deltax = b.x1 - b.x0
1330     b_deltay = b.y1 - b.y0
1331
1332     det = b_deltax*a_deltay - b_deltay*a_deltax
1333
1334     ba_deltax0 = b.x0 - a.x0
1335     ba_deltay0 = b.y0 - a.y0
1336
1337     try:
1338         a_t = ( b_deltax*ba_deltay0 - b_deltay*ba_deltax0)/det
1339         b_t = ( a_deltax*ba_deltay0 - a_deltay*ba_deltax0)/det
1340     except ArithmeticError:
1341         return []
1342
1343     # check for intersections out of bound
1344     if not (0<=a_t<=1 and 0<=b_t<=1): return []
1345
1346     # return parameters of the intersection
1347     return [( a_t, b_t)]
1348
1349
1350
1351
1352 #
1353 # normpathel: normalized element
1354 #
1355
1356 class normpathel:
1357
1358     """element of a normalized sub path"""
1359
1360     def at_pt(self, t):
1361         """returns coordinates of point in pts at parameter t (0<=t<=1) """
1362         pass
1363
1364     def arclen_pt(self, epsilon=1e-5):
1365         """returns arc length of normpathel in pts with given accuracy epsilon"""
1366         pass
1367
1368     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1369         """returns tuple (t,l) with
1370           t the parameter where the arclen of normpathel is length and
1371           l the total arclen
1372
1373         length:  length (in pts) to find the parameter for
1374         epsilon: epsilon controls the accuracy for calculation of the
1375                  length of the Bezier elements
1376         """
1377         # Note: _arclentoparam returns both, parameters and total lengths
1378         # while  arclentoparam returns only parameters
1379         pass
1380
1381     def bbox(self):
1382         """return bounding box of normpathel"""
1383         pass
1384
1385     def curvradius_pt(self, param):
1386         """Returns the curvature radius in pts at parameter param.
1387         This is the inverse of the curvature at this parameter
1388
1389         Please note that this radius can be negative or positive,
1390         depending on the sign of the curvature"""
1391         pass
1392
1393     def intersect(self, other, epsilon=1e-5):
1394         """intersect self with other normpathel"""
1395         pass
1396
1397     def reversed(self):
1398         """return reversed normpathel"""
1399         pass
1400
1401     def split(self, parameters):
1402         """splits normpathel
1403
1404         parameters: list of parameter values (0<=t<=1) at which to split
1405
1406         returns None or list of tuple of normpathels corresponding to
1407         the orginal normpathel.
1408
1409         """
1410
1411         pass
1412
1413     def tangentvector_pt(self, t):
1414         """returns tangent vector of normpathel in pts at parameter t (0<=t<=1)"""
1415         pass
1416
1417     def transformed(self, trafo):
1418         """return transformed normpathel according to trafo"""
1419         pass
1420
1421     def outputPS(self, file):
1422         """write PS code corresponding to normpathel to file"""
1423         pass
1424
1425     def outputPS(self, file):
1426         """write PDF code corresponding to normpathel to file"""
1427         pass
1428
1429 #
1430 # there are only two normpathels: normline and normcurve
1431 #
1432
1433 class normline(normpathel):
1434
1435     """Straight line from (x0, y0) to (x1, y1) (coordinates in pts)"""
1436
1437     __slots__ = "x0", "y0", "x1", "y1"
1438
1439     def __init__(self, x0, y0, x1, y1):
1440          self.x0 = x0
1441          self.y0 = y0
1442          self.x1 = x1
1443          self.y1 = y1
1444
1445     def __str__(self):
1446         return "normline(%g, %g, %g, %g)" % (self.x0, self.y0, self.x1, self.y1)
1447
1448     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1449         l = self.arclen_pt(epsilon)
1450         return ([max(min(1.0 * length / l, 1), 0) for length in lengths], l)
1451
1452     def _normcurve(self):
1453         """ return self as equivalent normcurve """
1454         xa = self.x0+(self.x1-self.x0)/3.0
1455         ya = self.y0+(self.y1-self.y0)/3.0
1456         xb = self.x0+2.0*(self.x1-self.x0)/3.0
1457         yb = self.y0+2.0*(self.y1-self.y0)/3.0
1458         return normcurve(self.x0, self.y0, xa, ya, xb, yb, self.x1, self.y1)
1459
1460     def arclen_pt(self,  epsilon=1e-5):
1461         return math.hypot(self.x0-self.x1, self.y0-self.y1)
1462
1463     def at_pt(self, t):
1464         return (self.x0+(self.x1-self.x0)*t, self.y0+(self.y1-self.y0)*t)
1465
1466     def bbox(self):
1467         return bbox._bbox(min(self.x0, self.x1), min(self.y0, self.y1),
1468                           max(self.x0, self.x1), max(self.y0, self.y1))
1469
1470     def begin_pt(self):
1471         return self.x0, self.y0
1472
1473     def curvradius_pt(self, param):
1474         return None
1475
1476     def end_pt(self):
1477         return self.x1, self.y1
1478
1479     def intersect(self, other, epsilon=1e-5):
1480         if isinstance(other, normline):
1481             return _intersectnormlines(self, other)
1482         else:
1483             return  _intersectnormcurves(self._normcurve(), 0, 1, other, 0, 1, epsilon)
1484
1485     def isstraight(self, epsilon):
1486         return 1
1487
1488     def reverse(self):
1489         self.x0, self.y0, self.x1, self.y1 = self.x1, self.y1, self.x0, self.y0
1490
1491     def reversed(self):
1492         return normline(self.x1, self.y1, self.x0, self.y0)
1493
1494     def split(self, parameters):
1495         x0, y0 = self.x0, self.y0
1496         x1, y1 = self.x1, self.y1
1497         if parameters:
1498             xl, yl = x0, y0
1499             result = []
1500
1501             if parameters[0] == 0:
1502                 result.append(None)
1503                 parameters = parameters[1:]
1504
1505             if parameters:
1506                 for t in parameters:
1507                     xs, ys = x0 + (x1-x0)*t, y0 + (y1-y0)*t
1508                     result.append(normline(xl, yl, xs, ys))
1509                     xl, yl = xs, ys
1510
1511                 if parameters[-1]!=1:
1512                     result.append(normline(xs, ys, x1, y1))
1513                 else:
1514                     result.append(None)
1515             else:
1516                 result.append(normline(x0, y0, x1, y1))
1517         else:
1518             result = []
1519         return result
1520
1521     def tangentvector_pt(self, t):
1522         return (self.x1-self.x0, self.y1-self.y0)
1523
1524     def transformed(self, trafo):
1525         return normline(*(trafo._apply(self.x0, self.y0) + trafo._apply(self.x1, self.y1)))
1526
1527     def outputPS(self, file):
1528         file.write("%g %g lineto\n" % (self.x1, self.y1))
1529
1530     def outputPDF(self, file):
1531         file.write("%f %f l\n" % (self.x1, self.y1))
1532
1533
1534 class normcurve(normpathel):
1535
1536     """Bezier curve with control points x0, y0, x1, y1, x2, y2, x3, y3 (coordinates in pts)"""
1537
1538     __slots__ = "x0", "y0", "x1", "y1", "x2", "y2", "x3", "y3"
1539
1540     def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1541         self.x0 = x0
1542         self.y0 = y0
1543         self.x1 = x1
1544         self.y1 = y1
1545         self.x2 = x2
1546         self.y2 = y2
1547         self.x3 = x3
1548         self.y3 = y3
1549
1550     def __str__(self):
1551         return "normcurve(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0, self.y0, self.x1, self.y1,
1552                                                               self.x2, self.y2, self.x3, self.y3)
1553
1554     def _arclentoparam_pt(self, lengths, epsilon=1e-5):
1555         """computes the parameters [t] of bpathel where the given lengths (in pts) are assumed
1556         returns ( [parameters], total arclen)
1557         A negative length gives a parameter 0"""
1558
1559         # create the list of accumulated lengths
1560         # and the length of the parameters
1561         seg = self.seglengths(1, epsilon)
1562         arclens = [seg[i][0] for i in range(len(seg))]
1563         Dparams = [seg[i][1] for i in range(len(seg))]
1564         l = len(arclens)
1565         for i in range(1,l):
1566             arclens[i] += arclens[i-1]
1567
1568         # create the list of parameters to be returned
1569         params = []
1570         for length in lengths:
1571             # find the last index that is smaller than length
1572             try:
1573                 lindex = bisect.bisect_left(arclens, length)
1574             except: # workaround for python 2.0
1575                 lindex = bisect.bisect(arclens, length)
1576                 while lindex and (lindex >= len(arclens) or
1577                                   arclens[lindex] >= length):
1578                     lindex -= 1
1579             if lindex == 0:
1580                 param = Dparams[0] * length * 1.0 / arclens[0]
1581             elif lindex < l-1:
1582                 param = Dparams[lindex+1] * (length - arclens[lindex]) * 1.0 / (arclens[lindex+1] - arclens[lindex])
1583                 for i in range(lindex+1):
1584                     param += Dparams[i]
1585             else:
1586                 param = 1 + Dparams[-1] * (length - arclens[-1]) * 1.0 / (arclens[-1] - arclens[-2])
1587
1588             param = max(min(param,1),0)
1589             params.append(param)
1590         return (params, arclens[-1])
1591
1592     def arclen_pt(self, epsilon=1e-5):
1593         """computes arclen of bpathel in pts using successive midpoint split"""
1594         if self.isstraight(epsilon):
1595             return math.hypot(self.x3-self.x0, self.y3-self.y0)
1596         else:
1597             (a, b) = self.midpointsplit()
1598             return a.arclen_pt(epsilon) + b.arclen_pt(epsilon)
1599
1600
1601     def at_pt(self, t):
1602         xt = (  (-self.x0+3*self.x1-3*self.x2+self.x3)*t*t*t +
1603                (3*self.x0-6*self.x1+3*self.x2        )*t*t +
1604               (-3*self.x0+3*self.x1                  )*t +
1605               self.x0)
1606         yt = (  (-self.y0+3*self.y1-3*self.y2+self.y3)*t*t*t +
1607                (3*self.y0-6*self.y1+3*self.y2        )*t*t +
1608               (-3*self.y0+3*self.y1                  )*t +
1609               self.y0)
1610         return (xt, yt)
1611
1612     def bbox(self):
1613         return bbox._bbox(min(self.x0, self.x1, self.x2, self.x3),
1614                           min(self.y0, self.y1, self.y2, self.y3),
1615                           max(self.x0, self.x1, self.x2, self.x3),
1616                           max(self.y0, self.y1, self.y2, self.y3))
1617
1618     def begin_pt(self):
1619         return self.x0, self.y0
1620
1621     def curvradius_pt(self, param):
1622         xdot = 3 * (1-param)*(1-param) * (-self.x0 + self.x1) \
1623              + 6 * (1-param)*param * (-self.x1 + self.x2) \
1624              + 3 * param*param * (-self.x2 + self.x3)
1625         ydot = 3 * (1-param)*(1-param) * (-self.y0 + self.y1) \
1626              + 6 * (1-param)*param * (-self.y1 + self.y2) \
1627              + 3 * param*param * (-self.y2 + self.y3)
1628         xddot = 6 * (1-param) * (self.x0 - 2*self.x1 + self.x2) \
1629               + 6 * param * (self.x1 - 2*self.x2 + self.x3)
1630         yddot = 6 * (1-param) * (self.y0 - 2*self.y1 + self.y2) \
1631               + 6 * param * (self.y1 - 2*self.y2 + self.y3)
1632         return (xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot)
1633
1634     def end_pt(self):
1635         return self.x3, self.y3
1636
1637     def intersect(self, other, epsilon=1e-5):
1638         if isinstance(other, normline):
1639             return  _intersectnormcurves(self, 0, 1, other._normcurve(), 0, 1, epsilon)
1640         else:
1641             return  _intersectnormcurves(self, 0, 1, other, 0, 1, epsilon)
1642
1643     def isstraight(self, epsilon=1e-5):
1644         """check wheter the normcurve is approximately straight"""
1645
1646         # just check, whether the modulus of the difference between
1647         # the length of the control polygon
1648         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1649         # straight line between starting and ending point of the
1650         # normcurve (i.e. |P3-P1|) is smaller the epsilon
1651         return abs(math.hypot(self.x1-self.x0, self.y1-self.y0)+
1652                    math.hypot(self.x2-self.x1, self.y2-self.y1)+
1653                    math.hypot(self.x3-self.x2, self.y3-self.y2)-
1654                    math.hypot(self.x3-self.x0, self.y3-self.y0))<epsilon
1655
1656     def midpointsplit(self):
1657         """splits bpathel at midpoint returning bpath with two bpathels"""
1658
1659         # for efficiency reason, we do not use self.split(0.5)!
1660
1661         # first, we have to calculate the  midpoints between adjacent
1662         # control points
1663         x01 = 0.5*(self.x0+self.x1)
1664         y01 = 0.5*(self.y0+self.y1)
1665         x12 = 0.5*(self.x1+self.x2)
1666         y12 = 0.5*(self.y1+self.y2)
1667         x23 = 0.5*(self.x2+self.x3)
1668         y23 = 0.5*(self.y2+self.y3)
1669
1670         # In the next iterative step, we need the midpoints between 01 and 12
1671         # and between 12 and 23
1672         x01_12 = 0.5*(x01+x12)
1673         y01_12 = 0.5*(y01+y12)
1674         x12_23 = 0.5*(x12+x23)
1675         y12_23 = 0.5*(y12+y23)
1676
1677         # Finally the midpoint is given by
1678         xmidpoint = 0.5*(x01_12+x12_23)
1679         ymidpoint = 0.5*(y01_12+y12_23)
1680
1681         return (normcurve(self.x0, self.y0,
1682                           x01, y01,
1683                           x01_12, y01_12,
1684                           xmidpoint, ymidpoint),
1685                 normcurve(xmidpoint, ymidpoint,
1686                           x12_23, y12_23,
1687                           x23, y23,
1688                           self.x3, self.y3))
1689
1690     def reverse(self):
1691         self.x0, self.y0, self.x1, self.y1, self.x2, self.y2, self.x3, self.y3 = \
1692         self.x3, self.y3, self.x2, self.y2, self.x1, self.y1, self.x0, self.y0
1693
1694     def reversed(self):
1695         return normcurve(self.x3, self.y3, self.x2, self.y2, self.x1, self.y1, self.x0, self.y0)
1696
1697     def seglengths(self, paraminterval, epsilon=1e-5):
1698         """returns the list of segment line lengths (in pts) of the normcurve
1699            together with the length of the parameterinterval"""
1700
1701         # lower and upper bounds for the arclen
1702         lowerlen = math.hypot(self.x3-self.x0, self.y3-self.y0)
1703         upperlen = ( math.hypot(self.x1-self.x0, self.y1-self.y0) +
1704                      math.hypot(self.x2-self.x1, self.y2-self.y1) +
1705                      math.hypot(self.x3-self.x2, self.y3-self.y2) )
1706
1707         # instead of isstraight method:
1708         if abs(upperlen-lowerlen)<epsilon:
1709             return [( 0.5*(upperlen+lowerlen), paraminterval )]
1710         else:
1711             (a, b) = self.midpointsplit()
1712             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
1713
1714     def _split(self, parameters):
1715         """return list of normcurve corresponding to split at parameters"""
1716
1717         # first, we calculate the coefficients corresponding to our
1718         # original bezier curve. These represent a useful starting
1719         # point for the following change of the polynomial parameter
1720         a0x = self.x0
1721         a0y = self.y0
1722         a1x = 3*(-self.x0+self.x1)
1723         a1y = 3*(-self.y0+self.y1)
1724         a2x = 3*(self.x0-2*self.x1+self.x2)
1725         a2y = 3*(self.y0-2*self.y1+self.y2)
1726         a3x = -self.x0+3*(self.x1-self.x2)+self.x3
1727         a3y = -self.y0+3*(self.y1-self.y2)+self.y3
1728
1729         if parameters[0]!=0:
1730             parameters = [0] + parameters
1731         if parameters[-1]!=1:
1732             parameters = parameters + [1]
1733
1734         result = []
1735
1736         for i in range(len(parameters)-1):
1737             t1 = parameters[i]
1738             dt = parameters[i+1]-t1
1739
1740             # [t1,t2] part
1741             #
1742             # the new coefficients of the [t1,t1+dt] part of the bezier curve
1743             # are then given by expanding
1744             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
1745             #  a3*(t1+dt*u)**3 in u, yielding
1746             #
1747             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
1748             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
1749             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
1750             #   a3*dt**3                         * u**3
1751             #
1752             # from this values we obtain the new control points by inversion
1753             #
1754             # XXX: we could do this more efficiently by reusing for
1755             # (x0, y0) the control point (x3, y3) from the previous
1756             # Bezier curve
1757
1758             x0 = a0x + a1x*t1 + a2x*t1*t1 + a3x*t1*t1*t1
1759             y0 = a0y + a1y*t1 + a2y*t1*t1 + a3y*t1*t1*t1
1760             x1 = (a1x+2*a2x*t1+3*a3x*t1*t1)*dt/3.0 + x0
1761             y1 = (a1y+2*a2y*t1+3*a3y*t1*t1)*dt/3.0 + y0
1762             x2 = (a2x+3*a3x*t1)*dt*dt/3.0 - x0 + 2*x1
1763             y2 = (a2y+3*a3y*t1)*dt*dt/3.0 - y0 + 2*y1
1764             x3 = a3x*dt*dt*dt + x0 - 3*x1 + 3*x2
1765             y3 = a3y*dt*dt*dt + y0 - 3*y1 + 3*y2
1766
1767             result.append(normcurve(x0, y0, x1, y1, x2, y2, x3, y3))
1768
1769         return result
1770
1771     def split(self, parameters):
1772         if parameters:
1773             # we need to split
1774             bps = self._split(list(parameters))
1775
1776             if parameters[0]==0:
1777                 result = [None]
1778             else:
1779                 bp0 = bps[0]
1780                 result = [normcurve(self.x0, self.y0, bp0.x1, bp0.y1, bp0.x2, bp0.y2, bp0.x3, bp0.y3)]
1781                 bps = bps[1:]
1782
1783             for bp in bps:
1784                 result.append(normcurve(bp.x0, bp.y0, bp.x1, bp.y1, bp.x2, bp.y2, bp.x3, bp.y3))
1785
1786             if parameters[-1]==1:
1787                 result.append(None)
1788         else:
1789             result = []
1790         return result
1791
1792     def tangentvector_pt(self, t):
1793         tvectx = (3*(  -self.x0+3*self.x1-3*self.x2+self.x3)*t*t +
1794                   2*( 3*self.x0-6*self.x1+3*self.x2        )*t +
1795                     (-3*self.x0+3*self.x1                  ))
1796         tvecty = (3*(  -self.y0+3*self.y1-3*self.y2+self.y3)*t*t +
1797                   2*( 3*self.y0-6*self.y1+3*self.y2        )*t +
1798                     (-3*self.y0+3*self.y1                  ))
1799         return (tvectx, tvecty)
1800
1801     def transform(self, trafo):
1802         self.x0, self.y0 = trafo._apply(self.x0, self.y0)
1803         self.x1, self.y1 = trafo._apply(self.x1, self.y1)
1804         self.x2, self.y2 = trafo._apply(self.x2, self.y2)
1805         self.x3, self.y3 = trafo._apply(self.x3, self.y3)
1806
1807     def transformed(self, trafo):
1808         return normcurve(*(trafo._apply(self.x0, self.y0)+
1809                            trafo._apply(self.x1, self.y1)+
1810                            trafo._apply(self.x2, self.y2)+
1811                            trafo._apply(self.x3, self.y3)))
1812
1813     def outputPS(self, file):
1814         file.write("%g %g %g %g %g %g curveto\n" % (self.x1, self.y1, self.x2, self.y2, self.x3, self.y3))
1815
1816     def outputPDF(self, file):
1817         file.write("%f %f %f %f %f %f c\n" % (self.x1, self.y1, self.x2, self.y2, self.x3, self.y3))
1818
1819 #
1820 # normpaths are made up of normsubpaths, which represent connected line segments
1821 #
1822
1823 class normsubpath:
1824
1825     """sub path of a normalized path
1826
1827     A subpath consists of a list of normpathels, i.e., lines and bcurves
1828     and can either be closed or not.
1829
1830     Some invariants, which have to be obeyed:
1831     - All normpathels have to be longer than epsilon pts.
1832     - The last point of a normpathel and the first point of the next
1833     element have to be equal.
1834     - When the path is closed, the last normpathel has to be a
1835     normline and the last point of this normline has to be equal
1836     to the first point of the first normpathel, except when
1837     this normline would be too short.
1838     """
1839
1840     __slots__ = "normpathels", "closed", "epsilon"
1841
1842     def __init__(self, normpathels, closed, epsilon=1e-5):
1843         self.normpathels = [npel for npel in normpathels if not npel.isstraight(epsilon) or npel.arclen_pt(epsilon)>epsilon]
1844         self.closed = closed
1845         self.epsilon = epsilon
1846
1847     def __str__(self):
1848         return "subpath(%s, [%s])" % (self.closed and "closed" or "open",
1849                                     ", ".join(map(str, self.normpathels)))
1850
1851     def arclen_pt(self):
1852         """returns total arc length of normsubpath in pts with accuracy epsilon"""
1853         return sum([npel.arclen_pt(self.epsilon) for npel in self.normpathels])
1854
1855     def _arclentoparam_pt(self, lengths):
1856         """returns [t, l] where t are parameter value(s) matching given length(s)
1857         and l is the total length of the normsubpath
1858         The parameters are with respect to the normsubpath: t in [0, self.range()]
1859         lengths that are < 0 give parameter 0"""
1860
1861         allarclen = 0
1862         allparams = [0] * len(lengths)
1863         rests = copy.copy(lengths)
1864
1865         for pel in self.normpathels:
1866             params, arclen = pel._arclentoparam_pt(rests, self.epsilon)
1867             allarclen += arclen
1868             for i in range(len(rests)):
1869                 if rests[i] >= 0:
1870                     rests[i] -= arclen
1871                     allparams[i] += params[i]
1872
1873         return (allparams, allarclen)
1874
1875     def at_pt(self, param):
1876         """return coordinates in pts of sub path at parameter value param
1877
1878         The parameter param must be smaller or equal to the number of
1879         segments in the normpath, otherwise None is returned.
1880         """
1881         try:
1882             return self.normpathels[int(param-self.epsilon)].at_pt(param-int(param-self.epsilon))
1883         except:
1884             raise PathException("parameter value param out of range")
1885
1886     def bbox(self):
1887         if self.normpathels:
1888             abbox = self.normpathels[0].bbox()
1889             for anormpathel in self.normpathels[1:]:
1890                 abbox += anormpathel.bbox()
1891             return abbox
1892         else:
1893             return None
1894
1895     def begin_pt(self):
1896         return self.normpathels[0].begin_pt()
1897
1898     def curvradius_pt(self, param):
1899         try:
1900             return self.normpathels[int(param-self.epsilon)].curvradius_pt(param-int(param-self.epsilon))
1901         except:
1902             raise PathException("parameter value param out of range")
1903
1904     def end_pt(self):
1905         return self.normpathels[-1].end_pt()
1906
1907     def intersect(self, other):
1908         """intersect self with other normsubpath
1909
1910         returns a tuple of lists consisting of the parameter values
1911         of the intersection points of the corresponding normsubpath
1912
1913         """
1914         intersections = ([], [])
1915         epsilon = min(self.epsilon, other.epsilon)
1916         # Intersect all subpaths of self with the subpaths of other
1917         for t_a, pel_a  in enumerate(self.normpathels):
1918             for t_b, pel_b in enumerate(other.normpathels):
1919                 for intersection in pel_a.intersect(pel_b, epsilon):
1920                     # check whether an intersection occurs at the end
1921                     # of a closed subpath. If yes, we don't include it
1922                     # in the list of intersections to prevent a
1923                     # duplication of intersection points
1924                     if not ((self.closed and self.range()-intersection[0]-t_a<epsilon) or
1925                             (other.closed and other.range()-intersection[1]-t_b<epsilon)):
1926                         intersections[0].append(intersection[0]+t_a)
1927                         intersections[1].append(intersection[1]+t_b)
1928         return intersections
1929
1930     def range(self):
1931         """return maximal parameter value, i.e. number of line/curve segments"""
1932         return len(self.normpathels)
1933
1934     def reverse(self):
1935         self.normpathels.reverse()
1936         for npel in self.normpathels:
1937             npel.reverse()
1938
1939     def reversed(self):
1940         nnormpathels = []
1941         for i in range(len(self.normpathels)):
1942             nnormpathels.append(self.normpathels[-(i+1)].reversed())
1943         return normsubpath(nnormpathels, self.closed)
1944
1945     def split(self, params):
1946         """split normsubpath at list of parameter values params and return list
1947         of normsubpaths
1948
1949         The parameter list params has to be sorted. Note that each element of
1950         the resulting list is an open normsubpath.
1951         """
1952
1953         if min(params) < -self.epsilon or max(params) > self.range()+self.epsilon:
1954             raise PathException("parameter for split of subpath out of range")
1955
1956         result = []
1957         npels = None
1958         for t, pel in enumerate(self.normpathels):
1959             # determine list of splitting parameters relevant for pel
1960             nparams = []
1961             for nt in params:
1962                 if t+1 >= nt:
1963                     nparams.append(nt-t)
1964                     params = params[1:]
1965
1966             # now we split the path at the filtered parameter values
1967             # This yields a list of normpathels and possibly empty
1968             # segments marked by None
1969             splitresult = pel.split(nparams)
1970             if splitresult:
1971                 # first split?
1972                 if npels is None:
1973                     if splitresult[0] is None:
1974                         # mark split at the beginning of the normsubpath
1975                         result = [None]
1976                     else:
1977                         result.append(normsubpath([splitresult[0]], 0))
1978                 else:
1979                     npels.append(splitresult[0])
1980                     result.append(normsubpath(npels, 0))
1981                 for npel in splitresult[1:-1]:
1982                     result.append(normsubpath([npel], 0))
1983                 if len(splitresult)>1 and splitresult[-1] is not None:
1984                     npels = [splitresult[-1]]
1985                 else:
1986                     npels = []
1987             else:
1988                 if npels is None:
1989                     npels = [pel]
1990                 else:
1991                     npels.append(pel)
1992
1993         if npels:
1994             result.append(normsubpath(npels, 0))
1995         else:
1996             # mark split at the end of the normsubpath
1997             result.append(None)
1998
1999         # join last and first segment together if the normsubpath was originally closed
2000         if self.closed:
2001             if result[0] is None:
2002                 result = result[1:]
2003             elif result[-1] is None:
2004                 result = result[:-1]
2005             else:
2006                 result[-1].normpathels.extend(result[0].normpathels)
2007                 result = result[1:]
2008         return result
2009
2010     def tangent(self, param, length=None):
2011         tx, ty = self.at_pt(param)
2012         try:
2013             tdx, tdy = self.normpathels[int(param-self.epsilon)].tangentvector_pt(param-int(param-self.epsilon))
2014         except:
2015             raise PathException("parameter value param out of range")
2016         tlen = math.hypot(tdx, tdy)
2017         if not (length is None or tlen==0):
2018             sfactor = unit.topt(length)/tlen
2019             tdx *= sfactor
2020             tdy *= sfactor
2021         return line_pt(tx, ty, tx+tdx, ty+tdy)
2022
2023     def trafo(self, param):
2024         tx, ty = self.at_pt(param)
2025         try:
2026             tdx, tdy = self.normpathels[int(param-self.epsilon)].tangentvector_pt(param-int(param-self.epsilon))
2027         except:
2028             raise PathException("parameter value param out of range")
2029         return trafo.translate_pt(tx, ty)*trafo.rotate(degrees(math.atan2(tdy, tdx)))
2030
2031     def transform(self, trafo):
2032         """transform sub path according to trafo"""
2033         for pel in self.normpathels:
2034             pel.transform(trafo)
2035
2036     def transformed(self, trafo):
2037         """return sub path transformed according to trafo"""
2038         nnormpathels = []
2039         for pel in self.normpathels:
2040             nnormpathels.append(pel.transformed(trafo))
2041         return normsubpath(nnormpathels, self.closed)
2042
2043     def outputPS(self, file):
2044         # if the normsubpath is closed, we must not output a normline at
2045         # the end
2046         if not self.normpathels:
2047             return
2048         if self.closed and isinstance(self.normpathels[-1], normline):
2049             normpathels = self.normpathels[:-1]
2050         else:
2051             normpathels = self.normpathels
2052         if normpathels:
2053             file.write("%g %g moveto\n" % self.begin_pt())
2054             for anormpathel in normpathels:
2055                 anormpathel.outputPS(file)
2056         if self.closed:
2057             file.write("closepath\n")
2058
2059     def outputPDF(self, file):
2060         # if the normsubpath is closed, we must not output a normline at
2061         # the end
2062         if not self.normpathels:
2063             return
2064         if self.closed and isinstance(self.normpathels[-1], normline):
2065             normpathels = self.normpathels[:-1]
2066         else:
2067             normpathels = self.normpathels
2068         if normpathels:
2069             file.write("%f %f m\n" % self.begin_pt())
2070             for anormpathel in normpathels:
2071                 anormpathel.outputPDF(file)
2072         if self.closed:
2073             file.write("h\n")
2074
2075 #
2076 # the normpath class
2077 #
2078
2079 class normpath(path):
2080
2081     """normalized path
2082
2083     A normalized path consists of a list of normalized sub paths.
2084
2085     """
2086
2087     def __init__(self, arg=[], epsilon=1e-5):
2088         """ construct a normpath from another normpath passed as arg,
2089         a path or a list of normsubpaths. An accuracy of epsilon pts
2090         is used for numerical calculations.
2091         """
2092
2093         self.epsilon = epsilon
2094         if isinstance(arg, normpath):
2095             self.subpaths = copy.copy(arg.subpaths)
2096             return
2097         elif isinstance(arg, path):
2098             # split path in sub paths
2099             self.subpaths = []
2100             currentsubpathels = []
2101             context = _pathcontext()
2102             for pel in arg.path:
2103                 for npel in pel._normalized(context):
2104                     if isinstance(npel, moveto_pt):
2105                         if currentsubpathels:
2106                             # append open sub path
2107                             self.subpaths.append(normsubpath(currentsubpathels, 0, epsilon))
2108                         # start new sub path
2109                         currentsubpathels = []
2110                     elif isinstance(npel, closepath):
2111                         if currentsubpathels:
2112                             # append closed sub path
2113                             currentsubpathels.append(normline(context.currentpoint[0], context.currentpoint[1],
2114                                                               context.currentsubpath[0], context.currentsubpath[1]))
2115                         self.subpaths.append(normsubpath(currentsubpathels, 1, epsilon))
2116                         currentsubpathels = []
2117                     else:
2118                         currentsubpathels.append(npel)
2119                 pel._updatecontext(context)
2120
2121             if currentsubpathels:
2122                 # append open sub path
2123                 self.subpaths.append(normsubpath(currentsubpathels, 0, epsilon))
2124         else:
2125             # we expect a list of normsubpaths
2126             self.subpaths = list(arg)
2127
2128     def __add__(self, other):
2129         result = normpath(other)
2130         result.subpaths = self.subpaths + result.subpaths
2131         return result
2132
2133     def __iadd__(self, other):
2134         self.subpaths += normpath(other).subpaths
2135         return self
2136
2137     def __nonzero__(self):
2138         return len(self.subpaths)>0
2139
2140     def __str__(self):
2141         return "normpath(%s)" % ", ".join(map(str, self.subpaths))
2142
2143     def _findsubpath(self, param, arclen):
2144         """return a tuple (subpath, rparam), where subpath is the subpath
2145         containing the position specified by either param or arclen and rparam
2146         is the corresponding parameter value in this subpath.
2147         """
2148
2149         if param is not None and arclen is not None:
2150             raise PathException("either param or arclen has to be specified, but not both")
2151         elif arclen is not None:
2152             param = self.arclentoparam(arclen)
2153
2154         spt = 0
2155         for sp in self.subpaths:
2156             sprange = sp.range()
2157             if spt <= param <= sprange+spt+self.epsilon:
2158                 return sp, param-spt
2159             spt += sprange
2160         raise PathException("parameter value out of range")
2161
2162     def append(self, pathel):
2163         # XXX factor parts of this code out
2164         if self.subpaths[-1].closed:
2165             context = _pathcontext(self.end_pt(), None)
2166             currentsubpathels = []
2167         else:
2168             context = _pathcontext(self.end_pt(), self.subpaths[-1].begin_pt())
2169             currentsubpathels = self.subpaths[-1].normpathels
2170             self.subpaths = self.subpaths[:-1]
2171         for npel in pathel._normalized(context):
2172             if isinstance(npel, moveto_pt):
2173                 if currentsubpathels:
2174                     # append open sub path
2175                     self.subpaths.append(normsubpath(currentsubpathels, 0, self.epsilon))
2176                 # start new sub path
2177                 currentsubpathels = []
2178             elif isinstance(npel, closepath):
2179                 if currentsubpathels:
2180                     # append closed sub path
2181                     currentsubpathels.append(normline(context.currentpoint[0], context.currentpoint[1],
2182                                                       context.currentsubpath[0], context.currentsubpath[1]))
2183                     self.subpaths.append(normsubpath(currentsubpathels, 1, self.epsilon))
2184                 currentsubpathels = []
2185             else:
2186                 currentsubpathels.append(npel)
2187
2188         if currentsubpathels:
2189             # append open sub path
2190             self.subpaths.append(normsubpath(currentsubpathels, 0, self.epsilon))
2191
2192     def arclen_pt(self):
2193         """returns total arc length of normpath in pts"""
2194         return sum([sp.arclen_pt() for sp in self.subpaths])
2195
2196     def arclen(self):
2197         """returns total arc length of normpath"""
2198         return unit.t_pt(self.arclen_pt())
2199
2200     def arclentoparam_pt(self, lengths):
2201         rests = copy.copy(lengths)
2202         allparams = [0] * len(lengths)
2203
2204         for sp in self.subpaths:
2205             # we need arclen for knowing when all the parameters are done
2206             # for lengths that are done: rests[i] is negative
2207             # sp._arclentoparam has to ignore such lengths
2208             params, arclen = sp._arclentoparam_pt(rests)
2209             finis = 0 # number of lengths that are done
2210             for i in range(len(rests)):
2211                 if rests[i] >= 0:
2212                   rests[i] -= arclen
2213                   allparams[i] += params[i]
2214                 else:
2215                     finis += 1
2216             if finis == len(rests): break
2217
2218         if len(lengths) == 1: allparams = allparams[0]
2219         return allparams
2220
2221     def arclentoparam(self, lengths):
2222         """returns the parameter value(s) matching the given length(s)
2223
2224         all given lengths must be positive.
2225         A length greater than the total arclength will give self.range()
2226         """
2227         l = [unit.topt(length) for length in helper.ensuresequence(lengths)]
2228         return self.arclentoparam_pt(l)
2229
2230     def at_pt(self, param=None, arclen=None):
2231         """return coordinates in pts of path at either parameter value param
2232         or arc length arclen.
2233
2234         At discontinuities in the path, the limit from below is returned.
2235         """
2236         sp, param = self._findsubpath(param, arclen)
2237         return sp.at_pt(param)
2238
2239     def at(self, param=None, arclen=None):
2240         """return coordinates of path at either parameter value param
2241         or arc length arclen.
2242
2243         At discontinuities in the path, the limit from below is returned
2244         """
2245         x, y = self.at_pt(param, arclen)
2246         return unit.t_pt(x), unit.t_pt(y)
2247
2248     def bbox(self):
2249         abbox = None
2250         for sp in self.subpaths:
2251             nbbox =  sp.bbox()
2252             if abbox is None:
2253                 abbox = nbbox
2254             elif nbbox:
2255                 abbox += nbbox
2256         return abbox
2257
2258     def begin_pt(self):
2259         """return coordinates of first point of first subpath in path (in pts)"""
2260         if self.subpaths:
2261             return self.subpaths[0].begin_pt()
2262         else:
2263             raise PathException("cannot return first point of empty path")
2264
2265     def begin(self):
2266         """return coordinates of first point of first subpath in path"""
2267         x, y = self.begin_pt()
2268         return unit.t_pt(x), unit.t_pt(y)
2269
2270     def curvradius_pt(self, param=None, arclen=None):
2271         """Returns the curvature radius in pts (or None if infinite)
2272         at parameter param or arc length arclen.  This is the inverse
2273         of the curvature at this parameter
2274
2275         Please note that this radius can be negative or positive,
2276         depending on the sign of the curvature"""
2277         sp, param = self._findsubpath(param, arclen)
2278         return sp.curvradius_pt(param)
2279
2280     def curvradius(self, param=None, arclen=None):
2281         """Returns the curvature radius (or None if infinite) at
2282         parameter param or arc length arclen.  This is the inverse of
2283         the curvature at this parameter
2284
2285         Please note that this radius can be negative or positive,
2286         depending on the sign of the curvature"""
2287         radius = self.curvradius_pt(param, arclen)
2288         if radius is not None:
2289             radius = unit.t_pt(radius)
2290         return radius
2291
2292     def end_pt(self):
2293         """return coordinates of last point of last subpath in path (in pts)"""
2294         if self.subpaths:
2295             return self.subpaths[-1].end_pt()
2296         else:
2297             raise PathException("cannot return last point of empty path")
2298
2299     def end(self):
2300         """return coordinates of last point of last subpath in path"""
2301         x, y = self.end_pt()
2302         return unit.t_pt(x), unit.t_pt(y)
2303
2304     def join(self, other):
2305         if not self.subpaths:
2306             raise PathException("cannot join to end of empty path")
2307         if self.subpaths[-1].closed:
2308             raise PathException("cannot join to end of closed sub path")
2309         other = normpath(other)
2310         if not other.subpaths:
2311             raise PathException("cannot join empty path")
2312
2313         self.subpaths[-1].normpathels += other.subpaths[0].normpathels
2314         self.subpaths += other.subpaths[1:]
2315
2316     def joined(self, other):
2317         result = normpath(self.subpaths)
2318         result.join(other)
2319         return result
2320
2321     def intersect(self, other):
2322         """intersect self with other path
2323
2324         returns a tuple of lists consisting of the parameter values
2325         of the intersection points of the corresponding normpath
2326
2327         """
2328         if not isinstance(other, normpath):
2329             other = normpath(other)
2330
2331         # here we build up the result
2332         intersections = ([], [])
2333
2334         # Intersect all subpaths of self with the subpaths of
2335         # other. Here, st_a, st_b are the parameter values
2336         # corresponding to the first point of the subpaths sp_a and
2337         # sp_b, respectively.
2338         st_a = 0
2339         for sp_a in self.subpaths:
2340             st_b =0
2341             for sp_b in other.subpaths:
2342                 for intersection in zip(*sp_a.intersect(sp_b)):
2343                     intersections[0].append(intersection[0]+st_a)
2344                     intersections[1].append(intersection[1]+st_b)
2345                 st_b += sp_b.range()
2346             st_a += sp_a.range()
2347         return intersections
2348
2349     def range(self):
2350         """return maximal value for parameter value param"""
2351         return sum([sp.range() for sp in self.subpaths])
2352
2353     def reverse(self):
2354         """reverse path"""
2355         self.subpaths.reverse()
2356         for sp in self.subpaths:
2357             sp.reverse()
2358
2359     def reversed(self):
2360         """return reversed path"""
2361         nnormpath = normpath()
2362         for i in range(len(self.subpaths)):
2363             nnormpath.subpaths.append(self.subpaths[-(i+1)].reversed())
2364         return nnormpath
2365
2366     def split(self, params):
2367         """split path at parameter values params
2368
2369         Note that the parameter list has to be sorted.
2370
2371         """
2372
2373         # check whether parameter list is really sorted
2374         sortedparams = list(params)
2375         sortedparams.sort()
2376         if sortedparams!=list(params):
2377             raise ValueError("split parameter list params has to be sorted")
2378
2379         # we construct this list of normpaths
2380         result = []
2381
2382         # the currently built up normpath
2383         np = normpath()
2384
2385         t0 = 0
2386         for subpath in self.subpaths:
2387             tf = t0+subpath.range()
2388             if params and tf>=params[0]:
2389                 # split this subpath
2390                 # determine the relevant splitting params
2391                 for i in range(len(params)):
2392                     if params[i]>tf: break
2393                 else:
2394                     i = len(params)
2395
2396                 splitsubpaths = subpath.split([x-t0 for x in params[:i]])
2397                 # handle first element, which may be None, separately
2398                 if splitsubpaths[0] is None:
2399                     if not np.subpaths:
2400                         result.append(None)
2401                     else:
2402                         result.append(np)
2403                         np = normpath()
2404                     splitsubpaths.pop(0)
2405
2406                 for sp in splitsubpaths[:-1]:
2407                     np.subpaths.append(sp)
2408                     result.append(np)
2409                     np = normpath()
2410
2411                 # handle last element which may be None, separately
2412                 if splitsubpaths:
2413                     if splitsubpaths[-1] is None:
2414                         if np.subpaths:
2415                             result.append(np)
2416                             np = normpath()
2417                     else:
2418                         np.subpaths.append(splitsubpaths[-1])
2419
2420                 params = params[i:]
2421             else:
2422                 # append whole subpath to current normpath
2423                 np.subpaths.append(subpath)
2424             t0 = tf
2425
2426         if np.subpaths:
2427             result.append(np)
2428         else:
2429             # mark split at the end of the normsubpath
2430             result.append(None)
2431
2432         return result
2433
2434     def tangent(self, param=None, arclen=None, length=None):
2435         """return tangent vector of path at either parameter value param
2436         or arc length arclen.
2437
2438         At discontinuities in the path, the limit from below is returned.
2439         If length is not None, the tangent vector will be scaled to
2440         the desired length.
2441         """
2442         sp, param = self._findsubpath(param, arclen)
2443         return sp.tangent(param, length)
2444
2445     def transform(self, trafo):
2446         """transform path according to trafo"""
2447         for sp in self.subpaths:
2448             sp.transform(trafo)
2449
2450     def transformed(self, trafo):
2451         """return path transformed according to trafo"""
2452         return normpath([sp.transformed(trafo) for sp in self.subpaths])
2453
2454     def trafo(self, param=None, arclen=None):
2455         """return transformation at either parameter value param or arc length arclen"""
2456         sp, param = self._findsubpath(param, arclen)
2457         return sp.trafo(param)
2458
2459     def outputPS(self, file):
2460         for sp in self.subpaths:
2461             sp.outputPS(file)
2462
2463     def outputPDF(self, file):
2464         for sp in self.subpaths:
2465             sp.outputPDF(file)
2466