pyx/path.py

   1 #!/usr/bin/env python
   2 # -*- coding: ISO-8859-1 -*-
   3 #
   4 #
   5 # Copyright (C) 2002-2005 Jörg Lehmann <joergl@users.sourceforge.net>
   6 # Copyright (C) 2003-2004 Michael Schindler <m-schindler@users.sourceforge.net>
   7 # Copyright (C) 2002-2005 André Wobst <wobsta@users.sourceforge.net>
   8 #
   9 # This file is part of PyX (http://pyx.sourceforge.net/).
  10 #
  11 # PyX is free software; you can redistribute it and/or modify
  12 # it under the terms of the GNU General Public License as published by
  13 # the Free Software Foundation; either version 2 of the License, or
  14 # (at your option) any later version.
  15 #
  16 # PyX is distributed in the hope that it will be useful,
  17 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 # GNU General Public License for more details.
  20 #
  21 # You should have received a copy of the GNU General Public License
  22 # along with PyX; if not, write to the Free Software
  23 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24
  25 #       - exceptions: nocurrentpoint, paramrange
  26 #       - correct bbox for curveto and normcurve
  27 #         (maybe we still need the current bbox implementation (then maybe called
  28 #          cbox = control box) for normcurve for the use during the
  29 #          intersection of bpaths)
  30
  31 from __future__ import nested_scopes
  32
  33 import math, bisect
  34 from math import cos, sin, pi
  35 try:
  36     from math import radians, degrees
  37 except ImportError:
  38     # fallback implementation for Python 2.1 and below
  39     def radians(x): return x*pi/180
  40     def degrees(x): return x*180/pi
  41 import base, bbox, trafo, unit, helper
  42
  43 try:
  44     sum([])
  45 except NameError:
  46     # fallback implementation for Python 2.2. and below
  47     def sum(list):
  48         return reduce(lambda x, y: x+y, list, 0)
  49
  50 try:
  51     enumerate([])
  52 except NameError:
  53     # fallback implementation for Python 2.2. and below
  54     def enumerate(list):
  55         return zip(xrange(len(list)), list)
  56
  57 # use new style classes when possible
  58 __metaclass__ = type
  59
  60 ################################################################################
  61
  62 # global epsilon (default precision of normsubpaths)
  63 _epsilon = 1e-5
  64
  65 def set(epsilon=None):
  66     global _epsilon
  67     if epsilon is not None:
  68         _epsilon = epsilon
  69
  70 ################################################################################
  71 # Bezier helper functions
  72 ################################################################################
  73
  74 def _arctobcurve(x_pt, y_pt, r_pt, phi1, phi2):
  75     """generate the best bezier curve corresponding to an arc segment"""
  76
  77     dphi = phi2-phi1
  78
  79     if dphi==0: return None
  80
  81     # the two endpoints should be clear
  82     x0_pt, y0_pt = x_pt+r_pt*cos(phi1), y_pt+r_pt*sin(phi1)
  83     x3_pt, y3_pt = x_pt+r_pt*cos(phi2), y_pt+r_pt*sin(phi2)
  84
  85     # optimal relative distance along tangent for second and third
  86     # control point
  87     l = r_pt*4*(1-cos(dphi/2))/(3*sin(dphi/2))
  88
  89     x1_pt, y1_pt = x0_pt-l*sin(phi1), y0_pt+l*cos(phi1)
  90     x2_pt, y2_pt = x3_pt+l*sin(phi2), y3_pt-l*cos(phi2)
  91
  92     return normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt)
  93
  94
  95 def _arctobezierpath(x_pt, y_pt, r_pt, phi1, phi2, dphimax=45):
  96     apath = []
  97
  98     phi1 = radians(phi1)
  99     phi2 = radians(phi2)
 100     dphimax = radians(dphimax)
 101
 102     if phi2<phi1:
 103         # guarantee that phi2>phi1 ...
 104         phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
 105     elif phi2>phi1+2*pi:
 106         # ... or remove unnecessary multiples of 2*pi
 107         phi2 = phi2 - (math.floor((phi2-phi1)/(2*pi))-1)*2*pi
 108
 109     if r_pt == 0 or phi1-phi2 == 0: return []
 110
 111     subdivisions = abs(int((1.0*(phi1-phi2))/dphimax))+1
 112
 113     dphi = (1.0*(phi2-phi1))/subdivisions
 114
 115     for i in range(subdivisions):
 116         apath.append(_arctobcurve(x_pt, y_pt, r_pt, phi1+i*dphi, phi1+(i+1)*dphi))
 117
 118     return apath
 119
 120 #
 121 # we define one exception
 122 #
 123
 124 class PathException(Exception): pass
 125
 126 ################################################################################
 127 # _pathcontext: context during walk along path
 128 ################################################################################
 129
 130 class _pathcontext:
 131
 132     """context during walk along path"""
 133
 134     __slots__ = "currentpoint", "currentsubpath"
 135
 136     def __init__(self, currentpoint=None, currentsubpath=None):
 137         """ initialize context
 138
 139         currentpoint:   position of current point
 140         currentsubpath: position of first point of current subpath
 141
 142         """
 143
 144         self.currentpoint = currentpoint
 145         self.currentsubpath = currentsubpath
 146
 147 ################################################################################
 148 # pathitem: element of a PS style path
 149 ################################################################################
 150
 151 class pathitem(base.canvasitem):
 152
 153     """element of a PS style path"""
 154
 155     def _updatecontext(self, context):
 156         """update context of during walk along pathitem
 157
 158         changes context in place
 159         """
 160         pass
 161
 162
 163     def _bbox(self, context):
 164         """calculate bounding box of pathitem
 165
 166         context: context of pathitem
 167
 168         returns bounding box of pathitem (in given context)
 169
 170         Important note: all coordinates in bbox, currentpoint, and
 171         currrentsubpath have to be floats (in unit.topt)
 172
 173         """
 174         pass
 175
 176     def _normalized(self, context):
 177         """returns list of normalized version of pathitem
 178
 179         context: context of pathitem
 180
 181         Returns the path converted into a list of closepath, moveto_pt,
 182         normline, or normcurve instances.
 183
 184         """
 185         pass
 186
 187     def outputPS(self, file):
 188         """write PS code corresponding to pathitem to file"""
 189         pass
 190
 191     def outputPDF(self, file):
 192         """write PDF code corresponding to pathitem to file"""
 193         pass
 194
 195 #
 196 # various pathitems
 197 #
 198 # Each one comes in two variants:
 199 #  - one which requires the coordinates to be already in pts (mainly
 200 #    used for internal purposes)
 201 #  - another which accepts arbitrary units
 202
 203 class closepath(pathitem):
 204
 205     """Connect subpath back to its starting point"""
 206
 207     __slots__ = ()
 208
 209     def __str__(self):
 210         return "closepath"
 211
 212     def _updatecontext(self, context):
 213         context.currentpoint = None
 214         context.currentsubpath = None
 215
 216     def _bbox(self, context):
 217         x0_pt, y0_pt = context.currentpoint
 218         x1_pt, y1_pt = context.currentsubpath
 219
 220         return bbox.bbox_pt(min(x0_pt, x1_pt), min(y0_pt, y1_pt),
 221                           max(x0_pt, x1_pt), max(y0_pt, y1_pt))
 222
 223     def _normalized(self, context):
 224         return [closepath()]
 225
 226     def outputPS(self, file):
 227         file.write("closepath\n")
 228
 229     def outputPDF(self, file):
 230         file.write("h\n")
 231
 232
 233 class moveto_pt(pathitem):
 234
 235     """Set current point to (x_pt, y_pt) (coordinates in pts)"""
 236
 237     __slots__ = "x_pt", "y_pt"
 238
 239     def __init__(self, x_pt, y_pt):
 240          self.x_pt = x_pt
 241          self.y_pt = y_pt
 242
 243     def __str__(self):
 244         return "%g %g moveto" % (self.x_pt, self.y_pt)
 245
 246     def _updatecontext(self, context):
 247         context.currentpoint = self.x_pt, self.y_pt
 248         context.currentsubpath = self.x_pt, self.y_pt
 249
 250     def _bbox(self, context):
 251         return None
 252
 253     def _normalized(self, context):
 254         return [moveto_pt(self.x_pt, self.y_pt)]
 255
 256     def outputPS(self, file):
 257         file.write("%g %g moveto\n" % (self.x_pt, self.y_pt) )
 258
 259     def outputPDF(self, file):
 260         file.write("%f %f m\n" % (self.x_pt, self.y_pt) )
 261
 262
 263 class lineto_pt(pathitem):
 264
 265     """Append straight line to (x_pt, y_pt) (coordinates in pts)"""
 266
 267     __slots__ = "x_pt", "y_pt"
 268
 269     def __init__(self, x_pt, y_pt):
 270          self.x_pt = x_pt
 271          self.y_pt = y_pt
 272
 273     def __str__(self):
 274         return "%g %g lineto" % (self.x_pt, self.y_pt)
 275
 276     def _updatecontext(self, context):
 277         context.currentsubpath = context.currentsubpath or context.currentpoint
 278         context.currentpoint = self.x_pt, self.y_pt
 279
 280     def _bbox(self, context):
 281         return bbox.bbox_pt(min(context.currentpoint[0], self.x_pt),
 282                           min(context.currentpoint[1], self.y_pt),
 283                           max(context.currentpoint[0], self.x_pt),
 284                           max(context.currentpoint[1], self.y_pt))
 285
 286     def _normalized(self, context):
 287         return [normline_pt(context.currentpoint[0], context.currentpoint[1], self.x_pt, self.y_pt)]
 288
 289     def outputPS(self, file):
 290         file.write("%g %g lineto\n" % (self.x_pt, self.y_pt) )
 291
 292     def outputPDF(self, file):
 293         file.write("%f %f l\n" % (self.x_pt, self.y_pt) )
 294
 295
 296 class curveto_pt(pathitem):
 297
 298     """Append curveto (coordinates in pts)"""
 299
 300     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
 301
 302     def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
 303         self.x1_pt = x1_pt
 304         self.y1_pt = y1_pt
 305         self.x2_pt = x2_pt
 306         self.y2_pt = y2_pt
 307         self.x3_pt = x3_pt
 308         self.y3_pt = y3_pt
 309
 310     def __str__(self):
 311         return "%g %g %g %g %g %g curveto" % (self.x1_pt, self.y1_pt,
 312                                               self.x2_pt, self.y2_pt,
 313                                               self.x3_pt, self.y3_pt)
 314
 315     def _updatecontext(self, context):
 316         context.currentsubpath = context.currentsubpath or context.currentpoint
 317         context.currentpoint = self.x3_pt, self.y3_pt
 318
 319     def _bbox(self, context):
 320         return bbox.bbox_pt(min(context.currentpoint[0], self.x1_pt, self.x2_pt, self.x3_pt),
 321                           min(context.currentpoint[1], self.y1_pt, self.y2_pt, self.y3_pt),
 322                           max(context.currentpoint[0], self.x1_pt, self.x2_pt, self.x3_pt),
 323                           max(context.currentpoint[1], self.y1_pt, self.y2_pt, self.y3_pt))
 324
 325     def _normalized(self, context):
 326         return [normcurve_pt(context.currentpoint[0], context.currentpoint[1],
 327                           self.x1_pt, self.y1_pt,
 328                           self.x2_pt, self.y2_pt,
 329                           self.x3_pt, self.y3_pt)]
 330
 331     def outputPS(self, file):
 332         file.write("%g %g %g %g %g %g curveto\n" % ( self.x1_pt, self.y1_pt,
 333                                                      self.x2_pt, self.y2_pt,
 334                                                      self.x3_pt, self.y3_pt ) )
 335
 336     def outputPDF(self, file):
 337         file.write("%f %f %f %f %f %f c\n" % ( self.x1_pt, self.y1_pt,
 338                                                self.x2_pt, self.y2_pt,
 339                                                self.x3_pt, self.y3_pt ) )
 340
 341
 342 class rmoveto_pt(pathitem):
 343
 344     """Perform relative moveto (coordinates in pts)"""
 345
 346     __slots__ = "dx_pt", "dy_pt"
 347
 348     def __init__(self, dx_pt, dy_pt):
 349          self.dx_pt = dx_pt
 350          self.dy_pt = dy_pt
 351
 352     def _updatecontext(self, context):
 353         context.currentpoint = (context.currentpoint[0] + self.dx_pt,
 354                                 context.currentpoint[1] + self.dy_pt)
 355         context.currentsubpath = context.currentpoint
 356
 357     def _bbox(self, context):
 358         return None
 359
 360     def _normalized(self, context):
 361         x_pt = context.currentpoint[0]+self.dx_pt
 362         y_pt = context.currentpoint[1]+self.dy_pt
 363         return [moveto_pt(x_pt, y_pt)]
 364
 365     def outputPS(self, file):
 366         file.write("%g %g rmoveto\n" % (self.dx_pt, self.dy_pt) )
 367
 368
 369 class rlineto_pt(pathitem):
 370
 371     """Perform relative lineto (coordinates in pts)"""
 372
 373     __slots__ = "dx_pt", "dy_pt"
 374
 375     def __init__(self, dx_pt, dy_pt):
 376          self.dx_pt = dx_pt
 377          self.dy_pt = dy_pt
 378
 379     def _updatecontext(self, context):
 380         context.currentsubpath = context.currentsubpath or context.currentpoint
 381         context.currentpoint = (context.currentpoint[0]+self.dx_pt,
 382                                 context.currentpoint[1]+self.dy_pt)
 383
 384     def _bbox(self, context):
 385         x = context.currentpoint[0] + self.dx_pt
 386         y = context.currentpoint[1] + self.dy_pt
 387         return bbox.bbox_pt(min(context.currentpoint[0], x),
 388                           min(context.currentpoint[1], y),
 389                           max(context.currentpoint[0], x),
 390                           max(context.currentpoint[1], y))
 391
 392     def _normalized(self, context):
 393         x0_pt = context.currentpoint[0]
 394         y0_pt = context.currentpoint[1]
 395         return [normline_pt(x0_pt, y0_pt, x0_pt+self.dx_pt, y0_pt+self.dy_pt)]
 396
 397     def outputPS(self, file):
 398         file.write("%g %g rlineto\n" % (self.dx_pt, self.dy_pt) )
 399
 400
 401 class rcurveto_pt(pathitem):
 402
 403     """Append rcurveto (coordinates in pts)"""
 404
 405     __slots__ = "dx1_pt", "dy1_pt", "dx2_pt", "dy2_pt", "dx3_pt", "dy3_pt"
 406
 407     def __init__(self, dx1_pt, dy1_pt, dx2_pt, dy2_pt, dx3_pt, dy3_pt):
 408         self.dx1_pt = dx1_pt
 409         self.dy1_pt = dy1_pt
 410         self.dx2_pt = dx2_pt
 411         self.dy2_pt = dy2_pt
 412         self.dx3_pt = dx3_pt
 413         self.dy3_pt = dy3_pt
 414
 415     def outputPS(self, file):
 416         file.write("%g %g %g %g %g %g rcurveto\n" % ( self.dx1_pt, self.dy1_pt,
 417                                                     self.dx2_pt, self.dy2_pt,
 418                                                     self.dx3_pt, self.dy3_pt ) )
 419
 420     def _updatecontext(self, context):
 421         x3_pt = context.currentpoint[0]+self.dx3_pt
 422         y3_pt = context.currentpoint[1]+self.dy3_pt
 423
 424         context.currentsubpath = context.currentsubpath or context.currentpoint
 425         context.currentpoint = x3_pt, y3_pt
 426
 427     def _bbox(self, context):
 428         x1_pt = context.currentpoint[0]+self.dx1_pt
 429         y1_pt = context.currentpoint[1]+self.dy1_pt
 430         x2_pt = context.currentpoint[0]+self.dx2_pt
 431         y2_pt = context.currentpoint[1]+self.dy2_pt
 432         x3_pt = context.currentpoint[0]+self.dx3_pt
 433         y3_pt = context.currentpoint[1]+self.dy3_pt
 434         return bbox.bbox_pt(min(context.currentpoint[0], x1_pt, x2_pt, x3_pt),
 435                           min(context.currentpoint[1], y1_pt, y2_pt, y3_pt),
 436                           max(context.currentpoint[0], x1_pt, x2_pt, x3_pt),
 437                           max(context.currentpoint[1], y1_pt, y2_pt, y3_pt))
 438
 439     def _normalized(self, context):
 440         x0_pt = context.currentpoint[0]
 441         y0_pt = context.currentpoint[1]
 442         return [normcurve_pt(x0_pt, y0_pt, x0_pt+self.dx1_pt, y0_pt+self.dy1_pt, x0_pt+self.dx2_pt, y0_pt+self.dy2_pt, x0_pt+self.dx3_pt, y0_pt+self.dy3_pt)]
 443
 444
 445 class arc_pt(pathitem):
 446
 447     """Append counterclockwise arc (coordinates in pts)"""
 448
 449     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 450
 451     def __init__(self, x_pt, y_pt, r_pt, angle1, angle2):
 452         self.x_pt = x_pt
 453         self.y_pt = y_pt
 454         self.r_pt = r_pt
 455         self.angle1 = angle1
 456         self.angle2 = angle2
 457
 458     def _sarc(self):
 459         """Return starting point of arc segment"""
 460         return (self.x_pt+self.r_pt*cos(radians(self.angle1)),
 461                 self.y_pt+self.r_pt*sin(radians(self.angle1)))
 462
 463     def _earc(self):
 464         """Return end point of arc segment"""
 465         return (self.x_pt+self.r_pt*cos(radians(self.angle2)),
 466                 self.y_pt+self.r_pt*sin(radians(self.angle2)))
 467
 468     def _updatecontext(self, context):
 469         if context.currentpoint:
 470             context.currentsubpath = context.currentsubpath or context.currentpoint
 471         else:
 472             # we assert that currentsubpath is also None
 473             context.currentsubpath = self._sarc()
 474
 475         context.currentpoint = self._earc()
 476
 477     def _bbox(self, context):
 478         phi1 = radians(self.angle1)
 479         phi2 = radians(self.angle2)
 480
 481         # starting end end point of arc segment
 482         sarcx_pt, sarcy_pt = self._sarc()
 483         earcx_pt, earcy_pt = self._earc()
 484
 485         # Now, we have to determine the corners of the bbox for the
 486         # arc segment, i.e. global maxima/mimima of cos(phi) and sin(phi)
 487         # in the interval [phi1, phi2]. These can either be located
 488         # on the borders of this interval or in the interior.
 489
 490         if phi2 < phi1:
 491             # guarantee that phi2>phi1
 492             phi2 = phi2 + (math.floor((phi1-phi2)/(2*pi))+1)*2*pi
 493
 494         # next minimum of cos(phi) looking from phi1 in counterclockwise
 495         # direction: 2*pi*floor((phi1-pi)/(2*pi)) + 3*pi
 496
 497         if phi2 < (2*math.floor((phi1-pi)/(2*pi))+3)*pi:
 498             minarcx_pt = min(sarcx_pt, earcx_pt)
 499         else:
 500             minarcx_pt = self.x_pt-self.r_pt
 501
 502         # next minimum of sin(phi) looking from phi1 in counterclockwise
 503         # direction: 2*pi*floor((phi1-3*pi/2)/(2*pi)) + 7/2*pi
 504
 505         if phi2 < (2*math.floor((phi1-3.0*pi/2)/(2*pi))+7.0/2)*pi:
 506             minarcy_pt = min(sarcy_pt, earcy_pt)
 507         else:
 508             minarcy_pt = self.y_pt-self.r_pt
 509
 510         # next maximum of cos(phi) looking from phi1 in counterclockwise
 511         # direction: 2*pi*floor((phi1)/(2*pi))+2*pi
 512
 513         if phi2 < (2*math.floor((phi1)/(2*pi))+2)*pi:
 514             maxarcx_pt = max(sarcx_pt, earcx_pt)
 515         else:
 516             maxarcx_pt = self.x_pt+self.r_pt
 517
 518         # next maximum of sin(phi) looking from phi1 in counterclockwise
 519         # direction: 2*pi*floor((phi1-pi/2)/(2*pi)) + 1/2*pi
 520
 521         if phi2 < (2*math.floor((phi1-pi/2)/(2*pi))+5.0/2)*pi:
 522             maxarcy_pt = max(sarcy_pt, earcy_pt)
 523         else:
 524             maxarcy_pt = self.y_pt+self.r_pt
 525
 526         # Finally, we are able to construct the bbox for the arc segment.
 527         # Note that if there is a currentpoint defined, we also
 528         # have to include the straight line from this point
 529         # to the first point of the arc segment
 530
 531         if context.currentpoint:
 532             return (bbox.bbox_pt(min(context.currentpoint[0], sarcx_pt),
 533                                min(context.currentpoint[1], sarcy_pt),
 534                                max(context.currentpoint[0], sarcx_pt),
 535                                max(context.currentpoint[1], sarcy_pt)) +
 536                     bbox.bbox_pt(minarcx_pt, minarcy_pt, maxarcx_pt, maxarcy_pt)
 537                     )
 538         else:
 539             return  bbox.bbox_pt(minarcx_pt, minarcy_pt, maxarcx_pt, maxarcy_pt)
 540
 541     def _normalized(self, context):
 542         # get starting and end point of arc segment and bpath corresponding to arc
 543         sarcx_pt, sarcy_pt = self._sarc()
 544         earcx_pt, earcy_pt = self._earc()
 545         barc = _arctobezierpath(self.x_pt, self.y_pt, self.r_pt, self.angle1, self.angle2)
 546
 547         # convert to list of curvetos omitting movetos
 548         nbarc = []
 549
 550         for bpathitem in barc:
 551             nbarc.append(normcurve_pt(bpathitem.x0_pt, bpathitem.y0_pt,
 552                                    bpathitem.x1_pt, bpathitem.y1_pt,
 553                                    bpathitem.x2_pt, bpathitem.y2_pt,
 554                                    bpathitem.x3_pt, bpathitem.y3_pt))
 555
 556         # Note that if there is a currentpoint defined, we also
 557         # have to include the straight line from this point
 558         # to the first point of the arc segment.
 559         # Otherwise, we have to add a moveto at the beginning
 560         if context.currentpoint:
 561             return [normline_pt(context.currentpoint[0], context.currentpoint[1], sarcx_pt, sarcy_pt)] + nbarc
 562         else:
 563             return [moveto_pt(sarcx_pt, sarcy_pt)] + nbarc
 564
 565     def outputPS(self, file):
 566         file.write("%g %g %g %g %g arc\n" % ( self.x_pt, self.y_pt,
 567                                             self.r_pt,
 568                                             self.angle1,
 569                                             self.angle2 ) )
 570
 571
 572 class arcn_pt(pathitem):
 573
 574     """Append clockwise arc (coordinates in pts)"""
 575
 576     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 577
 578     def __init__(self, x_pt, y_pt, r_pt, angle1, angle2):
 579         self.x_pt = x_pt
 580         self.y_pt = y_pt
 581         self.r_pt = r_pt
 582         self.angle1 = angle1
 583         self.angle2 = angle2
 584
 585     def _sarc(self):
 586         """Return starting point of arc segment"""
 587         return (self.x_pt+self.r_pt*cos(radians(self.angle1)),
 588                 self.y_pt+self.r_pt*sin(radians(self.angle1)))
 589
 590     def _earc(self):
 591         """Return end point of arc segment"""
 592         return (self.x_pt+self.r_pt*cos(radians(self.angle2)),
 593                 self.y_pt+self.r_pt*sin(radians(self.angle2)))
 594
 595     def _updatecontext(self, context):
 596         if context.currentpoint:
 597             context.currentsubpath = context.currentsubpath or context.currentpoint
 598         else:  # we assert that currentsubpath is also None
 599             context.currentsubpath = self._sarc()
 600
 601         context.currentpoint = self._earc()
 602
 603     def _bbox(self, context):
 604         # in principle, we obtain bbox of an arcn element from
 605         # the bounding box of the corrsponding arc element with
 606         # angle1 and angle2 interchanged. Though, we have to be carefull
 607         # with the straight line segment, which is added if currentpoint
 608         # is defined.
 609
 610         # Hence, we first compute the bbox of the arc without this line:
 611
 612         a = arc_pt(self.x_pt, self.y_pt, self.r_pt,
 613                  self.angle2,
 614                  self.angle1)
 615
 616         sarcx_pt, sarcy_pt = self._sarc()
 617         arcbb = a._bbox(_pathcontext())
 618
 619         # Then, we repeat the logic from arc.bbox, but with interchanged
 620         # start and end points of the arc
 621
 622         if context.currentpoint:
 623             return  bbox.bbox_pt(min(context.currentpoint[0], sarcx_pt),
 624                                min(context.currentpoint[1], sarcy_pt),
 625                                max(context.currentpoint[0], sarcx_pt),
 626                                max(context.currentpoint[1], sarcy_pt))+ arcbb
 627         else:
 628             return arcbb
 629
 630     def _normalized(self, context):
 631         # get starting and end point of arc segment and bpath corresponding to arc
 632         sarcx_pt, sarcy_pt = self._sarc()
 633         earcx_pt, earcy_pt = self._earc()
 634         barc = _arctobezierpath(self.x_pt, self.y_pt, self.r_pt, self.angle2, self.angle1)
 635         barc.reverse()
 636
 637         # convert to list of curvetos omitting movetos
 638         nbarc = []
 639
 640         for bpathitem in barc:
 641             nbarc.append(normcurve_pt(bpathitem.x3_pt, bpathitem.y3_pt,
 642                                    bpathitem.x2_pt, bpathitem.y2_pt,
 643                                    bpathitem.x1_pt, bpathitem.y1_pt,
 644                                    bpathitem.x0_pt, bpathitem.y0_pt))
 645
 646         # Note that if there is a currentpoint defined, we also
 647         # have to include the straight line from this point
 648         # to the first point of the arc segment.
 649         # Otherwise, we have to add a moveto at the beginning
 650         if context.currentpoint:
 651             return [normline_pt(context.currentpoint[0], context.currentpoint[1], sarcx_pt, sarcy_pt)] + nbarc
 652         else:
 653             return [moveto_pt(sarcx_pt, sarcy_pt)] + nbarc
 654
 655
 656     def outputPS(self, file):
 657         file.write("%g %g %g %g %g arcn\n" % ( self.x_pt, self.y_pt,
 658                                                self.r_pt,
 659                                                self.angle1,
 660                                                self.angle2 ) )
 661
 662
 663 class arct_pt(pathitem):
 664
 665     """Append tangent arc (coordinates in pts)"""
 666
 667     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "r_pt"
 668
 669     def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt, r_pt):
 670         self.x1_pt = x1_pt
 671         self.y1_pt = y1_pt
 672         self.x2_pt = x2_pt
 673         self.y2_pt = y2_pt
 674         self.r_pt = r_pt
 675
 676     def _path(self, currentpoint, currentsubpath):
 677         """returns new currentpoint, currentsubpath and path consisting
 678         of arc and/or line which corresponds to arct
 679
 680         this is a helper routine for _bbox and _normalized, which both need
 681         this path. Note: we don't want to calculate the bbox from a bpath
 682
 683         """
 684
 685         # direction and length of tangent 1
 686         dx1_pt = currentpoint[0]-self.x1_pt
 687         dy1_pt = currentpoint[1]-self.y1_pt
 688         l1 = math.hypot(dx1_pt, dy1_pt)
 689
 690         # direction and length of tangent 2
 691         dx2_pt = self.x2_pt-self.x1_pt
 692         dy2_pt = self.y2_pt-self.y1_pt
 693         l2 = math.hypot(dx2_pt, dy2_pt)
 694
 695         # intersection angle between two tangents
 696         alpha = math.acos((dx1_pt*dx2_pt+dy1_pt*dy2_pt)/(l1*l2))
 697
 698         if math.fabs(sin(alpha)) >= 1e-15 and 1.0+self.r_pt != 1.0:
 699             cotalpha2 = 1.0/math.tan(alpha/2)
 700
 701             # two tangent points
 702             xt1_pt = self.x1_pt + dx1_pt*self.r_pt*cotalpha2/l1
 703             yt1_pt = self.y1_pt + dy1_pt*self.r_pt*cotalpha2/l1
 704             xt2_pt = self.x1_pt + dx2_pt*self.r_pt*cotalpha2/l2
 705             yt2_pt = self.y1_pt + dy2_pt*self.r_pt*cotalpha2/l2
 706
 707             # direction of center of arc
 708             rx_pt = self.x1_pt - 0.5*(xt1_pt+xt2_pt)
 709             ry_pt = self.y1_pt - 0.5*(yt1_pt+yt2_pt)
 710             lr = math.hypot(rx_pt, ry_pt)
 711
 712             # angle around which arc is centered
 713             if rx_pt >= 0:
 714                 phi = degrees(math.atan2(ry_pt, rx_pt))
 715             else:
 716                 # XXX why is rx_pt/ry_pt and not ry_pt/rx_pt used???
 717                 phi = degrees(math.atan(rx_pt/ry_pt))+180
 718
 719             # half angular width of arc
 720             deltaphi = 90*(1-alpha/pi)
 721
 722             # center position of arc
 723             mx_pt = self.x1_pt - rx_pt*self.r_pt/(lr*sin(alpha/2))
 724             my_pt = self.y1_pt - ry_pt*self.r_pt/(lr*sin(alpha/2))
 725
 726             # now we are in the position to construct the path
 727             p = path(moveto_pt(*currentpoint))
 728
 729             if phi<0:
 730                 p.append(arc_pt(mx_pt, my_pt, self.r_pt, phi-deltaphi, phi+deltaphi))
 731             else:
 732                 p.append(arcn_pt(mx_pt, my_pt, self.r_pt, phi+deltaphi, phi-deltaphi))
 733
 734             return ( (xt2_pt, yt2_pt),
 735                      currentsubpath or (xt2_pt, yt2_pt),
 736                      p )
 737
 738         else:
 739             # we need no arc, so just return a straight line to currentpoint to x1_pt, y1_pt
 740             return  ( (self.x1_pt, self.y1_pt),
 741                       currentsubpath or (self.x1_pt, self.y1_pt),
 742                       line_pt(currentpoint[0], currentpoint[1], self.x1_pt, self.y1_pt) )
 743
 744     def _updatecontext(self, context):
 745         result = self._path(context.currentpoint, context.currentsubpath)
 746         context.currentpoint, context.currentsubpath = result[:2]
 747
 748     def _bbox(self, context):
 749         return self._path(context.currentpoint, context.currentsubpath)[2].bbox()
 750
 751     def _normalized(self, context):
 752         # XXX TODO NOTE
 753         return self._path(context.currentpoint,
 754                           context.currentsubpath)[2].normpath().normsubpaths[0].normsubpathitems
 755     def outputPS(self, file):
 756         file.write("%g %g %g %g %g arct\n" % ( self.x1_pt, self.y1_pt,
 757                                                self.x2_pt, self.y2_pt,
 758                                                self.r_pt ) )
 759
 760 #
 761 # now the pathitems that convert from user coordinates to pts
 762 #
 763
 764 class moveto(moveto_pt):
 765
 766     """Set current point to (x, y)"""
 767
 768     __slots__ = "x_pt", "y_pt"
 769
 770     def __init__(self, x, y):
 771         moveto_pt.__init__(self, unit.topt(x), unit.topt(y))
 772
 773
 774 class lineto(lineto_pt):
 775
 776     """Append straight line to (x, y)"""
 777
 778     __slots__ = "x_pt", "y_pt"
 779
 780     def __init__(self, x, y):
 781         lineto_pt.__init__(self, unit.topt(x), unit.topt(y))
 782
 783
 784 class curveto(curveto_pt):
 785
 786     """Append curveto"""
 787
 788     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
 789
 790     def __init__(self, x1, y1, x2, y2, x3, y3):
 791         curveto_pt.__init__(self,
 792                             unit.topt(x1), unit.topt(y1),
 793                             unit.topt(x2), unit.topt(y2),
 794                             unit.topt(x3), unit.topt(y3))
 795
 796 class rmoveto(rmoveto_pt):
 797
 798     """Perform relative moveto"""
 799
 800     __slots__ = "dx_pt", "dy_pt"
 801
 802     def __init__(self, dx, dy):
 803         rmoveto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
 804
 805
 806 class rlineto(rlineto_pt):
 807
 808     """Perform relative lineto"""
 809
 810     __slots__ = "dx_pt", "dy_pt"
 811
 812     def __init__(self, dx, dy):
 813         rlineto_pt.__init__(self, unit.topt(dx), unit.topt(dy))
 814
 815
 816 class rcurveto(rcurveto_pt):
 817
 818     """Append rcurveto"""
 819
 820     __slots__ = "dx1_pt", "dy1_pt", "dx2_pt", "dy2_pt", "dx3_pt", "dy3_pt"
 821
 822     def __init__(self, dx1, dy1, dx2, dy2, dx3, dy3):
 823         rcurveto_pt.__init__(self,
 824                              unit.topt(dx1), unit.topt(dy1),
 825                              unit.topt(dx2), unit.topt(dy2),
 826                              unit.topt(dx3), unit.topt(dy3))
 827
 828
 829 class arcn(arcn_pt):
 830
 831     """Append clockwise arc"""
 832
 833     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 834
 835     def __init__(self, x, y, r, angle1, angle2):
 836         arcn_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r), angle1, angle2)
 837
 838
 839 class arc(arc_pt):
 840
 841     """Append counterclockwise arc"""
 842
 843     __slots__ = "x_pt", "y_pt", "r_pt", "angle1", "angle2"
 844
 845     def __init__(self, x, y, r, angle1, angle2):
 846         arc_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(r), angle1, angle2)
 847
 848
 849 class arct(arct_pt):
 850
 851     """Append tangent arc"""
 852
 853     __slots__ = "x1_pt", "y1_pt", "x2_pt", "y2_pt", "r"
 854
 855     def __init__(self, x1, y1, x2, y2, r):
 856         arct_pt.__init__(self, unit.topt(x1), unit.topt(y1),
 857                          unit.topt(x2), unit.topt(y2), unit.topt(r))
 858
 859 #
 860 # "combined" pathitems provided for performance reasons
 861 #
 862
 863 class multilineto_pt(pathitem):
 864
 865     """Perform multiple linetos (coordinates in pts)"""
 866
 867     __slots__ = "points_pt"
 868
 869     def __init__(self, points_pt):
 870         self.points_pt = points_pt
 871
 872     def _updatecontext(self, context):
 873         context.currentsubpath = context.currentsubpath or context.currentpoint
 874         context.currentpoint = self.points_pt[-1]
 875
 876     def _bbox(self, context):
 877         xs_pt = [point[0] for point in self.points_pt]
 878         ys_pt = [point[1] for point in self.points_pt]
 879         return bbox.bbox_pt(min(context.currentpoint[0], *xs_pt),
 880                           min(context.currentpoint[1], *ys_pt),
 881                           max(context.currentpoint[0], *xs_pt),
 882                           max(context.currentpoint[1], *ys_pt))
 883
 884     def _normalized(self, context):
 885         result = []
 886         x0_pt, y0_pt = context.currentpoint
 887         for x_pt, y_pt in self.points_pt:
 888             result.append(normline_pt(x0_pt, y0_pt, x_pt, y_pt))
 889             x0_pt, y0_pt = x_pt, y_pt
 890         return result
 891
 892     def outputPS(self, file):
 893         for point_pt in self.points_pt:
 894             file.write("%g %g lineto\n" % point_pt )
 895
 896     def outputPDF(self, file):
 897         for point_pt in self.points_pt:
 898             file.write("%f %f l\n" % point_pt )
 899
 900
 901 class multicurveto_pt(pathitem):
 902
 903     """Perform multiple curvetos (coordinates in pts)"""
 904
 905     __slots__ = "points_pt"
 906
 907     def __init__(self, points_pt):
 908         self.points_pt = points_pt
 909
 910     def _updatecontext(self, context):
 911         context.currentsubpath = context.currentsubpath or context.currentpoint
 912         context.currentpoint = self.points_pt[-1]
 913
 914     def _bbox(self, context):
 915         xs = ( [point[0] for point in self.points_pt] +
 916                [point[2] for point in self.points_pt] +
 917                [point[4] for point in self.points_pt] )
 918         ys = ( [point[1] for point in self.points_pt] +
 919                [point[3] for point in self.points_pt] +
 920                [point[5] for point in self.points_pt] )
 921         return bbox.bbox_pt(min(context.currentpoint[0], *xs_pt),
 922                           min(context.currentpoint[1], *ys_pt),
 923                           max(context.currentpoint[0], *xs_pt),
 924                           max(context.currentpoint[1], *ys_pt))
 925
 926     def _normalized(self, context):
 927         result = []
 928         x0_pt, y0_pt = context.currentpoint
 929         for point_pt in self.points_pt:
 930             result.append(normcurve_pt(x0_pt, y0_pt, *point_pt))
 931             x0_pt, y0_pt = point_pt[4:]
 932         return result
 933
 934     def outputPS(self, file):
 935         for point_pt in self.points_pt:
 936             file.write("%g %g %g %g %g %g curveto\n" % point_pt)
 937
 938     def outputPDF(self, file):
 939         for point_pt in self.points_pt:
 940             file.write("%f %f %f %f %f %f c\n" % point_pt)
 941
 942
 943 ################################################################################
 944 # path: PS style path
 945 ################################################################################
 946
 947 class path(base.canvasitem):
 948
 949     """PS style path"""
 950
 951     __slots__ = "path", "_normpath"
 952
 953     def __init__(self, *args):
 954         if len(args)==1 and isinstance(args[0], path):
 955             self.path = args[0].path
 956         else:
 957             self.path = list(args)
 958         self._normpath = None
 959
 960     def __add__(self, other):
 961         return path(*(self.path+other.path))
 962
 963     def __iadd__(self, other):
 964         self.path += other.path
 965         self._normpath = None
 966         return self
 967
 968     def __getitem__(self, i):
 969         return self.path[i]
 970
 971     def __len__(self):
 972         return len(self.path)
 973
 974     def append(self, pathitem):
 975         self.path.append(pathitem)
 976         self._normpath = None
 977
 978     def arclen_pt(self):
 979         """returns total arc length of path in pts"""
 980         return self.normpath().arclen_pt()
 981
 982     def arclen(self):
 983         """returns total arc length of path"""
 984         return self.normpath().arclen()
 985
 986     def arclentoparam(self, lengths):
 987         """returns the parameter value(s) matching the given length(s)"""
 988         return self.normpath().arclentoparam(lengths)
 989
 990     def at_pt(self, params):
 991         """return coordinates of path in pts at params."""
 992         return self.normpath().at_pt(params)
 993
 994     def at(self, params):
 995         """return coordinates of path at params."""
 996         return self.normpath().at(params)
 997
 998     def bbox(self):
 999         context = _pathcontext()
