pyx/path.py

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