2 # -*- coding: ISO-8859-1 -*-
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>
9 # This file is part of PyX (http://pyx.sourceforge.net/).
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.
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.
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 from __future__
import nested_scopes
29 from math
import radians
, degrees
31 # fallback implementation for Python 2.1
32 def radians(x
): return x
*math
.pi
/180
33 def degrees(x
): return x
*180/math
.pi
35 import bbox
, canvas
, path
, trafo
, unit
40 # fallback implementation for Python 2.2 and below
42 return reduce(lambda x
, y
: x
+y
, list, 0)
47 # fallback implementation for Python 2.2 and below
49 return zip(xrange(len(list)), list)
51 # use new style classes when possible
56 ################################################################################
58 # specific exception for normpath-related problems
59 class NormpathException(Exception): pass
61 # invalid result marker
64 """invalid result marker class
66 The followin norm(sub)path(item) methods:
72 return list of result values, which might contain the invalid instance
73 defined below to signal points, where the result is undefined due to
74 properties of the norm(sub)path(item). Accessing invalid leads to an
75 NormpathException, but you can test the result values by "is invalid".
79 raise NormpathException("invalid result (the requested value is undefined due to path properties)")
80 __str__
= __repr__
= __neg__
= invalid1
82 def invalid2(self
, other
):
84 __cmp__
= __add__
= __iadd__
= __sub__
= __isub__
= __mul__
= __imul__
= __div__
= __idiv__
= invalid2
88 ################################################################################
90 # global epsilon (default precision of normsubpaths)
92 # minimal relative speed (abort condition for tangent information)
95 def set(epsilon
=None, minrelspeed
=None):
98 if epsilon
is not None:
100 if minrelspeed
is not None:
101 _minrelspeed
= minrelspeed
104 ################################################################################
106 ################################################################################
108 class normsubpathitem
:
110 """element of a normalized sub path
112 Various operations on normsubpathitems might be subject of
113 approximitions. Those methods get the finite precision epsilon,
114 which is the accuracy needed expressed as a length in pts.
116 normsubpathitems should never be modified inplace, since references
117 might be shared betweeen several normsubpaths.
120 def arclen_pt(self
, epsilon
):
121 """return arc length in pts"""
124 def _arclentoparam_pt(self
, lengths_pt
, epsilon
):
125 """return a tuple of params and the total length arc length in pts"""
128 def arclentoparam_pt(self
, lengths_pt
, epsilon
):
129 """return a tuple of params"""
132 def at_pt(self
, params
):
133 """return coordinates at params in pts"""
136 def atbegin_pt(self
):
137 """return coordinates of first point in pts"""
141 """return coordinates of last point in pts"""
145 """return bounding box of normsubpathitem"""
149 """return control box of normsubpathitem
151 The control box also fully encloses the normsubpathitem but in the case of a Bezier
152 curve it is not the minimal box doing so. On the other hand, it is much faster
157 def curveradius_pt(self
, params
):
158 """return the curvature radius at params in pts
160 The curvature radius is the inverse of the curvature. When the
161 curvature is 0, None is returned. Note that this radius can be negative
162 or positive, depending on the sign of the curvature."""
165 def intersect(self
, other
, epsilon
):
166 """intersect self with other normsubpathitem"""
169 def modifiedbegin_pt(self
, x_pt
, y_pt
):
170 """return a normsubpathitem with a modified beginning point"""
173 def modifiedend_pt(self
, x_pt
, y_pt
):
174 """return a normsubpathitem with a modified end point"""
177 def _paramtoarclen_pt(self
, param
, epsilon
):
178 """return a tuple of arc lengths and the total arc length in pts"""
182 """return pathitem corresponding to normsubpathitem"""
185 """return reversed normsubpathitem"""
188 def rotation(self
, params
):
189 """return rotation trafos (i.e. trafos without translations) at params"""
192 def segments(self
, params
):
193 """return segments of the normsubpathitem
195 The returned list of normsubpathitems for the segments between
196 the params. params needs to contain at least two values.
200 def trafo(self
, params
):
201 """return transformations at params"""
203 def transformed(self
, trafo
):
204 """return transformed normsubpathitem according to trafo"""
207 def outputPS(self
, file, writer
, context
):
208 """write PS code corresponding to normsubpathitem to file"""
211 def outputPDF(self
, file, writer
, context
):
212 """write PDF code corresponding to normsubpathitem to file"""
216 class normline_pt(normsubpathitem
):
218 """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)"""
220 __slots__
= "x0_pt", "y0_pt", "x1_pt", "y1_pt"
222 def __init__(self
, x0_pt
, y0_pt
, x1_pt
, y1_pt
):
229 return "normline_pt(%g, %g, %g, %g)" % (self
.x0_pt
, self
.y0_pt
, self
.x1_pt
, self
.y1_pt
)
231 def _arclentoparam_pt(self
, lengths_pt
, epsilon
):
232 # do self.arclen_pt inplace for performance reasons
233 l_pt
= math
.hypot(self
.x0_pt
-self
.x1_pt
, self
.y0_pt
-self
.y1_pt
)
234 return [length_pt
/l_pt
for length_pt
in lengths_pt
], l_pt
236 def arclentoparam_pt(self
, lengths_pt
, epsilon
):
237 """return a tuple of params"""
238 return self
._arclentoparam
_pt
(lengths_pt
, epsilon
)[0]
240 def arclen_pt(self
, epsilon
):
241 return math
.hypot(self
.x0_pt
-self
.x1_pt
, self
.y0_pt
-self
.y1_pt
)
243 def at_pt(self
, params
):
244 return [(self
.x0_pt
+(self
.x1_pt
-self
.x0_pt
)*t
, self
.y0_pt
+(self
.y1_pt
-self
.y0_pt
)*t
)
247 def atbegin_pt(self
):
248 return self
.x0_pt
, self
.y0_pt
251 return self
.x1_pt
, self
.y1_pt
254 return bbox
.bbox_pt(min(self
.x0_pt
, self
.x1_pt
), min(self
.y0_pt
, self
.y1_pt
),
255 max(self
.x0_pt
, self
.x1_pt
), max(self
.y0_pt
, self
.y1_pt
))
259 def curvature_pt(self
, params
):
260 result
= [0] * len(params
)
262 def curveradius_pt(self
, params
):
263 return [None] * len(params
)
265 def intersect(self
, other
, epsilon
):
266 if isinstance(other
, normline_pt
):
267 a_deltax_pt
= self
.x1_pt
- self
.x0_pt
268 a_deltay_pt
= self
.y1_pt
- self
.y0_pt
270 b_deltax_pt
= other
.x1_pt
- other
.x0_pt
271 b_deltay_pt
= other
.y1_pt
- other
.y0_pt
273 det
= 1.0 / (b_deltax_pt
* a_deltay_pt
- b_deltay_pt
* a_deltax_pt
)
274 except ArithmeticError:
277 ba_deltax0_pt
= other
.x0_pt
- self
.x0_pt
278 ba_deltay0_pt
= other
.y0_pt
- self
.y0_pt
280 a_t
= (b_deltax_pt
* ba_deltay0_pt
- b_deltay_pt
* ba_deltax0_pt
) * det
281 b_t
= (a_deltax_pt
* ba_deltay0_pt
- a_deltay_pt
* ba_deltax0_pt
) * det
283 # check for intersections out of bound
284 # TODO: we might allow for a small out of bound errors.
285 if not (0<=a_t
<=1 and 0<=b_t
<=1):
288 # return parameters of intersection
291 return [(s_t
, o_t
) for o_t
, s_t
in other
.intersect(self
, epsilon
)]
293 def modifiedbegin_pt(self
, x_pt
, y_pt
):
294 return normline_pt(x_pt
, y_pt
, self
.x1_pt
, self
.y1_pt
)
296 def modifiedend_pt(self
, x_pt
, y_pt
):
297 return normline_pt(self
.x0_pt
, self
.y0_pt
, x_pt
, y_pt
)
299 def _paramtoarclen_pt(self
, params
, epsilon
):
300 totalarclen_pt
= self
.arclen_pt(epsilon
)
301 arclens_pt
= [totalarclen_pt
* param
for param
in params
+ [1]]
302 return arclens_pt
[:-1], arclens_pt
[-1]
305 return path
.lineto_pt(self
.x1_pt
, self
.y1_pt
)
308 return normline_pt(self
.x1_pt
, self
.y1_pt
, self
.x0_pt
, self
.y0_pt
)
310 def rotation(self
, params
):
311 return [trafo
.rotate(degrees(math
.atan2(self
.y1_pt
-self
.y0_pt
, self
.x1_pt
-self
.x0_pt
)))]*len(params
)
313 def segments(self
, params
):
315 raise ValueError("at least two parameters needed in segments")
319 xr_pt
= self
.x0_pt
+ (self
.x1_pt
-self
.x0_pt
)*t
320 yr_pt
= self
.y0_pt
+ (self
.y1_pt
-self
.y0_pt
)*t
321 if xl_pt
is not None:
322 result
.append(normline_pt(xl_pt
, yl_pt
, xr_pt
, yr_pt
))
327 def trafo(self
, params
):
328 rotate
= trafo
.rotate(degrees(math
.atan2(self
.y1_pt
-self
.y0_pt
, self
.x1_pt
-self
.x0_pt
)))
329 return [trafo
.translate_pt(*at_pt
) * rotate
330 for param
, at_pt
in zip(params
, self
.at_pt(params
))]
332 def transformed(self
, trafo
):
333 return normline_pt(*(trafo
.apply_pt(self
.x0_pt
, self
.y0_pt
) + trafo
.apply_pt(self
.x1_pt
, self
.y1_pt
)))
335 def outputPS(self
, file, writer
, context
):
336 file.write("%g %g lineto\n" % (self
.x1_pt
, self
.y1_pt
))
338 def outputPDF(self
, file, writer
, context
):
339 file.write("%f %f l\n" % (self
.x1_pt
, self
.y1_pt
))
342 class normcurve_pt(normsubpathitem
):
344 """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)"""
346 __slots__
= "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt"
348 def __init__(self
, x0_pt
, y0_pt
, x1_pt
, y1_pt
, x2_pt
, y2_pt
, x3_pt
, y3_pt
):
359 return "normcurve_pt(%g, %g, %g, %g, %g, %g, %g, %g)" % (self
.x0_pt
, self
.y0_pt
, self
.x1_pt
, self
.y1_pt
,
360 self
.x2_pt
, self
.y2_pt
, self
.x3_pt
, self
.y3_pt
)
362 def _midpointsplit(self
, epsilon
):
363 """split curve into two parts
365 Helper method to reduce the complexity of a problem by turning
366 a normcurve_pt into several normline_pt segments. This method
367 returns normcurve_pt instances only, when they are not yet straight
368 enough to be replaceable by normcurve_pt instances. Thus a recursive
369 midpointsplitting will turn a curve into line segments with the
370 given precision epsilon.
373 # first, we have to calculate the midpoints between adjacent
375 x01_pt
= 0.5*(self
.x0_pt
+ self
.x1_pt
)
376 y01_pt
= 0.5*(self
.y0_pt
+ self
.y1_pt
)
377 x12_pt
= 0.5*(self
.x1_pt
+ self
.x2_pt
)
378 y12_pt
= 0.5*(self
.y1_pt
+ self
.y2_pt
)
379 x23_pt
= 0.5*(self
.x2_pt
+ self
.x3_pt
)
380 y23_pt
= 0.5*(self
.y2_pt
+ self
.y3_pt
)
382 # In the next iterative step, we need the midpoints between 01 and 12
383 # and between 12 and 23
384 x01_12_pt
= 0.5*(x01_pt
+ x12_pt
)
385 y01_12_pt
= 0.5*(y01_pt
+ y12_pt
)
386 x12_23_pt
= 0.5*(x12_pt
+ x23_pt
)
387 y12_23_pt
= 0.5*(y12_pt
+ y23_pt
)
389 # Finally the midpoint is given by
390 xmidpoint_pt
= 0.5*(x01_12_pt
+ x12_23_pt
)
391 ymidpoint_pt
= 0.5*(y01_12_pt
+ y12_23_pt
)
393 # Before returning the normcurves we check whether we can
394 # replace them by normlines within an error of epsilon pts.
395 # The maximal error value is given by the modulus of the
396 # difference between the length of the control polygon
397 # (i.e. |P1-P0|+|P2-P1|+|P3-P2|), which consitutes an upper
398 # bound for the length, and the length of the straight line
399 # between start and end point of the normcurve (i.e. |P3-P1|),
400 # which represents a lower bound.
401 upperlen1
= (math
.hypot(x01_pt
- self
.x0_pt
, y01_pt
- self
.y0_pt
) +
402 math
.hypot(x01_12_pt
- x01_pt
, y01_12_pt
- y01_pt
) +
403 math
.hypot(xmidpoint_pt
- x01_12_pt
, ymidpoint_pt
- y01_12_pt
))
404 lowerlen1
= math
.hypot(xmidpoint_pt
- self
.x0_pt
, ymidpoint_pt
- self
.y0_pt
)
405 if upperlen1
-lowerlen1
< epsilon
:
406 c1
= normline_pt(self
.x0_pt
, self
.y0_pt
, xmidpoint_pt
, ymidpoint_pt
)
408 c1
= normcurve_pt(self
.x0_pt
, self
.y0_pt
,
410 x01_12_pt
, y01_12_pt
,
411 xmidpoint_pt
, ymidpoint_pt
)
413 upperlen2
= (math
.hypot(x12_23_pt
- xmidpoint_pt
, y12_23_pt
- ymidpoint_pt
) +
414 math
.hypot(x23_pt
- x12_23_pt
, y23_pt
- y12_23_pt
) +
415 math
.hypot(self
.x3_pt
- x23_pt
, self
.y3_pt
- y23_pt
))
416 lowerlen2
= math
.hypot(self
.x3_pt
- xmidpoint_pt
, self
.y3_pt
- ymidpoint_pt
)
417 if upperlen2
-lowerlen2
< epsilon
:
418 c2
= normline_pt(xmidpoint_pt
, ymidpoint_pt
, self
.x3_pt
, self
.y3_pt
)
420 c2
= normcurve_pt(xmidpoint_pt
, ymidpoint_pt
,
421 x12_23_pt
, y12_23_pt
,
423 self
.x3_pt
, self
.y3_pt
)
427 def _arclentoparam_pt(self
, lengths_pt
, epsilon
):
428 a
, b
= self
._midpointsplit
(epsilon
)
429 params_a
, arclen_a_pt
= a
._arclentoparam
_pt
(lengths_pt
, epsilon
)
430 params_b
, arclen_b_pt
= b
._arclentoparam
_pt
([length_pt
- arclen_a_pt
for length_pt
in lengths_pt
], epsilon
)
432 for param_a
, param_b
, length_pt
in zip(params_a
, params_b
, lengths_pt
):
433 if length_pt
> arclen_a_pt
:
434 params
.append(0.5+0.5*param_b
)
436 params
.append(0.5*param_a
)
437 return params
, arclen_a_pt
+ arclen_b_pt
439 def arclentoparam_pt(self
, lengths_pt
, epsilon
):
440 """return a tuple of params"""
441 return self
._arclentoparam
_pt
(lengths_pt
, epsilon
)[0]
443 def arclen_pt(self
, epsilon
):
444 a
, b
= self
._midpointsplit
(epsilon
)
445 return a
.arclen_pt(epsilon
) + b
.arclen_pt(epsilon
)
447 def at_pt(self
, params
):
448 return [( (-self
.x0_pt
+3*self
.x1_pt
-3*self
.x2_pt
+self
.x3_pt
)*t
*t
*t
+
449 (3*self
.x0_pt
-6*self
.x1_pt
+3*self
.x2_pt
)*t
*t
+
450 (-3*self
.x0_pt
+3*self
.x1_pt
)*t
+
452 (-self
.y0_pt
+3*self
.y1_pt
-3*self
.y2_pt
+self
.y3_pt
)*t
*t
*t
+
453 (3*self
.y0_pt
-6*self
.y1_pt
+3*self
.y2_pt
)*t
*t
+
454 (-3*self
.y0_pt
+3*self
.y1_pt
)*t
+
458 def atbegin_pt(self
):
459 return self
.x0_pt
, self
.y0_pt
462 return self
.x3_pt
, self
.y3_pt
465 xmin_pt
, xmax_pt
= path
._bezierpolyrange
(self
.x0_pt
, self
.x1_pt
, self
.x2_pt
, self
.x3_pt
)
466 ymin_pt
, ymax_pt
= path
._bezierpolyrange
(self
.y0_pt
, self
.y1_pt
, self
.y2_pt
, self
.y3_pt
)
467 return bbox
.bbox_pt(xmin_pt
, ymin_pt
, xmax_pt
, ymax_pt
)
470 return bbox
.bbox_pt(min(self
.x0_pt
, self
.x1_pt
, self
.x2_pt
, self
.x3_pt
),
471 min(self
.y0_pt
, self
.y1_pt
, self
.y2_pt
, self
.y3_pt
),
472 max(self
.x0_pt
, self
.x1_pt
, self
.x2_pt
, self
.x3_pt
),
473 max(self
.y0_pt
, self
.y1_pt
, self
.y2_pt
, self
.y3_pt
))
475 def curvature_pt(self
, params
):
477 # see notes in rotation
478 approxarclen
= (math
.hypot(self
.x1_pt
-self
.x0_pt
, self
.y1_pt
-self
.y0_pt
) +
479 math
.hypot(self
.x2_pt
-self
.x1_pt
, self
.y2_pt
-self
.y1_pt
) +
480 math
.hypot(self
.x3_pt
-self
.x2_pt
, self
.y3_pt
-self
.y2_pt
))
482 xdot
= ( 3 * (1-param
)*(1-param
) * (-self
.x0_pt
+ self
.x1_pt
) +
483 6 * (1-param
)*param
* (-self
.x1_pt
+ self
.x2_pt
) +
484 3 * param
*param
* (-self
.x2_pt
+ self
.x3_pt
) )
485 ydot
= ( 3 * (1-param
)*(1-param
) * (-self
.y0_pt
+ self
.y1_pt
) +
486 6 * (1-param
)*param
* (-self
.y1_pt
+ self
.y2_pt
) +
487 3 * param
*param
* (-self
.y2_pt
+ self
.y3_pt
) )
488 xddot
= ( 6 * (1-param
) * (self
.x0_pt
- 2*self
.x1_pt
+ self
.x2_pt
) +
489 6 * param
* (self
.x1_pt
- 2*self
.x2_pt
+ self
.x3_pt
) )
490 yddot
= ( 6 * (1-param
) * (self
.y0_pt
- 2*self
.y1_pt
+ self
.y2_pt
) +
491 6 * param
* (self
.y1_pt
- 2*self
.y2_pt
+ self
.y3_pt
) )
493 hypot
= math
.hypot(xdot
, ydot
)
494 if hypot
/approxarclen
> _minrelspeed
:
495 result
.append((xdot
*yddot
- ydot
*xddot
) / hypot
**3)
497 result
.append(invalid
)
500 def curveradius_pt(self
, params
):
503 xdot
= ( 3 * (1-param
)*(1-param
) * (-self
.x0_pt
+ self
.x1_pt
) +
504 6 * (1-param
)*param
* (-self
.x1_pt
+ self
.x2_pt
) +
505 3 * param
*param
* (-self
.x2_pt
+ self
.x3_pt
) )
506 ydot
= ( 3 * (1-param
)*(1-param
) * (-self
.y0_pt
+ self
.y1_pt
) +
507 6 * (1-param
)*param
* (-self
.y1_pt
+ self
.y2_pt
) +
508 3 * param
*param
* (-self
.y2_pt
+ self
.y3_pt
) )
509 xddot
= ( 6 * (1-param
) * (self
.x0_pt
- 2*self
.x1_pt
+ self
.x2_pt
) +
510 6 * param
* (self
.x1_pt
- 2*self
.x2_pt
+ self
.x3_pt
) )
511 yddot
= ( 6 * (1-param
) * (self
.y0_pt
- 2*self
.y1_pt
+ self
.y2_pt
) +
512 6 * param
* (self
.y1_pt
- 2*self
.y2_pt
+ self
.y3_pt
) )
514 # TODO: The curveradius can become huge. Shall we add/need/whatever an
515 # invalid threshold here too?
517 radius
= (xdot
**2 + ydot
**2)**1.5 / (xdot
*yddot
- ydot
*xddot
)
521 result
.append(radius
)
525 def intersect(self
, other
, epsilon
):
526 # There can be no intersection point, when the control boxes are not
527 # overlapping. Note that we use the control box instead of the bounding
528 # box here, because the former can be calculated more efficiently for
530 if not self
.cbox().intersects(other
.cbox()):
532 a
, b
= self
._midpointsplit
(epsilon
)
533 # To improve the performance in the general case we alternate the
534 # splitting process between the two normsubpathitems
535 return ( [( 0.5*a_t
, o_t
) for o_t
, a_t
in other
.intersect(a
, epsilon
)] +
536 [(0.5+0.5*b_t
, o_t
) for o_t
, b_t
in other
.intersect(b
, epsilon
)] )
538 def modifiedbegin_pt(self
, x_pt
, y_pt
):
539 return normcurve_pt(x_pt
, y_pt
,
540 self
.x1_pt
, self
.y1_pt
,
541 self
.x2_pt
, self
.y2_pt
,
542 self
.x3_pt
, self
.y3_pt
)
544 def modifiedend_pt(self
, x_pt
, y_pt
):
545 return normcurve_pt(self
.x0_pt
, self
.y0_pt
,
546 self
.x1_pt
, self
.y1_pt
,
547 self
.x2_pt
, self
.y2_pt
,
550 def _paramtoarclen_pt(self
, params
, epsilon
):
551 arclens_pt
= [segment
.arclen_pt(epsilon
) for segment
in self
.segments([0] + list(params
) + [1])]
552 for i
in range(1, len(arclens_pt
)):
553 arclens_pt
[i
] += arclens_pt
[i
-1]
554 return arclens_pt
[:-1], arclens_pt
[-1]
557 return path
.curveto_pt(self
.x1_pt
, self
.y1_pt
, self
.x2_pt
, self
.y2_pt
, self
.x3_pt
, self
.y3_pt
)
560 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
)
562 def rotation(self
, params
):
564 # We need to take care of the case of tdx_pt and tdy_pt close to zero.
565 # We should not compare those values to epsilon (which is a length) directly.
566 # Furthermore we want this "speed" in general and it's abort condition in
567 # particular to be invariant on the actual size of the normcurve. Hence we
568 # first calculate a crude approximation for the arclen.
569 approxarclen
= (math
.hypot(self
.x1_pt
-self
.x0_pt
, self
.y1_pt
-self
.y0_pt
) +
570 math
.hypot(self
.x2_pt
-self
.x1_pt
, self
.y2_pt
-self
.y1_pt
) +
571 math
.hypot(self
.x3_pt
-self
.x2_pt
, self
.y3_pt
-self
.y2_pt
))
573 tdx_pt
= (3*( -self
.x0_pt
+3*self
.x1_pt
-3*self
.x2_pt
+self
.x3_pt
)*param
*param
+
574 2*( 3*self
.x0_pt
-6*self
.x1_pt
+3*self
.x2_pt
)*param
+
575 (-3*self
.x0_pt
+3*self
.x1_pt
))
576 tdy_pt
= (3*( -self
.y0_pt
+3*self
.y1_pt
-3*self
.y2_pt
+self
.y3_pt
)*param
*param
+
577 2*( 3*self
.y0_pt
-6*self
.y1_pt
+3*self
.y2_pt
)*param
+
578 (-3*self
.y0_pt
+3*self
.y1_pt
))
579 # We scale the speed such the "relative speed" of a line is 1 independend of
580 # the length of the line. For curves we want this "relative speed" to be higher than
582 if math
.hypot(tdx_pt
, tdy_pt
)/approxarclen
> _minrelspeed
:
583 result
.append(trafo
.rotate(degrees(math
.atan2(tdy_pt
, tdx_pt
))))
585 # Note that we can't use the rule of l'Hopital here, since it would
586 # not provide us with a sign for the tangent. Hence we wouldn't
587 # notice whether the sign changes (which is a typical case at cusps).
588 result
.append(invalid
)
591 def segments(self
, params
):
593 raise ValueError("at least two parameters needed in segments")
595 # first, we calculate the coefficients corresponding to our
596 # original bezier curve. These represent a useful starting
597 # point for the following change of the polynomial parameter
600 a1x_pt
= 3*(-self
.x0_pt
+self
.x1_pt
)
601 a1y_pt
= 3*(-self
.y0_pt
+self
.y1_pt
)
602 a2x_pt
= 3*(self
.x0_pt
-2*self
.x1_pt
+self
.x2_pt
)
603 a2y_pt
= 3*(self
.y0_pt
-2*self
.y1_pt
+self
.y2_pt
)
604 a3x_pt
= -self
.x0_pt
+3*(self
.x1_pt
-self
.x2_pt
)+self
.x3_pt
605 a3y_pt
= -self
.y0_pt
+3*(self
.y1_pt
-self
.y2_pt
)+self
.y3_pt
609 for i
in range(len(params
)-1):
615 # the new coefficients of the [t1,t1+dt] part of the bezier curve
616 # are then given by expanding
617 # a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 +
618 # a3*(t1+dt*u)**3 in u, yielding
620 # a0 + a1*t1 + a2*t1**2 + a3*t1**3 +
621 # ( a1 + 2*a2 + 3*a3*t1**2 )*dt * u +
622 # ( a2 + 3*a3*t1 )*dt**2 * u**2 +
625 # from this values we obtain the new control points by inversion
627 # TODO: we could do this more efficiently by reusing for
628 # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous
631 x0_pt
= a0x_pt
+ a1x_pt
*t1
+ a2x_pt
*t1
*t1
+ a3x_pt
*t1
*t1
*t1
632 y0_pt
= a0y_pt
+ a1y_pt
*t1
+ a2y_pt
*t1
*t1
+ a3y_pt
*t1
*t1
*t1
633 x1_pt
= (a1x_pt
+2*a2x_pt
*t1
+3*a3x_pt
*t1
*t1
)*dt
/3.0 + x0_pt
634 y1_pt
= (a1y_pt
+2*a2y_pt
*t1
+3*a3y_pt
*t1
*t1
)*dt
/3.0 + y0_pt
635 x2_pt
= (a2x_pt
+3*a3x_pt
*t1
)*dt
*dt
/3.0 - x0_pt
+ 2*x1_pt
636 y2_pt
= (a2y_pt
+3*a3y_pt
*t1
)*dt
*dt
/3.0 - y0_pt
+ 2*y1_pt
637 x3_pt
= a3x_pt
*dt
*dt
*dt
+ x0_pt
- 3*x1_pt
+ 3*x2_pt
638 y3_pt
= a3y_pt
*dt
*dt
*dt
+ y0_pt
- 3*y1_pt
+ 3*y2_pt
640 result
.append(normcurve_pt(x0_pt
, y0_pt
, x1_pt
, y1_pt
, x2_pt
, y2_pt
, x3_pt
, y3_pt
))
644 def trafo(self
, params
):
646 for rotation
, at_pt
in zip(self
.rotation(params
), self
.at_pt(params
)):
647 if rotation
is invalid
:
648 result
.append(rotation
)
650 result
.append(trafo
.translate_pt(*at_pt
) * rotation
)
653 def transformed(self
, trafo
):
654 x0_pt
, y0_pt
= trafo
.apply_pt(self
.x0_pt
, self
.y0_pt
)
655 x1_pt
, y1_pt
= trafo
.apply_pt(self
.x1_pt
, self
.y1_pt
)
656 x2_pt
, y2_pt
= trafo
.apply_pt(self
.x2_pt
, self
.y2_pt
)
657 x3_pt
, y3_pt
= trafo
.apply_pt(self
.x3_pt
, self
.y3_pt
)
658 return normcurve_pt(x0_pt
, y0_pt
, x1_pt
, y1_pt
, x2_pt
, y2_pt
, x3_pt
, y3_pt
)
660 def outputPS(self
, file, writer
, context
):
661 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
))
663 def outputPDF(self
, file, writer
, context
):
664 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
))
667 ################################################################################
669 ################################################################################
673 """sub path of a normalized path
675 A subpath consists of a list of normsubpathitems, i.e., normlines_pt and
676 normcurves_pt and can either be closed or not.
678 Some invariants, which have to be obeyed:
679 - All normsubpathitems have to be longer than epsilon pts.
680 - At the end there may be a normline (stored in self.skippedline) whose
681 length is shorter than epsilon -- it has to be taken into account
682 when adding further normsubpathitems
683 - The last point of a normsubpathitem and the first point of the next
684 element have to be equal.
685 - When the path is closed, the last point of last normsubpathitem has
686 to be equal to the first point of the first normsubpathitem.
687 - epsilon might be none, disallowing any numerics, but allowing for
688 arbitrary short paths. This is used in pdf output, where all paths need
689 to be transformed to normpaths.
692 __slots__
= "normsubpathitems", "closed", "epsilon", "skippedline"
694 def __init__(self
, normsubpathitems
=[], closed
=0, epsilon
=_marker
):
695 """construct a normsubpath"""
696 if epsilon
is _marker
:
698 self
.epsilon
= epsilon
699 # If one or more items appended to the normsubpath have been
700 # skipped (because their total length was shorter than epsilon),
701 # we remember this fact by a line because we have to take it
702 # properly into account when appending further normsubpathitems
703 self
.skippedline
= None
705 self
.normsubpathitems
= []
708 # a test (might be temporary)
709 for anormsubpathitem
in normsubpathitems
:
710 assert isinstance(anormsubpathitem
, normsubpathitem
), "only list of normsubpathitem instances allowed"
712 self
.extend(normsubpathitems
)
717 def __getitem__(self
, i
):
718 """return normsubpathitem i"""
719 return self
.normsubpathitems
[i
]
722 """return number of normsubpathitems"""
723 return len(self
.normsubpathitems
)
726 l
= ", ".join(map(str, self
.normsubpathitems
))
728 return "normsubpath([%s], closed=1)" % l
730 return "normsubpath([%s])" % l
732 def _distributeparams(self
, params
):
733 """return a dictionary mapping normsubpathitemindices to a tuple
734 of a paramindices and normsubpathitemparams.
736 normsubpathitemindex specifies a normsubpathitem containing
737 one or several positions. paramindex specify the index of the
738 param in the original list and normsubpathitemparam is the
739 parameter value in the normsubpathitem.
743 for i
, param
in enumerate(params
):
746 if index
> len(self
.normsubpathitems
) - 1:
747 index
= len(self
.normsubpathitems
) - 1
750 result
.setdefault(index
, ([], []))
751 result
[index
][0].append(i
)
752 result
[index
][1].append(param
- index
)
755 def append(self
, anormsubpathitem
):
756 """append normsubpathitem
758 Fails on closed normsubpath.
760 if self
.epsilon
is None:
761 self
.normsubpathitems
.append(anormsubpathitem
)
763 # consitency tests (might be temporary)
764 assert isinstance(anormsubpathitem
, normsubpathitem
), "only normsubpathitem instances allowed"
766 assert math
.hypot(*[x
-y
for x
, y
in zip(self
.skippedline
.atend_pt(), anormsubpathitem
.atbegin_pt())]) < self
.epsilon
, "normsubpathitems do not match"
767 elif self
.normsubpathitems
:
768 assert math
.hypot(*[x
-y
for x
, y
in zip(self
.normsubpathitems
[-1].atend_pt(), anormsubpathitem
.atbegin_pt())]) < self
.epsilon
, "normsubpathitems do not match"
771 raise NormpathException("Cannot append to closed normsubpath")
774 xs_pt
, ys_pt
= self
.skippedline
.atbegin_pt()
776 xs_pt
, ys_pt
= anormsubpathitem
.atbegin_pt()
777 xe_pt
, ye_pt
= anormsubpathitem
.atend_pt()
779 if (math
.hypot(xe_pt
-xs_pt
, ye_pt
-ys_pt
) >= self
.epsilon
or
780 anormsubpathitem
.arclen_pt(self
.epsilon
) >= self
.epsilon
):
782 anormsubpathitem
= anormsubpathitem
.modifiedbegin_pt(xs_pt
, ys_pt
)
783 self
.normsubpathitems
.append(anormsubpathitem
)
784 self
.skippedline
= None
786 self
.skippedline
= normline_pt(xs_pt
, ys_pt
, xe_pt
, ye_pt
)
789 """return arc length in pts"""
790 return sum([npitem
.arclen_pt(self
.epsilon
) for npitem
in self
.normsubpathitems
])
792 def _arclentoparam_pt(self
, lengths_pt
):
793 """return a tuple of params and the total length arc length in pts"""
794 # work on a copy which is counted down to negative values
795 lengths_pt
= lengths_pt
[:]
796 results
= [None] * len(lengths_pt
)
799 for normsubpathindex
, normsubpathitem
in enumerate(self
.normsubpathitems
):
800 params
, arclen
= normsubpathitem
._arclentoparam
_pt
(lengths_pt
, self
.epsilon
)
801 for i
in range(len(results
)):
802 if results
[i
] is None:
803 lengths_pt
[i
] -= arclen
804 if lengths_pt
[i
] < 0 or normsubpathindex
== len(self
.normsubpathitems
) - 1:
805 # overwrite the results until the length has become negative
806 results
[i
] = normsubpathindex
+ params
[i
]
807 totalarclen
+= arclen
809 return results
, totalarclen
811 def arclentoparam_pt(self
, lengths_pt
):
812 """return a tuple of params"""
813 return self
._arclentoparam
_pt
(lengths_pt
)[0]
815 def at_pt(self
, params
):
816 """return coordinates at params in pts"""
817 result
= [None] * len(params
)
818 for normsubpathitemindex
, (indices
, params
) in self
._distributeparams
(params
).items():
819 for index
, point_pt
in zip(indices
, self
.normsubpathitems
[normsubpathitemindex
].at_pt(params
)):
820 result
[index
] = point_pt
823 def atbegin_pt(self
):
824 """return coordinates of first point in pts"""
825 if not self
.normsubpathitems
and self
.skippedline
:
826 return self
.skippedline
.atbegin_pt()
827 return self
.normsubpathitems
[0].atbegin_pt()
830 """return coordinates of last point in pts"""
832 return self
.skippedline
.atend_pt()
833 return self
.normsubpathitems
[-1].atend_pt()
836 """return bounding box of normsubpath"""
837 if self
.normsubpathitems
:
838 abbox
= self
.normsubpathitems
[0].bbox()
839 for anormpathitem
in self
.normsubpathitems
[1:]:
840 abbox
+= anormpathitem
.bbox()
848 Fails on closed normsubpath.
851 raise NormpathException("Cannot close already closed normsubpath")
852 if not self
.normsubpathitems
:
853 if self
.skippedline
is None:
854 raise NormpathException("Cannot close empty normsubpath")
856 raise NormpathException("Normsubpath too short, cannot be closed")
858 xs_pt
, ys_pt
= self
.normsubpathitems
[-1].atend_pt()
859 xe_pt
, ye_pt
= self
.normsubpathitems
[0].atbegin_pt()
860 self
.append(normline_pt(xs_pt
, ys_pt
, xe_pt
, ye_pt
))
861 self
.flushskippedline()
865 """return copy of normsubpath"""
866 # Since normsubpathitems are never modified inplace, we just
867 # need to copy the normsubpathitems list. We do not pass the
868 # normsubpathitems to the constructor to not repeat the checks
869 # for minimal length of each normsubpathitem.
870 result
= normsubpath(epsilon
=self
.epsilon
)
871 result
.normsubpathitems
= self
.normsubpathitems
[:]
872 result
.closed
= self
.closed
874 # We can share the reference to skippedline, since it is a
875 # normsubpathitem as well and thus not modified in place either.
876 result
.skippedline
= self
.skippedline
880 def curvature_pt(self
, params
):
881 """return the curvature at params in 1/pts
883 The result contain the invalid instance at positions, where the
884 curvature is undefined."""
885 result
= [None] * len(params
)
886 for normsubpathitemindex
, (indices
, params
) in self
._distributeparams
(params
).items():
887 for index
, curvature_pt
in zip(indices
, self
.normsubpathitems
[normsubpathitemindex
].curvature_pt(params
)):
888 result
[index
] = curvature_pt
891 def curveradius_pt(self
, params
):
892 """return the curvature radius at params in pts
894 The curvature radius is the inverse of the curvature. When the
895 curvature is 0, None is returned. Note that this radius can be negative
896 or positive, depending on the sign of the curvature."""
897 result
= [None] * len(params
)
898 for normsubpathitemindex
, (indices
, params
) in self
._distributeparams
(params
).items():
899 for index
, radius_pt
in zip(indices
, self
.normsubpathitems
[normsubpathitemindex
].curveradius_pt(params
)):
900 result
[index
] = radius_pt
903 def extend(self
, normsubpathitems
):
904 """extend path by normsubpathitems
906 Fails on closed normsubpath.
908 for normsubpathitem
in normsubpathitems
:
909 self
.append(normsubpathitem
)
911 def flushskippedline(self
):
912 """flush the skippedline, i.e. apply it to the normsubpath
914 remove the skippedline by modifying the end point of the existing normsubpath
916 while self
.skippedline
:
918 lastnormsubpathitem
= self
.normsubpathitems
.pop()
920 raise ValueError("normsubpath too short to flush the skippedline")
921 lastnormsubpathitem
= lastnormsubpathitem
.modifiedend_pt(*self
.skippedline
.atend_pt())
922 self
.skippedline
= None
923 self
.append(lastnormsubpathitem
)
925 def intersect(self
, other
):
926 """intersect self with other normsubpath
928 Returns a tuple of lists consisting of the parameter values
929 of the intersection points of the corresponding normsubpath.
933 epsilon
= min(self
.epsilon
, other
.epsilon
)
934 # Intersect all subpaths of self with the subpaths of other, possibly including
935 # one intersection point several times
936 for t_a
, pitem_a
in enumerate(self
.normsubpathitems
):
937 for t_b
, pitem_b
in enumerate(other
.normsubpathitems
):
938 for intersection_a
, intersection_b
in pitem_a
.intersect(pitem_b
, epsilon
):
939 intersections_a
.append(intersection_a
+ t_a
)
940 intersections_b
.append(intersection_b
+ t_b
)
942 # although intersectipns_a are sorted for the different normsubpathitems,
943 # within a normsubpathitem, the ordering has to be ensured separately:
944 intersections
= zip(intersections_a
, intersections_b
)
946 intersections_a
= [a
for a
, b
in intersections
]
947 intersections_b
= [b
for a
, b
in intersections
]
949 # for symmetry reasons we enumerate intersections_a as well, although
950 # they are already sorted (note we do not need to sort intersections_a)
951 intersections_a
= zip(intersections_a
, range(len(intersections_a
)))
952 intersections_b
= zip(intersections_b
, range(len(intersections_b
)))
953 intersections_b
.sort()
955 # now we search for intersections points which are closer together than epsilon
956 # This task is handled by the following function
957 def closepoints(normsubpath
, intersections
):
958 split
= normsubpath
.segments([0] + [intersection
for intersection
, index
in intersections
] + [len(normsubpath
)])
960 if normsubpath
.closed
:
961 # note that the number of segments of a closed path is off by one
962 # compared to an open path
964 while i
< len(split
):
965 splitnormsubpath
= split
[i
]
967 while not splitnormsubpath
.normsubpathitems
: # i.e. while "is short"
968 ip1
, ip2
= intersections
[i
-1][1], intersections
[j
][1]
970 result
.append((ip1
, ip2
))
972 result
.append((ip2
, ip1
))
977 splitnormsubpath
= splitnormsubpath
.joined(split
[j
])
983 while i
< len(split
)-1:
984 splitnormsubpath
= split
[i
]
986 while not splitnormsubpath
.normsubpathitems
: # i.e. while "is short"
987 ip1
, ip2
= intersections
[i
-1][1], intersections
[j
][1]
989 result
.append((ip1
, ip2
))
991 result
.append((ip2
, ip1
))
994 splitnormsubpath
= splitnormsubpath
.joined(split
[j
])
1000 closepoints_a
= closepoints(self
, intersections_a
)
1001 closepoints_b
= closepoints(other
, intersections_b
)
1003 # map intersection point to lowest point which is equivalent to the
1005 equivalentpoints
= list(range(len(intersections_a
)))
1007 for closepoint_a
in closepoints_a
:
1008 for closepoint_b
in closepoints_b
:
1009 if closepoint_a
== closepoint_b
:
1010 for i
in range(closepoint_a
[1], len(equivalentpoints
)):
1011 if equivalentpoints
[i
] == closepoint_a
[1]:
1012 equivalentpoints
[i
] = closepoint_a
[0]
1014 # determine the remaining intersection points
1015 intersectionpoints
= {}
1016 for point
in equivalentpoints
:
1017 intersectionpoints
[point
] = 1
1021 intersectionpointskeys
= intersectionpoints
.keys()
1022 intersectionpointskeys
.sort()
1023 for point
in intersectionpointskeys
:
1024 for intersection_a
, index_a
in intersections_a
:
1025 if index_a
== point
:
1026 result_a
= intersection_a
1027 for intersection_b
, index_b
in intersections_b
:
1028 if index_b
== point
:
1029 result_b
= intersection_b
1030 result
.append((result_a
, result_b
))
1031 # note that the result is sorted in a, since we sorted
1032 # intersections_a in the very beginning
1034 return [x
for x
, y
in result
], [y
for x
, y
in result
]
1036 def join(self
, other
):
1037 """join other normsubpath inplace
1039 Fails on closed normsubpath. Fails to join closed normsubpath.
1042 raise NormpathException("Cannot join closed normsubpath")
1044 # insert connection line
1045 x0_pt
, y0_pt
= self
.atend_pt()
1046 x1_pt
, y1_pt
= other
.atbegin_pt()
1047 self
.append(normline_pt(x0_pt
, y0_pt
, x1_pt
, y1_pt
))
1049 # append other normsubpathitems
1050 self
.extend(other
.normsubpathitems
)
1051 if other
.skippedline
:
1052 self
.append(other
.skippedline
)
1054 def joined(self
, other
):
1055 """return joined self and other
1057 Fails on closed normsubpath. Fails to join closed normsubpath.
1059 result
= self
.copy()
1063 def _paramtoarclen_pt(self
, params
):
1064 """return a tuple of arc lengths and the total arc length in pts"""
1065 result
= [None] * len(params
)
1067 distributeparams
= self
._distributeparams
(params
)
1068 for normsubpathitemindex
in range(len(self
.normsubpathitems
)):
1069 if distributeparams
.has_key(normsubpathitemindex
):
1070 indices
, params
= distributeparams
[normsubpathitemindex
]
1071 arclens_pt
, normsubpathitemarclen_pt
= self
.normsubpathitems
[normsubpathitemindex
]._paramtoarclen
_pt
(params
, self
.epsilon
)
1072 for index
, arclen_pt
in zip(indices
, arclens_pt
):
1073 result
[index
] = totalarclen_pt
+ arclen_pt
1074 totalarclen_pt
+= normsubpathitemarclen_pt
1076 totalarclen_pt
+= self
.normsubpathitems
[normsubpathitemindex
].arclen_pt(self
.epsilon
)
1077 return result
, totalarclen_pt
1079 def pathitems(self
):
1080 """return list of pathitems"""
1081 if not self
.normsubpathitems
:
1084 # remove trailing normline_pt of closed subpaths
1085 if self
.closed
and isinstance(self
.normsubpathitems
[-1], normline_pt
):
1086 normsubpathitems
= self
.normsubpathitems
[:-1]
1088 normsubpathitems
= self
.normsubpathitems
1090 result
= [path
.moveto_pt(*self
.atbegin_pt())]
1091 for normsubpathitem
in normsubpathitems
:
1092 result
.append(normsubpathitem
.pathitem())
1094 result
.append(path
.closepath())
1098 """return reversed normsubpath"""
1100 for i
in range(len(self
.normsubpathitems
)):
1101 nnormpathitems
.append(self
.normsubpathitems
[-(i
+1)].reversed())
1102 return normsubpath(nnormpathitems
, self
.closed
, self
.epsilon
)
1104 def rotation(self
, params
):
1105 """return rotations at params"""
1106 result
= [None] * len(params
)
1107 for normsubpathitemindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1108 for index
, rotation
in zip(indices
, self
.normsubpathitems
[normsubpathitemindex
].rotation(params
)):
1109 result
[index
] = rotation
1112 def segments(self
, params
):
1113 """return segments of the normsubpath
1115 The returned list of normsubpaths for the segments between
1116 the params. params need to contain at least two values.
1118 For a closed normsubpath the last segment result is joined to
1119 the first one when params starts with 0 and ends with len(self).
1120 or params starts with len(self) and ends with 0. Thus a segments
1121 operation on a closed normsubpath might properly join those the
1122 first and the last part to take into account the closed nature of
1123 the normsubpath. However, for intermediate parameters, closepath
1124 is not taken into account, i.e. when walking backwards you do not
1125 loop over the closepath forwardly. The special values 0 and
1126 len(self) for the first and the last parameter should be given as
1127 integers, i.e. no finite precision is used when checking for
1131 raise ValueError("at least two parameters needed in segments")
1133 result
= [normsubpath(epsilon
=self
.epsilon
)]
1135 # instead of distribute the parameters, we need to keep their
1136 # order and collect parameters for the needed segments of
1137 # normsubpathitem with index collectindex
1140 for param
in params
:
1141 # calculate index and parameter for corresponding normsubpathitem
1144 if index
> len(self
.normsubpathitems
) - 1:
1145 index
= len(self
.normsubpathitems
) - 1
1149 if index
!= collectindex
:
1150 if collectindex
is not None:
1151 # append end point depening on the forthcoming index
1152 if index
> collectindex
:
1153 collectparams
.append(1)
1155 collectparams
.append(0)
1156 # get segments of the normsubpathitem and add them to the result
1157 segments
= self
.normsubpathitems
[collectindex
].segments(collectparams
)
1158 result
[-1].append(segments
[0])
1159 result
.extend([normsubpath([segment
], epsilon
=self
.epsilon
) for segment
in segments
[1:]])
1160 # add normsubpathitems and first segment parameter to close the
1161 # gap to the forthcoming index
1162 if index
> collectindex
:
1163 for i
in range(collectindex
+1, index
):
1164 result
[-1].append(self
.normsubpathitems
[i
])
1167 for i
in range(collectindex
-1, index
, -1):
1168 result
[-1].append(self
.normsubpathitems
[i
].reversed())
1170 collectindex
= index
1171 collectparams
.append(param
)
1172 # add remaining collectparams to the result
1173 segments
= self
.normsubpathitems
[collectindex
].segments(collectparams
)
1174 result
[-1].append(segments
[0])
1175 result
.extend([normsubpath([segment
], epsilon
=self
.epsilon
) for segment
in segments
[1:]])
1178 # join last and first segment together if the normsubpath was
1179 # originally closed and first and the last parameters are the
1180 # beginning and end points of the normsubpath
1181 if ( ( params
[0] == 0 and params
[-1] == len(self
.normsubpathitems
) ) or
1182 ( params
[-1] == 0 and params
[0] == len(self
.normsubpathitems
) ) ):
1183 result
[-1].normsubpathitems
.extend(result
[0].normsubpathitems
)
1184 result
= result
[-1:] + result
[1:-1]
1188 def trafo(self
, params
):
1189 """return transformations at params"""
1190 result
= [None] * len(params
)
1191 for normsubpathitemindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1192 for index
, trafo
in zip(indices
, self
.normsubpathitems
[normsubpathitemindex
].trafo(params
)):
1193 result
[index
] = trafo
1196 def transformed(self
, trafo
):
1197 """return transformed path"""
1198 nnormsubpath
= normsubpath(epsilon
=self
.epsilon
)
1199 for pitem
in self
.normsubpathitems
:
1200 nnormsubpath
.append(pitem
.transformed(trafo
))
1202 nnormsubpath
.close()
1203 elif self
.skippedline
is not None:
1204 nnormsubpath
.append(self
.skippedline
.transformed(trafo
))
1207 def outputPS(self
, file, writer
, context
):
1208 # if the normsubpath is closed, we must not output a normline at
1210 if not self
.normsubpathitems
:
1212 if self
.closed
and isinstance(self
.normsubpathitems
[-1], normline_pt
):
1213 assert len(self
.normsubpathitems
) > 1, "a closed normsubpath should contain more than a single normline_pt"
1214 normsubpathitems
= self
.normsubpathitems
[:-1]
1216 normsubpathitems
= self
.normsubpathitems
1217 file.write("%g %g moveto\n" % self
.atbegin_pt())
1218 for anormsubpathitem
in normsubpathitems
:
1219 anormsubpathitem
.outputPS(file, writer
, context
)
1221 file.write("closepath\n")
1223 def outputPDF(self
, file, writer
, context
):
1224 # if the normsubpath is closed, we must not output a normline at
1226 if not self
.normsubpathitems
:
1228 if self
.closed
and isinstance(self
.normsubpathitems
[-1], normline_pt
):
1229 assert len(self
.normsubpathitems
) > 1, "a closed normsubpath should contain more than a single normline_pt"
1230 normsubpathitems
= self
.normsubpathitems
[:-1]
1232 normsubpathitems
= self
.normsubpathitems
1233 file.write("%f %f m\n" % self
.atbegin_pt())
1234 for anormsubpathitem
in normsubpathitems
:
1235 anormsubpathitem
.outputPDF(file, writer
, context
)
1240 ################################################################################
1242 ################################################################################
1244 class normpathparam
:
1246 """parameter of a certain point along a normpath"""
1248 __slots__
= "normpath", "normsubpathindex", "normsubpathparam"
1250 def __init__(self
, normpath
, normsubpathindex
, normsubpathparam
):
1251 self
.normpath
= normpath
1252 self
.normsubpathindex
= normsubpathindex
1253 self
.normsubpathparam
= normsubpathparam
1254 float(normsubpathparam
)
1257 return "normpathparam(%s, %s, %s)" % (self
.normpath
, self
.normsubpathindex
, self
.normsubpathparam
)
1259 def __add__(self
, other
):
1260 if isinstance(other
, normpathparam
):
1261 assert self
.normpath
is other
.normpath
, "normpathparams have to belong to the same normpath"
1262 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) +
1263 other
.normpath
.paramtoarclen_pt(other
))
1265 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) + unit
.topt(other
))
1269 def __sub__(self
, other
):
1270 if isinstance(other
, normpathparam
):
1271 assert self
.normpath
is other
.normpath
, "normpathparams have to belong to the same normpath"
1272 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) -
1273 other
.normpath
.paramtoarclen_pt(other
))
1275 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) - unit
.topt(other
))
1277 def __rsub__(self
, other
):
1278 # other has to be a length in this case
1279 return self
.normpath
.arclentoparam_pt(-self
.normpath
.paramtoarclen_pt(self
) + unit
.topt(other
))
1281 def __mul__(self
, factor
):
1282 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) * factor
)
1286 def __div__(self
, divisor
):
1287 return self
.normpath
.arclentoparam_pt(self
.normpath
.paramtoarclen_pt(self
) / divisor
)
1290 return self
.normpath
.arclentoparam_pt(-self
.normpath
.paramtoarclen_pt(self
))
1292 def __cmp__(self
, other
):
1293 if isinstance(other
, normpathparam
):
1294 assert self
.normpath
is other
.normpath
, "normpathparams have to belong to the same normpath"
1295 return cmp((self
.normsubpathindex
, self
.normsubpathparam
), (other
.normsubpathindex
, other
.normsubpathparam
))
1297 return cmp(self
.normpath
.paramtoarclen_pt(self
), unit
.topt(other
))
1299 def arclen_pt(self
):
1300 """return arc length in pts corresponding to the normpathparam """
1301 return self
.normpath
.paramtoarclen_pt(self
)
1304 """return arc length corresponding to the normpathparam """
1305 return self
.normpath
.paramtoarclen(self
)
1308 def _valueorlistmethod(method
):
1309 """Creates a method which takes a single argument or a list and
1310 returns a single value or a list out of method, which always
1313 def wrappedmethod(self
, valueorlist
, *args
, **kwargs
):
1315 for item
in valueorlist
:
1318 return method(self
, [valueorlist
], *args
, **kwargs
)[0]
1319 return method(self
, valueorlist
, *args
, **kwargs
)
1320 return wrappedmethod
1323 class normpath(canvas
.canvasitem
):
1327 A normalized path consists of a list of normsubpaths.
1330 def __init__(self
, normsubpaths
=None):
1331 """construct a normpath from a list of normsubpaths"""
1333 if normsubpaths
is None:
1334 self
.normsubpaths
= [] # make a fresh list
1336 self
.normsubpaths
= normsubpaths
1337 for subpath
in normsubpaths
:
1338 assert isinstance(subpath
, normsubpath
), "only list of normsubpath instances allowed"
1340 def __add__(self
, other
):
1341 """create new normpath out of self and other"""
1342 result
= self
.copy()
1346 def __iadd__(self
, other
):
1347 """add other inplace"""
1348 for normsubpath
in other
.normpath().normsubpaths
:
1349 self
.normsubpaths
.append(normsubpath
.copy())
1352 def __getitem__(self
, i
):
1353 """return normsubpath i"""
1354 return self
.normsubpaths
[i
]
1357 """return the number of normsubpaths"""
1358 return len(self
.normsubpaths
)
1361 return "normpath([%s])" % ", ".join(map(str, self
.normsubpaths
))
1363 def _convertparams(self
, params
, convertmethod
):
1364 """return params with all non-normpathparam arguments converted by convertmethod
1367 - self._convertparams(params, self.arclentoparam_pt)
1368 - self._convertparams(params, self.arclentoparam)
1371 converttoparams
= []
1372 convertparamindices
= []
1373 for i
, param
in enumerate(params
):
1374 if not isinstance(param
, normpathparam
):
1375 converttoparams
.append(param
)
1376 convertparamindices
.append(i
)
1379 for i
, param
in zip(convertparamindices
, convertmethod(converttoparams
)):
1383 def _distributeparams(self
, params
):
1384 """return a dictionary mapping subpathindices to a tuple of a paramindices and subpathparams
1386 subpathindex specifies a subpath containing one or several positions.
1387 paramindex specify the index of the normpathparam in the original list and
1388 subpathparam is the parameter value in the subpath.
1392 for i
, param
in enumerate(params
):
1393 assert param
.normpath
is self
, "normpathparam has to belong to this path"
1394 result
.setdefault(param
.normsubpathindex
, ([], []))
1395 result
[param
.normsubpathindex
][0].append(i
)
1396 result
[param
.normsubpathindex
][1].append(param
.normsubpathparam
)
1399 def append(self
, item
):
1400 """append a normsubpath by a normsubpath or a pathitem"""
1401 if isinstance(item
, normsubpath
):
1402 # the normsubpaths list can be appended by a normsubpath only
1403 self
.normsubpaths
.append(item
)
1404 elif isinstance(item
, path
.pathitem
):
1405 # ... but we are kind and allow for regular path items as well
1406 # in order to make a normpath to behave more like a regular path
1407 context
= path
.context(*(self
.normsubpaths
[-1].atend_pt() +
1408 self
.normsubpaths
[-1].atbegin_pt()))
1409 item
.updatenormpath(self
, context
)
1411 def arclen_pt(self
):
1412 """return arc length in pts"""
1413 return sum([normsubpath
.arclen_pt() for normsubpath
in self
.normsubpaths
])
1416 """return arc length"""
1417 return self
.arclen_pt() * unit
.t_pt
1419 def _arclentoparam_pt(self
, lengths_pt
):
1420 """return the params matching the given lengths_pt"""
1421 # work on a copy which is counted down to negative values
1422 lengths_pt
= lengths_pt
[:]
1423 results
= [None] * len(lengths_pt
)
1425 for normsubpathindex
, normsubpath
in enumerate(self
.normsubpaths
):
1426 params
, arclen
= normsubpath
._arclentoparam
_pt
(lengths_pt
)
1428 for i
, result
in enumerate(results
):
1429 if results
[i
] is None:
1430 lengths_pt
[i
] -= arclen
1431 if lengths_pt
[i
] < 0 or normsubpathindex
== len(self
.normsubpaths
) - 1:
1432 # overwrite the results until the length has become negative
1433 results
[i
] = normpathparam(self
, normsubpathindex
, params
[i
])
1440 def arclentoparam_pt(self
, lengths_pt
):
1441 """return the param(s) matching the given length(s)_pt in pts"""
1443 arclentoparam_pt
= _valueorlistmethod(_arclentoparam_pt
)
1445 def arclentoparam(self
, lengths
):
1446 """return the param(s) matching the given length(s)"""
1447 return self
._arclentoparam
_pt
([unit
.topt(l
) for l
in lengths
])
1448 arclentoparam
= _valueorlistmethod(arclentoparam
)
1450 def _at_pt(self
, params
):
1451 """return coordinates of normpath in pts at params"""
1452 result
= [None] * len(params
)
1453 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1454 for index
, point_pt
in zip(indices
, self
.normsubpaths
[normsubpathindex
].at_pt(params
)):
1455 result
[index
] = point_pt
1458 def at_pt(self
, params
):
1459 """return coordinates of normpath in pts at param(s) or lengths in pts"""
1460 return self
._at
_pt
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1461 at_pt
= _valueorlistmethod(at_pt
)
1463 def at(self
, params
):
1464 """return coordinates of normpath at param(s) or arc lengths"""
1465 return [(x_pt
* unit
.t_pt
, y_pt
* unit
.t_pt
)
1466 for x_pt
, y_pt
in self
._at
_pt
(self
._convertparams
(params
, self
.arclentoparam
))]
1467 at
= _valueorlistmethod(at
)
1469 def atbegin_pt(self
):
1470 """return coordinates of the beginning of first subpath in normpath in pts"""
1471 if self
.normsubpaths
:
1472 return self
.normsubpaths
[0].atbegin_pt()
1474 raise NormpathException("cannot return first point of empty path")
1477 """return coordinates of the beginning of first subpath in normpath"""
1478 x
, y
= self
.atbegin_pt()
1479 return x
* unit
.t_pt
, y
* unit
.t_pt
1482 """return coordinates of the end of last subpath in normpath in pts"""
1483 if self
.normsubpaths
:
1484 return self
.normsubpaths
[-1].atend_pt()
1486 raise NormpathException("cannot return last point of empty path")
1489 """return coordinates of the end of last subpath in normpath"""
1490 x
, y
= self
.atend_pt()
1491 return x
* unit
.t_pt
, y
* unit
.t_pt
1494 """return bbox of normpath"""
1496 for normsubpath
in self
.normsubpaths
:
1497 nbbox
= normsubpath
.bbox()
1505 """return param corresponding of the beginning of the normpath"""
1506 if self
.normsubpaths
:
1507 return normpathparam(self
, 0, 0)
1509 raise NormpathException("empty path")
1512 """return copy of normpath"""
1514 for normsubpath
in self
.normsubpaths
:
1515 result
.append(normsubpath
.copy())
1518 def _curvature_pt(self
, params
):
1519 """return the curvature in 1/pts at params in pts
1521 The curvature radius is the inverse of the curvature. When the
1522 curvature is 0, None is returned. Note that this radius can be negative
1523 or positive, depending on the sign of the curvature."""
1525 result
= [None] * len(params
)
1526 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1527 for index
, curvature_pt
in zip(indices
, self
.normsubpaths
[normsubpathindex
].curvature_pt(params
)):
1528 result
[index
] = curvature_pt
1531 def curvature_pt(self
, params
):
1532 """return the curvature in 1/pt at param(s) or arc length(s) in pts
1534 The curvature radius is the inverse of the curvature. When the
1535 curvature is 0, None is returned. Note that this radius can be negative
1536 or positive, depending on the sign of the curvature."""
1538 return self
._curveradius
_pt
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1539 curvature_pt
= _valueorlistmethod(curvature_pt
)
1541 def _curveradius_pt(self
, params
):
1542 """return the curvature radius at params in pts
1544 The curvature radius is the inverse of the curvature. When the
1545 curvature is 0, None is returned. Note that this radius can be negative
1546 or positive, depending on the sign of the curvature."""
1548 result
= [None] * len(params
)
1549 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1550 for index
, radius_pt
in zip(indices
, self
.normsubpaths
[normsubpathindex
].curveradius_pt(params
)):
1551 result
[index
] = radius_pt
1554 def curveradius_pt(self
, params
):
1555 """return the curvature radius in pts at param(s) or arc length(s) in pts
1557 The curvature radius is the inverse of the curvature. When the
1558 curvature is 0, None is returned. Note that this radius can be negative
1559 or positive, depending on the sign of the curvature."""
1561 return self
._curveradius
_pt
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1562 curveradius_pt
= _valueorlistmethod(curveradius_pt
)
1564 def curveradius(self
, params
):
1565 """return the curvature radius at param(s) or arc length(s)
1567 The curvature radius is the inverse of the curvature. When the
1568 curvature is 0, None is returned. Note that this radius can be negative
1569 or positive, depending on the sign of the curvature."""
1572 for radius_pt
in self
._curveradius
_pt
(self
._convertparams
(params
, self
.arclentoparam
)):
1573 if radius_pt
is not None:
1574 result
.append(radius_pt
* unit
.t_pt
)
1578 curveradius
= _valueorlistmethod(curveradius
)
1581 """return param corresponding of the end of the path"""
1582 if self
.normsubpaths
:
1583 return normpathparam(self
, len(self
)-1, len(self
.normsubpaths
[-1]))
1585 raise NormpathException("empty path")
1587 def extend(self
, normsubpaths
):
1588 """extend path by normsubpaths or pathitems"""
1589 for anormsubpath
in normsubpaths
:
1590 # use append to properly handle regular path items as well as normsubpaths
1591 self
.append(anormsubpath
)
1593 def intersect(self
, other
):
1594 """intersect self with other path
1596 Returns a tuple of lists consisting of the parameter values
1597 of the intersection points of the corresponding normpath.
1599 other
= other
.normpath()
1601 # here we build up the result
1602 intersections
= ([], [])
1604 # Intersect all normsubpaths of self with the normsubpaths of
1606 for ia
, normsubpath_a
in enumerate(self
.normsubpaths
):
1607 for ib
, normsubpath_b
in enumerate(other
.normsubpaths
):
1608 for intersection
in zip(*normsubpath_a
.intersect(normsubpath_b
)):
1609 intersections
[0].append(normpathparam(self
, ia
, intersection
[0]))
1610 intersections
[1].append(normpathparam(other
, ib
, intersection
[1]))
1611 return intersections
1613 def join(self
, other
):
1614 """join other normsubpath inplace
1616 Both normpaths must contain at least one normsubpath.
1617 The last normsubpath of self will be joined to the first
1618 normsubpath of other.
1620 if not self
.normsubpaths
:
1621 raise NormpathException("cannot join to empty path")
1622 if not other
.normsubpaths
:
1623 raise PathException("cannot join empty path")
1624 self
.normsubpaths
[-1].join(other
.normsubpaths
[0])
1625 self
.normsubpaths
.extend(other
.normsubpaths
[1:])
1627 def joined(self
, other
):
1628 """return joined self and other
1630 Both normpaths must contain at least one normsubpath.
1631 The last normsubpath of self will be joined to the first
1632 normsubpath of other.
1634 result
= self
.copy()
1635 result
.join(other
.normpath())
1638 # << operator also designates joining
1642 """return a normpath, i.e. self"""
1645 def _paramtoarclen_pt(self
, params
):
1646 """return arc lengths in pts matching the given params"""
1647 result
= [None] * len(params
)
1649 distributeparams
= self
._distributeparams
(params
)
1650 for normsubpathindex
in range(max(distributeparams
.keys()) + 1):
1651 if distributeparams
.has_key(normsubpathindex
):
1652 indices
, params
= distributeparams
[normsubpathindex
]
1653 arclens_pt
, normsubpatharclen_pt
= self
.normsubpaths
[normsubpathindex
]._paramtoarclen
_pt
(params
)
1654 for index
, arclen_pt
in zip(indices
, arclens_pt
):
1655 result
[index
] = totalarclen_pt
+ arclen_pt
1656 totalarclen_pt
+= normsubpatharclen_pt
1658 totalarclen_pt
+= self
.normsubpaths
[normsubpathindex
].arclen_pt()
1661 def paramtoarclen_pt(self
, params
):
1662 """return arc length(s) in pts matching the given param(s)"""
1663 paramtoarclen_pt
= _valueorlistmethod(_paramtoarclen_pt
)
1665 def paramtoarclen(self
, params
):
1666 """return arc length(s) matching the given param(s)"""
1667 return [arclen_pt
* unit
.t_pt
for arclen_pt
in self
._paramtoarclen
_pt
(params
)]
1668 paramtoarclen
= _valueorlistmethod(paramtoarclen
)
1671 """return path corresponding to normpath"""
1673 for normsubpath
in self
.normsubpaths
:
1674 pathitems
.extend(normsubpath
.pathitems())
1675 return path
.path(*pathitems
)
1678 """return reversed path"""
1679 nnormpath
= normpath()
1680 for i
in range(len(self
.normsubpaths
)):
1681 nnormpath
.normsubpaths
.append(self
.normsubpaths
[-(i
+1)].reversed())
1684 def _rotation(self
, params
):
1685 """return rotation at params"""
1686 result
= [None] * len(params
)
1687 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1688 for index
, rotation
in zip(indices
, self
.normsubpaths
[normsubpathindex
].rotation(params
)):
1689 result
[index
] = rotation
1692 def rotation_pt(self
, params
):
1693 """return rotation at param(s) or arc length(s) in pts"""
1694 return self
._rotation
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1695 rotation_pt
= _valueorlistmethod(rotation_pt
)
1697 def rotation(self
, params
):
1698 """return rotation at param(s) or arc length(s)"""
1699 return self
._rotation
(self
._convertparams
(params
, self
.arclentoparam
))
1700 rotation
= _valueorlistmethod(rotation
)
1702 def _split_pt(self
, params
):
1703 """split path at params and return list of normpaths"""
1705 # instead of distributing the parameters, we need to keep their
1706 # order and collect parameters for splitting of normsubpathitem
1707 # with index collectindex
1709 for param
in params
:
1710 if param
.normsubpathindex
!= collectindex
:
1711 if collectindex
is not None:
1712 # append end point depening on the forthcoming index
1713 if param
.normsubpathindex
> collectindex
:
1714 collectparams
.append(len(self
.normsubpaths
[collectindex
]))
1716 collectparams
.append(0)
1717 # get segments of the normsubpath and add them to the result
1718 segments
= self
.normsubpaths
[collectindex
].segments(collectparams
)
1719 result
[-1].append(segments
[0])
1720 result
.extend([normpath([segment
]) for segment
in segments
[1:]])
1721 # add normsubpathitems and first segment parameter to close the
1722 # gap to the forthcoming index
1723 if param
.normsubpathindex
> collectindex
:
1724 for i
in range(collectindex
+1, param
.normsubpathindex
):
1725 result
[-1].append(self
.normsubpaths
[i
])
1728 for i
in range(collectindex
-1, param
.normsubpathindex
, -1):
1729 result
[-1].append(self
.normsubpaths
[i
].reversed())
1730 collectparams
= [len(self
.normsubpaths
[param
.normsubpathindex
])]
1732 result
= [normpath(self
.normsubpaths
[:param
.normsubpathindex
])]
1734 collectindex
= param
.normsubpathindex
1735 collectparams
.append(param
.normsubpathparam
)
1736 # add remaining collectparams to the result
1737 collectparams
.append(len(self
.normsubpaths
[collectindex
]))
1738 segments
= self
.normsubpaths
[collectindex
].segments(collectparams
)
1739 result
[-1].append(segments
[0])
1740 result
.extend([normpath([segment
]) for segment
in segments
[1:]])
1741 result
[-1].extend(self
.normsubpaths
[collectindex
+1:])
1744 def split_pt(self
, params
):
1745 """split path at param(s) or arc length(s) in pts and return list of normpaths"""
1747 for param
in params
:
1751 return self
._split
_pt
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1753 def split(self
, params
):
1754 """split path at param(s) or arc length(s) and return list of normpaths"""
1756 for param
in params
:
1760 return self
._split
_pt
(self
._convertparams
(params
, self
.arclentoparam
))
1762 def _tangent(self
, params
, length_pt
):
1763 """return tangent vector of path at params
1765 If length_pt in pts is not None, the tangent vector will be scaled to
1769 result
= [None] * len(params
)
1770 tangenttemplate
= path
.line_pt(0, 0, length_pt
, 0).normpath()
1771 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1772 for index
, atrafo
in zip(indices
, self
.normsubpaths
[normsubpathindex
].trafo(params
)):
1773 if atrafo
is invalid
:
1774 result
[index
] = invalid
1776 result
[index
] = tangenttemplate
.transformed(atrafo
)
1779 def tangent_pt(self
, params
, length_pt
):
1780 """return tangent vector of path at param(s) or arc length(s) in pts
1782 If length in pts is not None, the tangent vector will be scaled to
1785 return self
._tangent
(self
._convertparams
(params
, self
.arclentoparam_pt
), length_pt
)
1786 tangent_pt
= _valueorlistmethod(tangent_pt
)
1788 def tangent(self
, params
, length
):
1789 """return tangent vector of path at param(s) or arc length(s)
1791 If length is not None, the tangent vector will be scaled to
1794 return self
._tangent
(self
._convertparams
(params
, self
.arclentoparam
), unit
.topt(length
))
1795 tangent
= _valueorlistmethod(tangent
)
1797 def _trafo(self
, params
):
1798 """return transformation at params"""
1799 result
= [None] * len(params
)
1800 for normsubpathindex
, (indices
, params
) in self
._distributeparams
(params
).items():
1801 for index
, trafo
in zip(indices
, self
.normsubpaths
[normsubpathindex
].trafo(params
)):
1802 result
[index
] = trafo
1805 def trafo_pt(self
, params
):
1806 """return transformation at param(s) or arc length(s) in pts"""
1807 return self
._trafo
(self
._convertparams
(params
, self
.arclentoparam_pt
))
1808 trafo_pt
= _valueorlistmethod(trafo_pt
)
1810 def trafo(self
, params
):
1811 """return transformation at param(s) or arc length(s)"""
1812 return self
._trafo
(self
._convertparams
(params
, self
.arclentoparam
))
1813 trafo
= _valueorlistmethod(trafo
)
1815 def transformed(self
, trafo
):
1816 """return transformed normpath"""
1817 return normpath([normsubpath
.transformed(trafo
) for normsubpath
in self
.normsubpaths
])
1819 def outputPS(self
, file, writer
, context
):
1820 for normsubpath
in self
.normsubpaths
:
1821 normsubpath
.outputPS(file, writer
, context
)
1823 def outputPDF(self
, file, writer
, context
):
1824 for normsubpath
in self
.normsubpaths
:
1825 normsubpath
.outputPDF(file, writer
, context
)