1000         abbox = None
1001
1002         for pitem in self.path:
1003             nbbox =  pitem._bbox(context)
1004             pitem._updatecontext(context)
1005             if abbox is None:
1006                 abbox = nbbox
1007             elif nbbox:
1008                 abbox += nbbox
1009
1010         return abbox
1011
1012     def atbegin_pt(self):
1013         """return coordinates of first point of first subpath in path (in pts)"""
1014         return self.normpath().atbegin_pt()
1015
1016     def atbegin(self):
1017         """return coordinates of first point of first subpath in path"""
1018         return self.normpath().atbegin()
1019
1020     def curveradius_pt(self, params):
1021         """Returns the curvature radius in pts (or None if infinite)
1022         at params.  This is the inverse of the curvature at this parameter
1023
1024         Please note that this radius can be negative or positive,
1025         depending on the sign of the curvature"""
1026         return self.normpath().curveradius_pt(params)
1027
1028     def curveradius(self, params):
1029         """Returns the curvature radius (or None if infinite) at
1030         parameter params.  This is the inverse of
1031         the curvature at this parameter
1032
1033         Please note that this radius can be negative or positive,
1034         depending on the sign of the curvature"""
1035         return self.normpath().curveradius(params)
1036
1037     def atend_pt(self):
1038         """return coordinates of last point of last subpath in path (in pts)"""
1039         return self.normpath().atend_pt()
1040
1041     def atend(self):
1042         """return coordinates of last point of last subpath in path"""
1043         return self.normpath().atend()
1044
1045     def extend(self, pathitems):
1046         self.path.extend(pathitems)
1047
1048     def joined(self, other):
1049         """return path consisting of self and other joined together"""
1050         return self.normpath().joined(other)
1051
1052     # << operator also designates joining
1053     __lshift__ = joined
1054
1055     def intersect(self, other):
1056         """intersect normpath corresponding to self with other path"""
1057         return self.normpath().intersect(other)
1058
1059     def normpath(self, epsilon=None):
1060         """converts the path into a normpath"""
1061         # use cached value if existent
1062         if self._normpath is not None:
1063             return self._normpath
1064         # split path in sub paths
1065         subpaths = []
1066         currentsubpathitems = []
1067         context = _pathcontext()
1068         for pitem in self.path:
1069             for npitem in pitem._normalized(context):
1070                 if isinstance(npitem, moveto_pt):
1071                     if currentsubpathitems:
1072                         # append open sub path
1073                         subpaths.append(normsubpath(currentsubpathitems, closed=0, epsilon=epsilon))
1074                     # start new sub path
1075                     currentsubpathitems = []
1076                 elif isinstance(npitem, closepath):
1077                     if currentsubpathitems:
1078                         # append closed sub path
1079                         currentsubpathitems.append(normline_pt(context.currentpoint[0], context.currentpoint[1],
1080                                                             context.currentsubpath[0], context.currentsubpath[1]))
1081                     subpaths.append(normsubpath(currentsubpathitems, closed=1, epsilon=epsilon))
1082                     currentsubpathitems = []
1083                 else:
1084                     currentsubpathitems.append(npitem)
1085             pitem._updatecontext(context)
1086
1087         if currentsubpathitems:
1088             # append open sub path
1089             subpaths.append(normsubpath(currentsubpathitems, 0, epsilon))
1090         self._normpath = normpath(subpaths)
1091         return self._normpath
1092
1093     def reversed(self):
1094         """return reversed path"""
1095         return self.normpath().reversed()
1096
1097     def split(self, params):
1098         """return corresponding normpaths split at parameter values params"""
1099         return self.normpath().split(params)
1100
1101     def tangent(self, params, length=None):
1102         """return tangent vector of path at params.
1103
1104         If length is not None, the tangent vector will be scaled to
1105         the desired length.
1106         """
1107         return self.normpath().tangent(params, length)
1108
1109     def trafo(self, params):
1110         """return transformation at params"""
1111         return self.normpath().trafo(params)
1112
1113     def transformed(self, trafo):
1114         """return transformed path"""
1115         return self.normpath().transformed(trafo)
1116
1117     def outputPS(self, file):
1118         if not (isinstance(self.path[0], moveto_pt) or
1119                 isinstance(self.path[0], arc_pt) or
1120                 isinstance(self.path[0], arcn_pt)):
1121             raise PathException("first path element must be either moveto, arc, or arcn")
1122         for pitem in self.path:
1123             pitem.outputPS(file)
1124
1125     def outputPDF(self, file):
1126         if not (isinstance(self.path[0], moveto_pt) or
1127                 isinstance(self.path[0], arc_pt) or
1128                 isinstance(self.path[0], arcn_pt)):
1129             raise PathException("first path element must be either moveto, arc, or arcn")
1130         # PDF practically only supports normsubpathitems
1131         context = _pathcontext()
1132         for pitem in self.path:
1133             for npitem in pitem._normalized(context):
1134                 npitem.outputPDF(file)
1135             pitem._updatecontext(context)
1136
1137 ################################################################################
1138 # some special kinds of path, again in two variants
1139 ################################################################################
1140
1141 class line_pt(path):
1142
1143    """straight line from (x1_pt, y1_pt) to (x2_pt, y2_pt) (coordinates in pts)"""
1144
1145    def __init__(self, x1_pt, y1_pt, x2_pt, y2_pt):
1146        path.__init__(self, moveto_pt(x1_pt, y1_pt), lineto_pt(x2_pt, y2_pt))
1147
1148
1149 class curve_pt(path):
1150
1151    """Bezier curve with control points (x0_pt, y1_pt),..., (x3_pt, y3_pt)
1152    (coordinates in pts)"""
1153
1154    def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1155        path.__init__(self,
1156                      moveto_pt(x0_pt, y0_pt),
1157                      curveto_pt(x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1158
1159
1160 class rect_pt(path):
1161
1162    """rectangle at position (x,y) with width and height (coordinates in pts)"""
1163
1164    def __init__(self, x, y, width, height):
1165        path.__init__(self, moveto_pt(x, y),
1166                            lineto_pt(x+width, y),
1167                            lineto_pt(x+width, y+height),
1168                            lineto_pt(x, y+height),
1169                            closepath())
1170
1171
1172 class circle_pt(path):
1173
1174    """circle with center (x,y) and radius"""
1175
1176    def __init__(self, x, y, radius):
1177        path.__init__(self, arc_pt(x, y, radius, 0, 360),
1178                      closepath())
1179
1180
1181 class line(line_pt):
1182
1183    """straight line from (x1, y1) to (x2, y2)"""
1184
1185    def __init__(self, x1, y1, x2, y2):
1186        line_pt.__init__(self,
1187                         unit.topt(x1), unit.topt(y1),
1188                         unit.topt(x2), unit.topt(y2))
1189
1190
1191 class curve(curve_pt):
1192
1193    """Bezier curve with control points (x0, y1),..., (x3, y3)"""
1194
1195    def __init__(self, x0, y0, x1, y1, x2, y2, x3, y3):
1196        curve_pt.__init__(self,
1197                          unit.topt(x0), unit.topt(y0),
1198                          unit.topt(x1), unit.topt(y1),
1199                          unit.topt(x2), unit.topt(y2),
1200                          unit.topt(x3), unit.topt(y3))
1201
1202
1203 class rect(rect_pt):
1204
1205    """rectangle at position (x,y) with width and height"""
1206
1207    def __init__(self, x, y, width, height):
1208        rect_pt.__init__(self,
1209                         unit.topt(x), unit.topt(y),
1210                         unit.topt(width), unit.topt(height))
1211
1212
1213 class circle(circle_pt):
1214
1215    """circle with center (x,y) and radius"""
1216
1217    def __init__(self, x, y, radius):
1218        circle_pt.__init__(self,
1219                         unit.topt(x), unit.topt(y),
1220                         unit.topt(radius))
1221
1222 ################################################################################
1223 # normpath and corresponding classes
1224 ################################################################################
1225
1226 # two helper functions for the intersection of normsubpathitems
1227
1228 def _intersectnormcurves(a, a_t0, a_t1, b, b_t0, b_t1, epsilon):
1229     """intersect two bpathitems
1230
1231     a and b are bpathitems with parameter ranges [a_t0, a_t1],
1232     respectively [b_t0, b_t1].
1233     epsilon determines when the bpathitems are assumed to be straight
1234
1235     """
1236
1237     # intersection of bboxes is a necessary criterium for intersection
1238     if not a.bbox().intersects(b.bbox()): return []
1239
1240     if not a.isstraight(epsilon):
1241         (aa, ab) = a.midpointsplit()
1242         a_tm = 0.5*(a_t0+a_t1)
1243
1244         if not b.isstraight(epsilon):
1245             (ba, bb) = b.midpointsplit()
1246             b_tm = 0.5*(b_t0+b_t1)
1247
1248             return ( _intersectnormcurves(aa, a_t0, a_tm,
1249                                        ba, b_t0, b_tm, epsilon) +
1250                      _intersectnormcurves(ab, a_tm, a_t1,
1251                                        ba, b_t0, b_tm, epsilon) +
1252                      _intersectnormcurves(aa, a_t0, a_tm,
1253                                        bb, b_tm, b_t1, epsilon) +
1254                      _intersectnormcurves(ab, a_tm, a_t1,
1255                                        bb, b_tm, b_t1, epsilon) )
1256         else:
1257             return ( _intersectnormcurves(aa, a_t0, a_tm,
1258                                        b, b_t0, b_t1, epsilon) +
1259                      _intersectnormcurves(ab, a_tm, a_t1,
1260                                        b, b_t0, b_t1, epsilon) )
1261     else:
1262         if not b.isstraight(epsilon):
1263             (ba, bb) = b.midpointsplit()
1264             b_tm = 0.5*(b_t0+b_t1)
1265
1266             return  ( _intersectnormcurves(a, a_t0, a_t1,
1267                                        ba, b_t0, b_tm, epsilon) +
1268                       _intersectnormcurves(a, a_t0, a_t1,
1269                                        bb, b_tm, b_t1, epsilon) )
1270         else:
1271             # no more subdivisions of either a or b
1272             # => try to intersect a and b as straight line segments
1273
1274             a_deltax = a.x3_pt - a.x0_pt
1275             a_deltay = a.y3_pt - a.y0_pt
1276             b_deltax = b.x3_pt - b.x0_pt
1277             b_deltay = b.y3_pt - b.y0_pt
1278
1279             det = b_deltax*a_deltay - b_deltay*a_deltax
1280
1281             ba_deltax0_pt = b.x0_pt - a.x0_pt
1282             ba_deltay0_pt = b.y0_pt - a.y0_pt
1283
1284             try:
1285                 a_t = ( b_deltax*ba_deltay0_pt - b_deltay*ba_deltax0_pt)/det
1286                 b_t = ( a_deltax*ba_deltay0_pt - a_deltay*ba_deltax0_pt)/det
1287             except ArithmeticError:
1288                 return []
1289
1290             # check for intersections out of bound
1291             if not (0<=a_t<=1 and 0<=b_t<=1): return []
1292
1293             # return rescaled parameters of the intersection
1294             return [ ( a_t0 + a_t * (a_t1 - a_t0),
1295                        b_t0 + b_t * (b_t1 - b_t0) ) ]
1296
1297
1298 def _intersectnormlines(a, b):
1299     """return one-element list constisting either of tuple of
1300     parameters of the intersection point of the two normlines a and b
1301     or empty list if both normlines do not intersect each other"""
1302
1303     a_deltax_pt = a.x1_pt - a.x0_pt
1304     a_deltay_pt = a.y1_pt - a.y0_pt
1305     b_deltax_pt = b.x1_pt - b.x0_pt
1306     b_deltay_pt = b.y1_pt - b.y0_pt
1307
1308     det = 1.0*(b_deltax_pt * a_deltay_pt - b_deltay_pt * a_deltax_pt)
1309
1310     ba_deltax0_pt = b.x0_pt - a.x0_pt
1311     ba_deltay0_pt = b.y0_pt - a.y0_pt
1312
1313     try:
1314         a_t = ( b_deltax_pt * ba_deltay0_pt - b_deltay_pt * ba_deltax0_pt)/det
1315         b_t = ( a_deltax_pt * ba_deltay0_pt - a_deltay_pt * ba_deltax0_pt)/det
1316     except ArithmeticError:
1317         return []
1318
1319     # check for intersections out of bound
1320     if not (0<=a_t<=1 and 0<=b_t<=1): return []
1321
1322     # return parameters of the intersection
1323     return [( a_t, b_t)]
1324
1325
1326 ################################################################################
1327 # normsubpathitem class
1328 ################################################################################
1329
1330 class normsubpathitem:
1331
1332     """element of a normalized sub path"""
1333
1334     def _arclentoparam_pt(self, lengths, epsilon):
1335         """returns tuple (t,l) with
1336           t the parameter where the arclen of normsubpathitem is length and
1337           l the total arclen
1338
1339         length:  length (in pts) to find the parameter for
1340         epsilon: epsilon controls the accuracy for calculation of the
1341                  length of the Bezier elements
1342         """
1343         # Note: _arclentoparam returns both, parameters and total lengths
1344         # while  arclentoparam returns only parameters
1345         pass
1346
1347     def arclen_pt(self, epsilon):
1348         """returns arc length of normsubpathitem in pts with given accuracy epsilon"""
1349         pass
1350
1351     def at_pt(self, t):
1352         """returns coordinates of point in pts at parameter t (0<=t<=1) """
1353         pass
1354
1355     def atbegin_pt(self):
1356         """returns coordinates in pts of begin of normsubpathitem """
1357         pass
1358
1359     def atend_pt(self):
1360         """returns coordinates in pts of end of normsubpathitem """
1361         pass
1362
1363     def bbox(self):
1364         """return bounding box of normsubpathitem"""
1365         pass
1366
1367     def curveradius_pt(self, params):
1368         """Returns the curvature radiuses in pts at params.
1369         This is the inverse of the curvature at these parameters
1370
1371         Please note that this radius can be negative or positive,
1372         depending on the sign of the curvature"""
1373         pass
1374
1375     def intersect(self, other, epsilon):
1376         """intersect self with other normsubpathitem"""
1377         pass
1378
1379     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1380         """returns a (new) modified normpath with different start and
1381         end points as provided"""
1382         pass
1383
1384     def paramtoarclen_pt(self, param, epsilon):
1385         """ return arc length in pts corresponding to param """
1386         pass
1387
1388     def reversed(self):
1389         """return reversed normsubpathitem"""
1390         pass
1391
1392     def split(self, parameters):
1393         """splits normsubpathitem
1394
1395         parameters: list of parameter values (0<=t<=1) at which to split
1396
1397         returns None or list of tuple of normsubpathitems corresponding to
1398         the orginal normsubpathitem.
1399
1400         """
1401         pass
1402
1403     def tangentvector_pt(self, t):
1404         """returns tangent vector of normsubpathitem in pts at parameter t (0<=t<=1)"""
1405         pass
1406
1407     def transformed(self, trafo):
1408         """return transformed normsubpathitem according to trafo"""
1409         pass
1410
1411     def outputPS(self, file):
1412         """write PS code corresponding to normsubpathitem to file"""
1413         pass
1414
1415     def outputPS(self, file):
1416         """write PDF code corresponding to normsubpathitem to file"""
1417         pass
1418
1419 ################################################################################
1420 # there are only two normsubpathitems: normline and normcurve
1421 ################################################################################
1422
1423 def _valueorlistmethod(method):
1424     def wrappedmethod(self, valueorlist, *args, **kwargs):
1425         try:
1426             for item in valueorlist:
1427                 break
1428         except:
1429             return method(self, [valueorlist], *args, **kwargs)[0]
1430         return method(self, valueorlist, *args, **kwargs)
1431     return wrappedmethod
1432
1433 class normline_pt(normsubpathitem):
1434
1435     """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)"""
1436
1437     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt"
1438
1439     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt):
1440          self.x0_pt = x0_pt
1441          self.y0_pt = y0_pt
1442          self.x1_pt = x1_pt
1443          self.y1_pt = y1_pt
1444
1445     def __str__(self):
1446         return "normline_pt(%g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt)
1447
1448     def _arclentoparam_pt(self, lengths, epsilon):
1449         l = math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
1450         return [length/l for length in lengths], l
1451
1452     def _normcurve(self):
1453         """ return self as equivalent normcurve """
1454         xa_pt = self.x0_pt+(self.x1_pt-self.x0_pt)/3.0
1455         ya_pt = self.y0_pt+(self.y1_pt-self.y0_pt)/3.0
1456         xb_pt = self.x0_pt+2.0*(self.x1_pt-self.x0_pt)/3.0
1457         yb_pt = self.y0_pt+2.0*(self.y1_pt-self.y0_pt)/3.0
1458         return normcurve_pt(self.x0_pt, self.y0_pt, xa_pt, ya_pt, xb_pt, yb_pt, self.x1_pt, self.y1_pt)
1459
1460     def arclen_pt(self,  epsilon):
1461         return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt)
1462
1463     def at_pt(self, params):
1464         return [(self.x0_pt+(self.x1_pt-self.x0_pt)*t, self.y0_pt+(self.y1_pt-self.y0_pt)*t)
1465                 for t in params]
1466
1467     def atbegin_pt(self):
1468         return self.x0_pt, self.y0_pt
1469
1470     def atend_pt(self):
1471         return self.x1_pt, self.y1_pt
1472
1473     def bbox(self):
1474         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt), min(self.y0_pt, self.y1_pt),
1475                           max(self.x0_pt, self.x1_pt), max(self.y0_pt, self.y1_pt))
1476
1477     def curveradius_pt(self, params):
1478         return [None] * len(params)
1479
1480     def intersect(self, other, epsilon):
1481         if isinstance(other, normline_pt):
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 modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1490         if xs_pt is None:
1491             xs_pt = self.x0_pt
1492         if ys_pt is None:
1493             ys_pt = self.y0_pt
1494         if xe_pt is None:
1495             xe_pt = self.x1_pt
1496         if ye_pt is None:
1497             ye_pt = self.y1_pt
1498         return normline_pt(xs_pt, ys_pt, xe_pt, ye_pt)
1499
1500     def _paramtoarclen_pt(self, params, epsilon):
1501         totalarclen_pt = self.arclen_pt(epsilon)
1502         arclens_pt = [totalarclen_pt * param for param in params + [1]]
1503         return arclens_pt[:-1], arclens_pt[-1]
1504
1505     def reverse(self):
1506         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt = self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1507
1508     def reversed(self):
1509         return normline_pt(self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
1510
1511     def split(self, params):
1512         # just for performance reasons
1513         x0_pt, y0_pt = self.x0_pt, self.y0_pt
1514         x1_pt, y1_pt = self.x1_pt, self.y1_pt
1515
1516         result = []
1517
1518         xl_pt, yl_pt = x0_pt, y0_pt
1519         for t in params + [1]:
1520             xr_pt, yr_pt = x0_pt + (x1_pt-x0_pt)*t, y0_pt + (y1_pt-y0_pt)*t
1521             result.append(normline_pt(xl_pt, yl_pt, xr_pt, yr_pt))
1522             xl_pt, yl_pt = xr_pt, yr_pt
1523
1524         return result
1525
1526     def trafo(self, params):
1527         rotate = trafo.rotate(degrees(math.atan2(self.y1_pt-self.y0_pt, self.x1_pt-self.x0_pt)))
1528         return [trafo.translate_pt(*at_pt) * rotate
1529                 for param, at_pt in zip(params, self.at_pt(params))]
1530
1531     def transformed(self, trafo):
1532         return normline_pt(*(trafo._apply(self.x0_pt, self.y0_pt) + trafo._apply(self.x1_pt, self.y1_pt)))
1533
1534     def outputPS(self, file):
1535         file.write("%g %g lineto\n" % (self.x1_pt, self.y1_pt))
1536
1537     def outputPDF(self, file):
1538         file.write("%f %f l\n" % (self.x1_pt, self.y1_pt))
1539
1540
1541 class normcurve_pt(normsubpathitem):
1542
1543     """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)"""
1544
1545     __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
1546
1547     def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt):
1548         self.x0_pt = x0_pt
1549         self.y0_pt = y0_pt
1550         self.x1_pt = x1_pt
1551         self.y1_pt = y1_pt
1552         self.x2_pt = x2_pt
1553         self.y2_pt = y2_pt
1554         self.x3_pt = x3_pt
1555         self.y3_pt = y3_pt
1556
1557     def __str__(self):
1558         return "normcurve_pt(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt,
1559                                                                  self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt)
1560
1561     def _arclentoparam_pt(self, lengths, epsilon):
1562         """computes the parameters [t] of bpathitem where the given lengths (in pts) are assumed
1563         returns ( [parameters], total arclen)
1564         A negative length gives a parameter 0"""
1565
1566         # create the list of accumulated lengths
1567         # and the length of the parameters
1568         seg = self.seglengths(1, epsilon)
1569         arclens = [seg[i][0] for i in range(len(seg))]
1570         Dparams = [seg[i][1] for i in range(len(seg))]
1571         l = len(arclens)
1572         for i in range(1,l):
1573             arclens[i] += arclens[i-1]
1574
1575         # create the list of parameters to be returned
1576         params = []
1577         for length in lengths:
1578             # find the last index that is smaller than length
1579             try:
1580                 lindex = bisect.bisect_left(arclens, length)
1581             except: # workaround for python 2.0
1582                 lindex = bisect.bisect(arclens, length)
1583                 while lindex and (lindex >= len(arclens) or
1584                                   arclens[lindex] >= length):
1585                     lindex -= 1
1586             if lindex == 0:
1587                 param = Dparams[0] * length * 1.0 / arclens[0]
1588             elif lindex < l-1:
1589                 param = Dparams[lindex+1] * (length - arclens[lindex]) * 1.0 / (arclens[lindex+1] - arclens[lindex])
1590                 for i in range(lindex+1):
1591                     param += Dparams[i]
1592             else:
1593                 param = 1 + Dparams[-1] * (length - arclens[-1]) * 1.0 / (arclens[-1] - arclens[-2])
1594
1595             # param = max(min(param,1),0)
1596             params.append(param)
1597         return (params, arclens[-1])
1598
1599     def arclen_pt(self, epsilon):
1600         """computes arclen of bpathitem in pts using successive midpoint split"""
1601         if self.isstraight(epsilon):
1602             return math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1603         else:
1604             a, b = self.midpointsplit()
1605             return a.arclen_pt(epsilon) + b.arclen_pt(epsilon)
1606
1607     def at_pt(self, params):
1608         return [( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t +
1609                   (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt          )*t*t +
1610                   (-3*self.x0_pt+3*self.x1_pt                      )*t +
1611                   self.x0_pt,
1612                   (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t +
1613                   (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt          )*t*t +
1614                   (-3*self.y0_pt+3*self.y1_pt                      )*t +
1615                   self.y0_pt )
1616                 for t in params]
1617
1618     def atbegin_pt(self):
1619         return self.x0_pt, self.y0_pt
1620
1621     def atend_pt(self):
1622         return self.x3_pt, self.y3_pt
1623
1624     def bbox(self):
1625         return bbox.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1626                           min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt),
1627                           max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt),
1628                           max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt))
1629
1630     def curveradius_pt(self, params):
1631         result = []
1632         for param in params:
1633             xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) +
1634                      6 * (1-param)*param * (-self.x1_pt + self.x2_pt) +
1635                      3 * param*param * (-self.x2_pt + self.x3_pt) )
1636             ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) +
1637                      6 * (1-param)*param * (-self.y1_pt + self.y2_pt) +
1638                      3 * param*param * (-self.y2_pt + self.y3_pt) )
1639             xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) +
1640                       6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) )
1641             yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) +
1642                       6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) )
1643             result.append((xdot**2 + ydot**2)**1.5 / (xdot*yddot - ydot*xddot))
1644         return result
1645
1646     def intersect(self, other, epsilon):
1647         if isinstance(other, normline_pt):
1648             return  _intersectnormcurves(self, 0, 1, other._normcurve(), 0, 1, epsilon)
1649         else:
1650             return  _intersectnormcurves(self, 0, 1, other, 0, 1, epsilon)
1651
1652     def isstraight(self, epsilon):
1653         """check wheter the normcurve is approximately straight"""
1654
1655         # just check, whether the modulus of the difference between
1656         # the length of the control polygon
1657         # (i.e. |P1-P0|+|P2-P1|+|P3-P2|) and the length of the
1658         # straight line between starting and ending point of the
1659         # normcurve (i.e. |P3-P1|) is smaller the epsilon
1660         return abs(math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt)+
1661                    math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt)+
1662                    math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt)-
1663                    math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt))<epsilon
1664
1665     def midpointsplit(self):
1666         """splits bpathitem at midpoint returning bpath with two bpathitems"""
1667
1668         # for efficiency reason, we do not use self.split(0.5)!
1669
1670         # first, we have to calculate the  midpoints between adjacent
1671         # control points
1672         x01_pt = 0.5*(self.x0_pt + self.x1_pt)
1673         y01_pt = 0.5*(self.y0_pt + self.y1_pt)
1674         x12_pt = 0.5*(self.x1_pt + self.x2_pt)
1675         y12_pt = 0.5*(self.y1_pt + self.y2_pt)
1676         x23_pt = 0.5*(self.x2_pt + self.x3_pt)
1677         y23_pt = 0.5*(self.y2_pt + self.y3_pt)
1678
1679         # In the next iterative step, we need the midpoints between 01 and 12
1680         # and between 12 and 23
1681         x01_12_pt = 0.5*(x01_pt + x12_pt)
1682         y01_12_pt = 0.5*(y01_pt + y12_pt)
1683         x12_23_pt = 0.5*(x12_pt + x23_pt)
1684         y12_23_pt = 0.5*(y12_pt + y23_pt)
1685
1686         # Finally the midpoint is given by
1687         xmidpoint_pt = 0.5*(x01_12_pt + x12_23_pt)
1688         ymidpoint_pt = 0.5*(y01_12_pt + y12_23_pt)
1689
1690         return (normcurve_pt(self.x0_pt, self.y0_pt,
1691                           x01_pt, y01_pt,
1692                           x01_12_pt, y01_12_pt,
1693                           xmidpoint_pt, ymidpoint_pt),
1694                 normcurve_pt(xmidpoint_pt, ymidpoint_pt,
1695                           x12_23_pt, y12_23_pt,
1696                           x23_pt, y23_pt,
1697                           self.x3_pt, self.y3_pt))
1698
1699     def modified(self, xs_pt=None, ys_pt=None, xe_pt=None, ye_pt=None):
1700         if xs_pt is None:
1701             xs_pt = self.x0_pt
1702         if ys_pt is None:
1703             ys_pt = self.y0_pt
1704         if xe_pt is None:
1705             xe_pt = self.x3_pt
1706         if ye_pt is None:
1707             ye_pt = self.y3_pt
1708         return normcurve_pt(xs_pt, ys_pt,
1709                          self.x1_pt, self.y1_pt,
1710                          self.x2_pt, self.y2_pt,
1711                          xe_pt, ye_pt)
1712
1713     def _paramtoarclen_pt(self, params, epsilon):
1714         arclens_pt = [splitpath.arclen_pt(epsilon) for splitpath in self.split(params)]
1715         for i in range(1, len(arclens_pt)):
1716             arclens_pt[i] += arclens_pt[i-1]
1717         return arclens_pt[:-1], arclens_pt[-1]
1718
1719     def reverse(self):
1720         self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt = \
1721         self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt
1722
1723     def reversed(self):
1724         return normcurve_pt(self.x3_pt, self.y3_pt, self.x2_pt, self.y2_pt, self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt)
1725
1726     def seglengths(self, paraminterval, epsilon):
1727         """returns the list of segment line lengths (in pts) of the normcurve
1728            together with the length of the parameterinterval"""
1729
1730         # lower and upper bounds for the arclen
1731         lowerlen = math.hypot(self.x3_pt-self.x0_pt, self.y3_pt-self.y0_pt)
1732         upperlen = ( math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt) +
1733                      math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt) +
1734                      math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt) )
1735
1736         # instead of isstraight method:
1737         if abs(upperlen-lowerlen)<epsilon:
1738             return [( 0.5*(upperlen+lowerlen), paraminterval )]
1739         else:
1740             a, b = self.midpointsplit()
1741             return a.seglengths(0.5*paraminterval, epsilon) + b.seglengths(0.5*paraminterval, epsilon)
1742
1743     def split(self, params):
1744         """return list of normcurves corresponding to split at parameters"""
1745
1746         # first, we calculate the coefficients corresponding to our
1747         # original bezier curve. These represent a useful starting
1748         # point for the following change of the polynomial parameter
1749         a0x_pt = self.x0_pt
1750         a0y_pt = self.y0_pt
1751         a1x_pt = 3*(-self.x0_pt+self.x1_pt)
1752         a1y_pt = 3*(-self.y0_pt+self.y1_pt)
1753         a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt)
1754         a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt)
1755         a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt
1756         a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt
1757
1758         params = [0] + params + [1]
1759         result = []
1760
1761         for i in range(len(params)-1):
1762             t1 = params[i]
1763             dt = params[i+1]-t1
1764
1765             # [t1,t2] part
1766             #
1767             # the new coefficients of the [t1,t1+dt] part of the bezier curve
1768             # are then given by expanding
1769             #  a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
1770             #  a3*(t1+dt*u)**3 in u, yielding
1771             #
1772             #   a0 + a1*t1 + a2*t1**2 + a3*t1**3        +
1773             #   ( a1 + 2*a2 + 3*a3*t1**2 )*dt    * u    +
1774             #   ( a2 + 3*a3*t1 )*dt**2           * u**2 +
1775             #   a3*dt**3                         * u**3
1776             #
1777             # from this values we obtain the new control points by inversion
1778             #
1779             # XXX: we could do this more efficiently by reusing for
1780             # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
1781             # Bezier curve
1782
1783             x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1
1784             y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1
1785             x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt
1786             y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt
1787             x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt
1788             y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt
1789             x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt
1790             y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt
1791
1792             result.append(normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt))
1793
1794         return result
1795
1796     def trafo(self, params):
1797         result = []
1798         for param, at_pt in zip(params, self.at_pt(params)):
1799             tdx_pt = (3*(  -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param +
1800                       2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt           )*param +
1801                         (-3*self.x0_pt+3*self.x1_pt                        ))
1802             tdy_pt = (3*(  -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param +
1803                       2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt           )*param +
1804                         (-3*self.y0_pt+3*self.y1_pt                        ))
1805             result.append(trafo.translate_pt(*at_pt) * trafo.rotate(degrees(math.atan2(tdy_pt, tdx_pt))))
1806         return result
1807
1808     def transform(self, trafo):
1809         self.x0_pt, self.y0_pt = trafo._apply(self.x0_pt, self.y0_pt)
1810         self.x1_pt, self.y1_pt = trafo._apply(self.x1_pt, self.y1_pt)
1811         self.x2_pt, self.y2_pt = trafo._apply(self.x2_pt, self.y2_pt)
1812         self.x3_pt, self.y3_pt = trafo._apply(self.x3_pt, self.y3_pt)
1813
1814     def transformed(self, trafo):
1815         return normcurve_pt(*(trafo._apply(self.x0_pt, self.y0_pt)+
1816                            trafo._apply(self.x1_pt, self.y1_pt)+
1817                            trafo._apply(self.x2_pt, self.y2_pt)+
1818                            trafo._apply(self.x3_pt, self.y3_pt)))
1819
1820     def outputPS(self, file):
1821         file.write("%g %g %g %g %g %g curveto\n" % (self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt))
1822
1823     def outputPDF(self, file):
1824         file.write("%f %f %f %f %f %f c\n" % (self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt))
1825
1826 ################################################################################
1827 # normsubpath class
1828 ################################################################################
1829
1830 class normsubpath:
1831
1832     """sub path of a normalized path
1833
1834     A subpath consists of a list of normsubpathitems, i.e., lines and bcurves
1835     and can either be closed or not.
1836
1837     Some invariants, which have to be obeyed:
1838     - All normsubpathitems have to be longer than epsilon pts.
1839     - At the end there may be a normline (stored in self.skippedline) whose
1840       length is shorter than epsilon
1841     - The last point of a normsubpathitem and the first point of the next
1842     element have to be equal.
1843     - When the path is closed, the last point of last normsubpathitem has
1844       to be equal to the first point of the first normsubpathitem.
1845     """
1846
1847     __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline"
1848
1849     def __init__(self, normsubpathitems=[], closed=0, epsilon=None):
1850         if epsilon is None:
1851             epsilon = _epsilon
1852         self.epsilon = epsilon
1853         # If one or more items appended to the normsubpath have been
1854         # skipped (because their total length was shorter than
1855         # epsilon), we remember this fact by a line because we have to
1856         # take it properly into account when appending further subnormpathitems
1857         self.skippedline = None
1858
1859         self.normsubpathitems = []
1860         self.closed = 0
1861
1862         # a test (might be temporary)
1863         for anormsubpathitem in normsubpathitems:
1864             assert isinstance(anormsubpathitem, normsubpathitem), "only list of normsubpathitem instances allowed"
1865
1866         self.extend(normsubpathitems)
1867
1868         if closed:
1869             self.close()
1870
1871     def __add__(self, other):
1872         # we take self.epsilon as accuracy for the resulting subnormpath
1873         result = subnormpath(self.normpathitems, self.closed, self.epsilon)
1874         result += other
1875         return result
1876
1877     def __getitem__(self, i):
1878         return self.normsubpathitems[i]
1879
1880     def __iadd__(self, other):
1881         if other.closed:
1882             raise PathException("Cannot extend normsubpath by closed normsubpath")
1883         self.extend(other.normsubpathitems)
1884         return self
1885
1886     def __len__(self):
1887         return len(self.normsubpathitems)
1888
1889     def __str__(self):
1890         return "subpath(%s, [%s])" % (self.closed and "closed" or "open",
1891                                     ", ".join(map(str, self.normsubpathitems)))
1892
1893     def _distributeparamsold(self, params):
1894         """Creates a list tuples (normsubpathitem, itemparams),
1895         where itemparams are the parameter values corresponding
1896         to params in normsubpathitem. For the first normsubpathitem
1897         itemparams fulfil param < 1, for the last normsubpathitem
1898         itemparams fulfil 0 <= param, and for all other
1899         normsubpathitems itemparams fulfil 0 <= param < 1.
1900         Note that params have to be sorted.
1901         """
1902         if self.isshort():
1903             if params:
1904                 raise PathException("Cannot select parameters for a short normsubpath")
1905             return []
1906         result = []
1907         paramindex = 0
1908         for index, normsubpathitem in enumerate(self.normsubpathitems[:-1]):
1909             oldparamindex = paramindex
1910             while paramindex < len(params) and params[paramindex] < index + 1:
1911                 paramindex += 1
1912             result.append((normsubpathitem, [param - index for param in params[oldparamindex: paramindex]]))
1913         result.append((self.normsubpathitems[-1],
1914                        [param - len(self.normsubpathitems) + 1 for param in params[paramindex:]]))
1915         return result
1916
1917     def _distributeparams(self, params):
1918         """Returns a dictionary mapping normsubpathitemindices to a tuple of a
1919         paramindices and normsubpathitemparams.
1920
1921         normsubpathitemindex specifies a normsubpathitem containing
1922         one or several positions.  paramindex specify the index of the
1923         param in the original list and normsubpathitemparam is the
1924         parameter value in the normsubpathitem.
1925         """
1926
1927         result = {}
1928         for i, param in enumerate(params):
1929             if param > 0:
1930                 index = int(param)
1931                 if index > len(self.normsubpathitems) - 1:
1932                     index = len(self.normsubpathitems) - 1
1933             else:
1934                 index = 0
1935             result.setdefault(index, ([], []))
1936             result[index][0].append(i)
1937             result[index][1].append(param - index)
1938         return result
1939
1940     def append(self, anormsubpathitem):
1941         assert isinstance(anormsubpathitem, normsubpathitem), "only normsubpathitem instances allowed"
1942
1943         if self.closed:
1944             raise PathException("Cannot append to closed normsubpath")
1945
1946         if self.skippedline:
1947             xs_pt, ys_pt = self.skippedline.atbegin_pt()
1948         else:
1949             xs_pt, ys_pt = anormsubpathitem.atbegin_pt()
1950         xe_pt, ye_pt = anormsubpathitem.atend_pt()
1951
1952         if (math.hypot(xe_pt-xs_pt, ye_pt-ys_pt) >= self.epsilon or
1953             anormsubpathitem.arclen_pt(self.epsilon) >= self.epsilon):
1954             if self.skippedline:
1955                 anormsubpathitem = anormsubpathitem.modified(xs_pt=xs_pt, ys_pt=ys_pt)
1956             self.normsubpathitems.append(anormsubpathitem)
1957             self.skippedline = None
1958         else:
1959             self.skippedline = normline_pt(xs_pt, ys_pt, xe_pt, ye_pt)
1960
1961     def arclen_pt(self):
1962         """returns total arc length of normsubpath in pts with accuracy epsilon"""
1963         return sum([npitem.arclen_pt(self.epsilon) for npitem in self.normsubpathitems])
1964
1965     def _arclentoparam_pt(self, lengths_pt):
1966         """ returns (t, l) where t are parameter values matching given lengths
1967         and l is the total length of the normsubpath """
1968         # work on a copy which is counted down to negative values
1969         lengths_pt = lengths_pt[:]
1970         results = [None] * len(lengths_pt)
1971
1972         totalarclen = 0
1973         for normsubpathindex, normsubpathitem in enumerate(self.normsubpathitems):
1974             params, arclen = normsubpathitem._arclentoparam_pt(lengths_pt, self.epsilon)
1975             for i in range(len(results)):
1976                 if results[i] is None:
1977                     lengths_pt[i] -= arclen
1978                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpathitems) - 1:
1979                         # overwrite the results until the length has become negative
1980                         results[i] = normsubpathindex + params[i]
1981             totalarclen += arclen
1982
1983         return results, totalarclen
1984
1985     def at_pt(self, params):
1986         """return coordinates in pts of sub path at parameter value params
1987
1988         The parameter param must be smaller or equal to the number of
1989         segments in the normpath, otherwise None is returned.
1990         """
1991         result = [None] * len(params)
1992         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
1993             for index, point_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].at_pt(params)):
1994                 result[index] = point_pt
1995         return result
1996
1997     def atbegin_pt(self):
1998         if not self.normsubpathitems and self.skippedline:
1999             return self.skippedline.atbegin_pt()
2000         return self.normsubpathitems[0].atbegin_pt()
2001
2002     def atend_pt(self):
2003         if self.skippedline:
2004             return self.skippedline.atend_pt()
2005         return self.normsubpathitems[-1].atend_pt()
2006
2007     def bbox(self):
2008         if self.normsubpathitems:
2009             abbox = self.normsubpathitems[0].bbox()
2010             for anormpathitem in self.normsubpathitems[1:]:
2011                 abbox += anormpathitem.bbox()
2012             return abbox
2013         else:
2014             return None
2015
2016     def close(self):
2017         if self.closed:
2018             raise PathException("Cannot close already closed normsubpath")
2019         if not self.normsubpathitems:
2020             if self.skippedline is None:
2021                 raise PathException("Cannot close empty normsubpath")
2022             else:
2023                 raise PathException("Normsubpath too short, cannot be closed")
2024
2025         xs_pt, ys_pt = self.normsubpathitems[-1].atend_pt()
2026         xe_pt, ye_pt = self.normsubpathitems[0].atbegin_pt()
2027         self.append(normline_pt(xs_pt, ys_pt, xe_pt, ye_pt))
2028
2029         # the append might have left a skippedline, which we have to remove
2030         # from the end of the closed path
2031         if self.skippedline:
2032             self.normsubpathitems[-1] = self.normsubpathitems[-1].modified(xe_pt=self.skippedline.x1_pt,
2033                                                                            ye_pt=self.skippedline.y1_pt)
2034             self.skippedline = None
2035
2036         self.closed = 1
2037
2038     def curveradius_pt(self, params):
2039         result = [None] * len(params)
2040         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
2041             for index, radius_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].curveradius_pt(params)):
2042                 result[index] = radius_pt
2043         return result
2044
2045     def extend(self, normsubpathitems):
2046         for normsubpathitem in normsubpathitems:
2047             self.append(normsubpathitem)
2048
2049     def intersect(self, other):
2050         """intersect self with other normsubpath
2051
2052         returns a tuple of lists consisting of the parameter values
2053         of the intersection points of the corresponding normsubpath
2054
2055         """
2056         intersections_a = []
2057         intersections_b = []
2058         epsilon = min(self.epsilon, other.epsilon)
2059         # Intersect all subpaths of self with the subpaths of other, possibly including
2060         # one intersection point several times
2061         for t_a, pitem_a  in enumerate(self.normsubpathitems):
2062             for t_b, pitem_b in enumerate(other.normsubpathitems):
2063                 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon):
2064                     intersections_a.append(intersection_a + t_a)
2065                     intersections_b.append(intersection_b + t_b)
2066
2067         # although intersectipns_a are sorted for the different normsubpathitems,
2068         # within a normsubpathitem, the ordering has to be ensured separately:
2069         intersections = zip(intersections_a, intersections_b)
2070         intersections.sort()
2071         intersections_a = [a for a, b in intersections]
2072         intersections_b = [b for a, b in intersections]
2073
2074         # for symmetry reasons we enumerate intersections_a as well, although
2075         # they are already sorted (note we do not need to sort intersections_a)
2076         intersections_a = zip(intersections_a, range(len(intersections_a)))
2077         intersections_b = zip(intersections_b, range(len(intersections_b)))
2078         intersections_b.sort()
2079
2080         # now we search for intersections points which are closer together than epsilon
2081         # This task is handled by the following function
2082         def closepoints(normsubpath, intersections):
2083             split = normsubpath.split([intersection for intersection, index in intersections])
2084             result = []
2085             if normsubpath.closed:
2086                 # note that the number of segments of a closed path is off by one
2087                 # compared to an open path
2088                 i = 0
2089                 while i < len(split):
2090                     splitnormsubpath = split[i]
2091                     j = i
2092                     while splitnormsubpath.isshort():
2093                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
2094                         if ip1<ip2:
2095                             result.append((ip1, ip2))
2096                         else:
2097                             result.append((ip2, ip1))
2098                         j += 1
2099                         if j == len(split):
2100                             j = 0
2101                         if j < len(split):
2102                             splitnormsubpath = splitnormsubpath.joined(split[j])
2103                         else:
2104                             break
2105                     i += 1
2106             else:
2107                 i = 1
2108                 while i < len(split)-1:
2109                     splitnormsubpath = split[i]
2110                     j = i
2111                     while splitnormsubpath.isshort():
2112                         ip1, ip2 = intersections[i-1][1], intersections[j][1]
2113                         if ip1<ip2:
2114                             result.append((ip1, ip2))
2115                         else:
2116                             result.append((ip2, ip1))
2117                         j += 1
2118                         if j < len(split)-1:
2119                             splitnormsubpath.join(split[j])
2120                         else:
2121                             break
2122                     i += 1
2123             return result
2124
2125         closepoints_a = closepoints(self, intersections_a)
2126         closepoints_b = closepoints(other, intersections_b)
2127
2128         # map intersection point to lowest point which is equivalent to the
2129         # point
2130         equivalentpoints = list(range(len(intersections_a)))
2131
2132         for closepoint_a in closepoints_a:
2133             for closepoint_b in closepoints_b:
2134                 if closepoint_a == closepoint_b:
2135                     for i in range(closepoint_a[1], len(equivalentpoints)):
2136                         if equivalentpoints[i] == closepoint_a[1]:
2137                             equivalentpoints[i] = closepoint_a[0]
2138
2139         # determine the remaining intersection points
2140         intersectionpoints = {}
2141         for point in equivalentpoints:
2142             intersectionpoints[point] = 1
2143
2144         # build result
2145         result = []
2146         intersectionpointskeys = intersectionpoints.keys()
2147         intersectionpointskeys.sort()
2148         for point in intersectionpointskeys:
2149             for intersection_a, index_a in intersections_a:
2150                 if index_a == point:
2151                     result_a = intersection_a
2152             for intersection_b, index_b in intersections_b:
2153                 if index_b == point:
2154                     result_b = intersection_b
2155             result.append((result_a, result_b))
2156         # note that the result is sorted in a, since we sorted
2157         # intersections_a in the very beginning
2158
2159         return [x for x, y in result], [y for x, y in result]
2160
2161     def isshort(self):
2162         """return whether the subnormpath is shorter than epsilon"""
2163         return not self.normsubpathitems
2164
2165     def join(self, other):
2166         for othernormpathitem in other.normsubpathitems:
2167             self.append(othernormpathitem)
2168         if other.skippedline is not None:
2169             self.append(other.skippedline)
2170
2171     def joined(self, other):
2172         result = normsubpath(self.normsubpathitems, self.closed, self.epsilon)
2173         result.skippedline = self.skippedline
2174         result.join(other)
2175         return result
2176
2177     def _paramtoarclen_pt(self, params):
2178         """returns a tuple of arc lengths and the total arc length."""
2179         result = [None] * len(params)
2180         totalarclen_pt = 0
2181         distributeparams = self._distributeparams(params)
2182         for normsubpathitemindex in range(len(self.normsubpathitems)):
2183             if distributeparams.has_key(normsubpathitemindex):
2184                 indices, params = distributeparams[normsubpathitemindex]
2185                 arclens_pt, normsubpathitemarclen_pt = self.normsubpathitems[normsubpathitemindex]._paramtoarclen_pt(params, self.epsilon)
2186                 for index, arclen_pt in zip(indices, arclens_pt):
2187                     result[index] = totalarclen_pt + arclen_pt
2188                 totalarclen_pt += normsubpathitemarclen_pt
2189             else:
2190                 totalarclen_pt += self.normsubpathitems[normsubpathitemindex].arclen_pt(self.epsilon)
2191         return result, totalarclen_pt
2192
2193     def reverse(self):
2194         self.normsubpathitems.reverse()
2195         for npitem in self.normsubpathitems:
2196             npitem.reverse()
2197
2198     def reversed(self):
2199         nnormpathitems = []
2200         for i in range(len(self.normsubpathitems)):
2201             nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed())
2202         return normsubpath(nnormpathitems, self.closed)
2203
2204     def split(self, params):
2205         """split normsubpath at list of parameter values params and return list
2206         of normsubpaths
2207
2208         The parameter list params has to be sorted. Note that each element of
2209         the resulting list is an open normsubpath.
2210         """
2211
2212         result = [normsubpath(epsilon=self.epsilon)]
2213
2214         for normsubpathitem, itemparams in self._distributeparamsold(params):
2215             splititems = normsubpathitem.split(itemparams)
2216             result[-1].append(splititems[0])
2217             result.extend([normsubpath([splititem], epsilon=self.epsilon) for splititem in splititems[1:]])
2218
2219         if self.closed:
2220             if params:
2221                 # join last and first segment together if the normsubpath was originally closed and it has been split
2222                 result[-1].normsubpathitems.extend(result[0].normsubpathitems)
2223                 result = result[-1:] + result[1:-1]
2224             else:
2225                 # otherwise just close the copied path again
2226                 result[0].close()
2227         return result
2228
2229     def trafo(self, params):
2230         result = [None] * len(params)
2231         for normsubpathitemindex, (indices, params) in self._distributeparams(params).items():
2232             for index, trafo in zip(indices, self.normsubpathitems[normsubpathitemindex].trafo(params)):
2233                 result[index] = trafo
2234         return result
2235
2236     def transform(self, trafo):
2237         """transform sub path according to trafo"""
2238         # note that we have to rebuild the path again since normsubpathitems
2239         # may become shorter than epsilon and/or skippedline may become
2240         # longer than epsilon
2241         normsubpathitems = self.normsubpathitems
2242         closed = self.closed
2243         skippedline = self.skippedline
2244         self.normsubpathitems = []
2245         self.closed = 0
2246         self.skippedline = None
2247         for pitem in normsubpathitems:
2248             self.append(pitem.transformed(trafo))
2249         if closed:
2250             self.close()
2251         elif skippedline is not None:
2252             self.append(skippedline.transformed(trafo))
2253
2254     def transformed(self, trafo):
2255         """return sub path transformed according to trafo"""
2256         nnormsubpath = normsubpath(epsilon=self.epsilon)
2257         for pitem in self.normsubpathitems:
2258             nnormsubpath.append(pitem.transformed(trafo))
2259         if self.closed:
2260             nnormsubpath.close()
2261         elif self.skippedline is not None:
2262             nnormsubpath.append(skippedline.transformed(trafo))
2263         return nnormsubpath
2264
2265     def outputPS(self, file):
2266         # if the normsubpath is closed, we must not output a normline at
2267         # the end
2268         if not self.normsubpathitems:
2269             return
2270         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
2271             normsubpathitems = self.normsubpathitems[:-1]
2272         else:
2273             normsubpathitems = self.normsubpathitems
2274         if normsubpathitems:
2275             file.write("%g %g moveto\n" % self.atbegin_pt())
2276             for anormpathitem in normsubpathitems:
2277                 anormpathitem.outputPS(file)
2278         if self.closed:
2279             file.write("closepath\n")
2280
2281     def outputPDF(self, file):
2282         # if the normsubpath is closed, we must not output a normline at
2283         # the end
2284         if not self.normsubpathitems:
2285             return
2286         if self.closed and isinstance(self.normsubpathitems[-1], normline_pt):
2287             normsubpathitems = self.normsubpathitems[:-1]
2288         else:
2289             normsubpathitems = self.normsubpathitems
2290         if normsubpathitems:
2291             file.write("%f %f m\n" % self.atbegin_pt())
2292             for anormpathitem in normsubpathitems:
2293                 anormpathitem.outputPDF(file)
2294         if self.closed:
2295             file.write("h\n")
2296
2297 ################################################################################
2298 # normpathparam class
2299 ################################################################################
2300
2301 class normpathparam:
2302
2303     """ parameter of a certain point along a normpath """
2304
2305     def __init__(self, normpath, normsubpathindex, normsubpathparam):
2306         self.normpath = normpath
2307         self.normsubpathindex = normsubpathindex
2308         self.normsubpathparam = normsubpathparam
2309         float(normsubpathparam)
2310
2311     def __add__(self, other):
2312         if isinstance(other, normpathparam):
2313             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
2314             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) +
2315                                                   other.normpath.paramtoarclen_pt(other))
2316         else:
2317             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) + unit.topt(other))
2318
2319     __radd__ = __add__
2320
2321     def __sub__(self, other):
2322         if isinstance(other, normpathparam):
2323             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
2324             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) -
2325                                                   other.normpath.paramtoarclen_pt(other))
2326         else:
2327             return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) - unit.topt(other))
2328
2329     def __rsub__(self, other):
2330         # other has to be a length in this case
2331         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self) + unit.topt(other))
2332
2333     def __mul__(self, factor):
2334         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) * factor)
2335
2336     __rmul__ = __mul__
2337
2338     def __div__(self, divisor):
2339         return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) / divisor)
2340
2341     def __neg__(self):
2342         return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self))
2343
2344     def __cmp__(self, other):
2345         if isinstance(other, normpathparam):
2346             assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath"
2347             return cmp((self.normsubpathindex, self.normsubpathparam), (other.normsubpathindex, other.normsubpathparam))
2348         else:
2349             return cmp(self.normpath.paramtoarclen_pt(self), unit.topt(other))
2350
2351     def arclen_pt(self):
2352         """ return arc length in pts corresponding to the normpathparam """
2353         return self.normpath.paramtoarclen_pt(self)
2354
2355     def arclen(self):
2356         """ return arc length corresponding to the normpathparam """
2357         return self.normpath.paramtoarclen(self)
2358
2359
2360
2361 ################################################################################
2362 # normpath class
2363 ################################################################################
2364
2365 class normpath(base.canvasitem):
2366
2367     """normalized path
2368
2369     A normalized path consists of a list of normalized sub paths.
2370
2371     """
2372
2373     def __init__(self, normsubpaths=None):
2374         """ construct a normpath from another normpath passed as arg,
2375         a path or a list of normsubpaths. An accuracy of epsilon pts
2376         is used for numerical calculations.
2377         """
2378         if normsubpaths is None:
2379             self.normsubpaths = []
2380         else:
2381             self.normsubpaths = normsubpaths
2382             for subpath in normsubpaths:
2383                 assert isinstance(subpath, normsubpath), "only list of normsubpath instances allowed"
2384
2385     def __add__(self, other):
2386         result = normpath()
2387         result.normsubpaths = self.normsubpaths + other.normpath().normsubpaths
2388         return result
2389
2390     def __getitem__(self, i):
2391         return self.normsubpaths[i]
2392
2393     def __iadd__(self, other):
2394         self.normsubpaths += other.normpath().normsubpaths
2395         return self
2396
2397     def __len__(self):
2398         return len(self.normsubpaths)
2399
2400     def __str__(self):
2401         return "normpath(%s)" % ", ".join(map(str, self.normsubpaths))
2402
2403     def _convertparams(self, params, convertmethod):
2404         """ Returns params with all non-normpathparam arguments converted
2405         by convertmethod """
2406         converttoparams = []
2407         convertparamindices = []
2408         for i, param in enumerate(params):
2409             if not isinstance(param, normpathparam):
2410                 converttoparams.append(param)
2411                 convertparamindices.append(i)
2412         if converttoparams:
2413             params = params[:]
2414             for i, param in zip(convertparamindices, convertmethod(converttoparams)):
2415                 params[i] = param
2416         return params
2417
2418     def _distributeparams(self, normpathparams):
2419         """Returns a dictionary mapping subpathindices to a tuple of a
2420         paramindices and subpathparams.
2421
2422         subpathindex specifies a subpath containing one or several positions.
2423         paramindex specify the index of the normpathparam in the original list and
2424         subpathparam is the parameter value in the subpath.
2425         """
2426
2427         result = {}
2428         for i, param in enumerate(normpathparams):
2429             assert param.normpath is self, "normpathparam has to belong to this path"
2430             result.setdefault(param.normsubpathindex, ([], []))
2431             result[param.normsubpathindex][0].append(i)
2432             result[param.normsubpathindex][1].append(param.normsubpathparam)
2433         return result
2434
2435     def append(self, anormsubpath):
2436         if isinstance(anormsubpath, normsubpath):
2437             # the normsubpaths list can be appended by a normsubpath only
2438             self.normsubpaths.append(anormsubpath)
2439         else:
2440             # ... but we are kind and allow for regular path items as well
2441             # in order to make a normpath to behave more like a regular path
2442
2443             for pathitem in anormsubpath._normalized(_pathcontext(self.normsubpaths[-1].atbegin_pt(),
2444                                                                   self.normsubpaths[-1].atend_pt())):
2445                 if isinstance(pathitem, closepath):
2446                     self.normsubpaths[-1].close()
2447                 elif isinstance(pathitem, moveto_pt):
2448                     self.normsubpaths.append(normsubpath([normline_pt(pathitem.x_pt, pathitem.y_pt,
2449                                                                    pathitem.x_pt, pathitem.y_pt)]))
2450                 else:
2451                     self.normsubpaths[-1].append(pathitem)
2452
2453     def arclen_pt(self):
2454         """returns total arc length of normpath in pts"""
2455         return sum([normsubpath.arclen_pt() for normsubpath in self.normsubpaths])
2456
2457     def arclen(self):
2458         """returns total arc length of normpath"""
2459         return self.arclen_pt() * unit.t_pt
2460
2461     def arclentoparam_pt(self, lengths_pt):
2462         """ returns the parameter values matching the given lengths """
2463         # work on a copy which is counted down to negative values
2464         lengths_pt = lengths_pt[:]
2465         results = [None] * len(lengths_pt)
2466
2467         for normsubpathindex, normsubpath in enumerate(self.normsubpaths):
2468             params, arclen = normsubpath._arclentoparam_pt(lengths_pt)
2469             done = 1
2470             for i, result in enumerate(results):
2471                 if results[i] is None:
2472                     lengths_pt[i] -= arclen
2473                     if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpaths) - 1:
2474                         # overwrite the results until the length has become negative
2475                         results[i] = normpathparam(self, normsubpathindex, params[i])
2476                     done = 0
2477             if done:
2478                 break
2479
2480         return results
2481     arclentoparam_pt = _valueorlistmethod(arclentoparam_pt)
2482
2483     def arclentoparam(self, lengths):
2484         """ returns the parameter values matching the given lengths """
2485         return self.arclentoparam_pt([unit.topt(l) for l in lengths])
2486     arclentoparam = _valueorlistmethod(arclentoparam)
2487
2488     def _at_pt(self, params):
2489         """return coordinates in pts of path at either parameter value param
2490         or arc length arclen.
2491         """
2492
2493         result = [None] * len(params)
2494         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
2495             for index, point_pt in zip(indices, self.normsubpaths[normsubpathindex].at_pt(params)):
2496                 result[index] = point_pt
2497         return result
2498
2499     def at_pt(self, params):
2500         """return coordinates of path (in pts) at either parameter value param
2501         or arc length arclen (in pts).
2502         """
2503
2504         return self._at_pt(self._convertparams(params, self.arclentoparam_pt))
2505     at_pt = _valueorlistmethod(at_pt)
2506
2507     def at(self, params):
2508         """return coordinates of path at either parameter value param
2509         or arc length arclen.
2510         """
2511
2512         return [(x_pt * unit.t_pt, y_pt * unit.t_pt)
2513                 for x_pt, y_pt in self._at_pt(self._convertparams(params, self.arclentoparam))]
2514     at = _valueorlistmethod(at)
2515
2516     def atbegin_pt(self):
2517         """return coordinates of first point of first subpath in path (in pts)"""
2518         if self.normsubpaths:
2519             return self.normsubpaths[0].atbegin_pt()
2520         else:
2521             raise PathException("cannot return first point of empty path")
2522
2523     def atbegin(self):
2524         """return coordinates of first point of first subpath in path"""
2525         x, y = self.atbegin_pt()
2526         return x * unit.t_pt, y * unit.t_pt
2527
2528     def atend_pt(self):
2529         """return coordinates of last point of last subpath in path (in pts)"""
2530         if self.normsubpaths:
2531             return self.normsubpaths[-1].atend_pt()
2532         else:
2533             raise PathException("cannot return last point of empty path")
2534
2535     def atend(self):
2536         """return coordinates of last point of last subpath in path"""
2537         x, y = self.atend_pt()
2538         return x * unit.t_pt, y * unit.t_pt
2539
2540     def begin(self):
2541         """return param corresponding to begin of path"""
2542         if self.normsubpaths:
2543             return normpathparam(self, 0, 0)
2544         else:
2545             raise PathException("empty path")
2546
2547     def bbox(self):
2548         abbox = None
2549         for normsubpath in self.normsubpaths:
2550             nbbox =  normsubpath.bbox()
2551             if abbox is None:
2552                 abbox = nbbox
2553             elif nbbox:
2554                 abbox += nbbox
2555         return abbox
2556
2557     def _curveradius_pt(self, params):
2558         """Returns the curvature radius in pts (or None if infinite)
2559         at parameter param or arc length arclen.  This is the inverse
2560         of the curvature at this parameter
2561
2562         Please note that this radius can be negative or positive,
2563         depending on the sign of the curvature"""
2564
2565         result = [None] * len(params)
2566         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
2567             for index, radius_pt in zip(indices, self.normsubpaths[normsubpathindex].curveradius_pt(params)):
2568                 result[index] = radius_pt
2569         return result
2570
2571     def curveradius_pt(self, params):
2572         """Returns the curvature radius in pts (or None if infinite)
2573         at parameter param or arc length arclen.  This is the inverse
2574         of the curvature at this parameter
2575
2576         Please note that this radius can be negative or positive,
2577         depending on the sign of the curvature"""
2578         return self._curveradius_pt(self._convertparams(params, self.arclentoparam_pt))
2579     curveradius_pt = _valueorlistmethod(curveradius_pt)
2580
2581     def curveradius(self, params):
2582         """Returns the curvature radius (or None if infinite) at
2583         parameter param or arc length arclen.  This is the inverse of
2584         the curvature at this parameter
2585
2586         Please note that this radius can be negative or positive,
2587         depending on the sign of the curvature"""
2588         result = []
2589         for radius_pt in self._curveradius_pt(self._convertparams(params, self.arclentoparam)):
2590             if radius_pt is not None:
2591                 result.append(radius_pt * unit.t_pt)
2592             else:
2593                 result.append(None)
2594         return result
2595     curveradius = _valueorlistmethod(curveradius)
2596
2597     def end(self):
2598         """return param corresponding to end of path"""
2599         if self.normsubpaths:
2600             return normpathparam(self, len(self)-1, len(self.normsubpaths[-1]))
2601         else:
2602             raise PathException("empty path")
2603
2604     def extend(self, normsubpaths):
2605         for anormsubpath in normsubpaths:
2606             # use append to properly handle regular path items as well as normsubpaths
2607             self.append(anormsubpath)
2608
2609     def join(self, other):
2610         if not self.normsubpaths:
2611             raise PathException("cannot join to end of empty path")
2612         if self.normsubpaths[-1].closed:
2613             raise PathException("cannot join to end of closed sub path")
2614         other = other.normpath()
2615         if not other.normsubpaths:
2616             raise PathException("cannot join empty path")
2617
2618         self.normsubpaths[-1].normsubpathitems += other.normsubpaths[0].normsubpathitems
2619         self.normsubpaths += other.normsubpaths[1:]
2620
2621     def joined(self, other):
2622         # NOTE we skip a deep copy for performance reasons
2623         result = normpath(self.normsubpaths)
2624         result.join(other)
2625         return result
2626
2627     # << operator also designates joining
2628     __lshift__ = joined
2629
2630     def intersect(self, other):
2631         """intersect self with other path
2632
2633         returns a tuple of lists consisting of the parameter values
2634         of the intersection points of the corresponding normpath
2635
2636         """
2637         other = other.normpath()
2638
2639         # here we build up the result
2640         intersections = ([], [])
2641
2642         # Intersect all normsubpaths of self with the normsubpaths of
2643         # other.
2644         for ia, normsubpath_a in enumerate(self.normsubpaths):
2645             for ib, normsubpath_b in enumerate(other.normsubpaths):
2646                 for intersection in zip(*normsubpath_a.intersect(normsubpath_b)):
2647                     intersections[0].append(normpathparam(self, ia, intersection[0]))
2648                     intersections[1].append(normpathparam(other, ib, intersection[1]))
2649         return intersections
2650
2651     def normpath(self):
2652         return self
2653
2654     def paramtoarclen_pt(self, normpathparams):
2655         """returns the arc length corresponding to the normpathparams"""
2656         result = [None] * len(normpathparams)
2657         totalarclen_pt = 0
2658         distributeparams = self._distributeparams(normpathparams)
2659         for normsubpathindex in range(max(distributeparams.keys()) + 1):
2660             if distributeparams.has_key(normsubpathindex):
2661                 indices, params = distributeparams[normsubpathindex]
2662                 arclens_pt, normsubpatharclen_pt = self.normsubpaths[normsubpathindex]._paramtoarclen_pt(params)
2663                 for index, arclen_pt in zip(indices, arclens_pt):
2664                     result[index] = totalarclen_pt + arclen_pt
2665                 totalarclen_pt += normsubpatharclen_pt
2666             else:
2667                 totalarclen_pt += self.normsubpaths[normsubpathindex].arclen_pt()
2668         return result
2669     paramtoarclen_pt = _valueorlistmethod(paramtoarclen_pt)
2670
2671     def paramtoarclen(self, normpathparams):
2672         return [arclen_pt * unit.t_pt for arclen_pt in self.paramtoarclen_pt(normpathparams)]
2673     paramtoarclen = _valueorlistmethod(paramtoarclen)
2674
2675     def reverse(self):
2676         """reverse path"""
2677         self.normsubpaths.reverse()
2678         for normsubpath in self.normsubpaths:
2679             normsubpath.reverse()
2680
2681     def reversed(self):
2682         """return reversed path"""
2683         nnormpath = normpath()
2684         for i in range(len(self.normsubpaths)):
2685             nnormpath.normsubpaths.append(self.normsubpaths[-(i+1)].reversed())
2686         return nnormpath
2687
2688     def _split(self, params):
2689         """split path at parameter values params and return list of normpaths
2690
2691         Note that the params has to be sorted.
2692         """
2693
2694
2695         # check whether parameter list is really sorted
2696         sortedparams = list(params)
2697         sortedparams.sort()
2698         if sortedparams != list(params):
2699             raise ValueError("split parameter list params has to be sorted")
2700
2701         distributeparams = self._distributeparams(params)
2702
2703         # we construct this list of normpaths
2704         result = []
2705
2706         # the currently built up normpath
2707         np = normpath()
2708
2709         for index, subpath in enumerate(self.normsubpaths):
2710             if distributeparams.has_key(index):
2711                 # we do not use the sorting information in distributeparams[index][0]
2712                 splitnormsubpaths = subpath.split(distributeparams[index][1])
2713                 np.normsubpaths.append(splitnormsubpaths[0])
2714                 for normsubpath in splitnormsubpaths[1:]:
2715                     result.append(np)
2716                     np = normpath([normsubpath])
2717             else:
2718                 np.normsubpaths.append(subpath)
2719
2720         result.append(np)
2721         return result
2722
2723     def split_pt(self, params):
2724         """split path at parameter values params and return a list of normpaths
2725
2726         Note that the params has to be sorted..
2727         """
2728         try:
2729             for param in params:
2730                 break
2731         except:
2732             params = [params]
2733         return self._split(self._convertparams(params, self.arclentoparam_pt))
2734
2735     def split(self, params):
2736         """split path at parameter values params and return a list of normpaths
2737
2738         Note that the params has to be sorted.
2739         """
2740         try:
2741             for param in params:
2742                 break
2743         except:
2744             params = [params]
2745         return self._split(self._convertparams(params, self.arclentoparam))
2746
2747     def _tangent(self, params, length=None):
2748         """return tangent vector of path at the parameter values params.
2749
2750         If length is not None, the tangent vector will be scaled to
2751         the desired length.
2752         """
2753         result = [None] * len(params)
2754         tangenttemplate = line_pt(0, 0, 1, 0).normpath()
2755         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
2756             for index, atrafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
2757                 tangentpath = tangenttemplate.transformed(atrafo)
2758                 if length is not None:
2759                     sfactor = unit.topt(length)/tangentpath.arclen_pt()
2760                     tangentpath.transform(trafo.scale_pt(sfactor, sfactor, *tangentpath.atbegin_pt()))
2761                 result[index] = tangentpath
2762         return result
2763
2764     def tangent_pt(self, params, length=None):
2765         """return tangent vector of path at the parameter values params.
2766
2767         If length is not None, the tangent vector will be scaled to
2768         the desired length.
2769         """
2770
2771         return self._tangent(self._convertparams(params, self.arclentoparam_pt), length)
2772     tangent_pt = _valueorlistmethod(tangent_pt)
2773
2774     def tangent(self, params, length=None):
2775         """return tangent vector of path at the parameter values params.
2776
2777         If length is not None, the tangent vector will be scaled to
2778         the desired length.
2779         """
2780
2781         return self._tangent(self._convertparams(params, self.arclentoparam), length)
2782     tangent = _valueorlistmethod(tangent)
2783
2784     def transform(self, trafo):
2785         """transform path according to trafo"""
2786         for normsubpath in self.normsubpaths:
2787             normsubpath.transform(trafo)
2788
2789     def transformed(self, trafo):
2790         """return path transformed according to trafo"""
2791         return normpath([normsubpath.transformed(trafo) for normsubpath in self.normsubpaths])
2792
2793     def _trafo(self, params):
2794         """return transformation at parameter values param"""
2795         result = [None] * len(params)
2796         for normsubpathindex, (indices, params) in self._distributeparams(params).items():
2797             for index, trafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)):
2798                 result[index] = trafo
2799         return result
2800
2801     def trafo_pt(self, params):
2802         """return transformation at parameter values param"""
2803         return self._trafo(self._convertparams(params, self.arclentoparam_pt))
2804     trafo_pt = _valueorlistmethod(trafo_pt)
2805
2806     def trafo(self, params):
2807         """return transformation at parameter values param"""
2808         return self._trafo(self._convertparams(params, self.arclentoparam))
2809     trafo = _valueorlistmethod(trafo)
2810
2811     def outputPS(self, file):
2812         for normsubpath in self.normsubpaths:
2813             normsubpath.outputPS(file)
2814
2815     def outputPDF(self, file):
2816         for normsubpath in self.normsubpaths:
2817             normsubpath.outputPDF(file)