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