1# -*- encoding: utf-8 -*- 2# 3# 4# Copyright (C) 2002-2011 Jörg Lehmann <joerg@pyx-project.org> 5# Copyright (C) 2003-2013 Michael Schindler <m-schindler@users.sourceforge.net> 6# Copyright (C) 2002-2013 André Wobst <wobsta@pyx-project.org> 7# 8# This file is part of PyX (https://pyx-project.org/). 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 23 24import math, functools 25from . import mathutils, trafo, unit 26from . import bbox as bboxmodule 27 28 29class _marker: pass 30 31# specific exception for normpath-related problems 32class NormpathException(Exception): pass 33 34# global epsilon (default precision of normsubpaths) 35_epsilon = 1e-5 36 37def set(epsilon=None): 38 global _epsilon 39 if epsilon is not None: 40 _epsilon = epsilon 41 42 43################################################################################ 44# normsubpathitems 45################################################################################ 46 47class normsubpathitem: 48 49 """element of a normalized sub path 50 51 Various operations on normsubpathitems might be subject of 52 approximitions. Those methods get the finite precision epsilon, 53 which is the accuracy needed expressed as a length in pts. 54 55 normsubpathitems should never be modified inplace, since references 56 might be shared between several normsubpaths. 57 """ 58 59 def arclen_pt(self, epsilon, upper=False): 60 """return arc length in pts 61 62 When upper is set, the upper bound is calculated, otherwise the lower 63 bound is returned.""" 64 pass 65 66 def _arclentoparam_pt(self, lengths_pt, epsilon): 67 """return a tuple of params and the total length arc length in pts""" 68 pass 69 70 def arclentoparam_pt(self, lengths_pt, epsilon): 71 """return a tuple of params""" 72 pass 73 74 def at_pt(self, params): 75 """return coordinates at params in pts""" 76 pass 77 78 def atbegin_pt(self): 79 """return coordinates of first point in pts""" 80 pass 81 82 def atend_pt(self): 83 """return coordinates of last point in pts""" 84 pass 85 86 def bbox(self): 87 """return bounding box of normsubpathitem""" 88 pass 89 90 def cbox(self): 91 """return control box of normsubpathitem 92 93 The control box also fully encloses the normsubpathitem but in the case of a Bezier 94 curve it is not the minimal box doing so. On the other hand, it is much faster 95 to calculate. 96 """ 97 pass 98 99 def curvature_pt(self, params): 100 """return the curvature at params in 1/pts""" 101 pass 102 103 def intersect(self, other, epsilon): 104 """intersect self with other normsubpathitem""" 105 pass 106 107 def modifiedbegin_pt(self, x_pt, y_pt): 108 """return a normsubpathitem with a modified beginning point""" 109 pass 110 111 def modifiedend_pt(self, x_pt, y_pt): 112 """return a normsubpathitem with a modified end point""" 113 pass 114 115 def _paramtoarclen_pt(self, param, epsilon): 116 """return a tuple of arc lengths and the total arc length in pts""" 117 pass 118 119 def pathitem(self): 120 """return pathitem corresponding to normsubpathitem""" 121 122 def reversed(self): 123 """return reversed normsubpathitem""" 124 pass 125 126 def rotation(self, params): 127 """return rotation trafos (i.e. trafos without translations) at params""" 128 pass 129 130 def segments(self, params): 131 """return segments of the normsubpathitem 132 133 The returned list of normsubpathitems for the segments between 134 the params. params needs to contain at least two values. 135 """ 136 pass 137 138 def trafo(self, params): 139 """return transformations at params""" 140 141 def transformed(self, trafo): 142 """return transformed normsubpathitem according to trafo""" 143 pass 144 145 def outputPS(self, file, writer): 146 """write PS code corresponding to normsubpathitem to file""" 147 pass 148 149 def outputPDF(self, file, writer): 150 """write PDF code corresponding to normsubpathitem to file""" 151 pass 152 153 def returnSVGdata(self, inverse_y): 154 """return SVG code corresponding to normsubpathitem""" 155 pass 156 157 158class normline_pt(normsubpathitem): 159 160 """Straight line from (x0_pt, y0_pt) to (x1_pt, y1_pt) (coordinates in pts)""" 161 162 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt" 163 164 def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt): 165 self.x0_pt = x0_pt 166 self.y0_pt = y0_pt 167 self.x1_pt = x1_pt 168 self.y1_pt = y1_pt 169 170 def __str__(self): 171 return "normline_pt(%g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt) 172 173 def _arclentoparam_pt(self, lengths_pt, epsilon): 174 # do self.arclen_pt inplace for performance reasons 175 l_pt = math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt) 176 return [length_pt/l_pt for length_pt in lengths_pt], l_pt 177 178 def arclentoparam_pt(self, lengths_pt, epsilon): 179 """return a tuple of params""" 180 return self._arclentoparam_pt(lengths_pt, epsilon)[0] 181 182 def arclen_pt(self, epsilon, upper=False): 183 return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt) 184 185 def at_pt(self, params): 186 return [(self.x0_pt+(self.x1_pt-self.x0_pt)*t, self.y0_pt+(self.y1_pt-self.y0_pt)*t) 187 for t in params] 188 189 def atbegin_pt(self): 190 return self.x0_pt, self.y0_pt 191 192 def atend_pt(self): 193 return self.x1_pt, self.y1_pt 194 195 def bbox(self): 196 return bboxmodule.bbox_pt(min(self.x0_pt, self.x1_pt), min(self.y0_pt, self.y1_pt), 197 max(self.x0_pt, self.x1_pt), max(self.y0_pt, self.y1_pt)) 198 199 cbox = bbox 200 201 def curvature_pt(self, params): 202 return [0] * len(params) 203 204 def intersect(self, other, epsilon): 205 if isinstance(other, normline_pt): 206 a_deltax_pt = self.x1_pt - self.x0_pt 207 a_deltay_pt = self.y1_pt - self.y0_pt 208 209 b_deltax_pt = other.x1_pt - other.x0_pt 210 b_deltay_pt = other.y1_pt - other.y0_pt 211 212 invdet = b_deltax_pt * a_deltay_pt - b_deltay_pt * a_deltax_pt 213 214 if abs(invdet) < epsilon * epsilon: 215 # As invdet measures the area spanned by the two lines, least 216 # one of the lines is either very short or the lines are almost 217 # parallel. In both cases, a proper colinear check is adequate, 218 # already. Let's first check for short lines. 219 short_self = math.hypot(self.x1_pt - self.x0_pt, 220 self.y1_pt - self.y0_pt) < epsilon 221 short_other = math.hypot(other.x1_pt - other.x0_pt, 222 other.y1_pt - other.y0_pt) < epsilon 223 224 # For short lines we will only take their middle point into 225 # account. 226 if short_self: 227 sx_pt = 0.5*(self.x0_pt + self.x1_pt) 228 sy_pt = 0.5*(self.y0_pt + self.x1_pt) 229 if short_other: 230 ox_pt = 0.5*(other.x0_pt + other.x1_pt) 231 oy_pt = 0.5*(other.y0_pt + other.y1_pt) 232 233 def closepoint(x_pt, y_pt, 234 x0_pt, y0_pt, x1_pt, y1_pt): 235 """Returns the line parameter p in range [0, 1] for which 236 the point (x_pt, y_pt) is closest to the line defined by 237 ((x0_pt, y0_pt), (x1_pt, y1_pt)). The distance of (x0_pt, 238 y0_pt) and (x1_pt, y1_pt) must be larger than epsilon. If 239 the point has a greater distance than epsilon, None is 240 returned.""" 241 p = (((x0_pt - x_pt)*(x0_pt - x1_pt) + 242 (y0_pt - y_pt)*(y0_pt - y1_pt))/ 243 ((x1_pt - x0_pt)**2 + (y1_pt - y0_pt)**2)) 244 p = min(1, max(0, p)) 245 xs_pt = x0_pt + p*(x1_pt - x0_pt) 246 ys_pt = y0_pt + p*(y1_pt - y0_pt) 247 if math.hypot(xs_pt - x_pt, ys_pt - y_pt) < epsilon: 248 return p 249 return None # just be explicit in returning None here 250 251 if short_self and short_other: 252 # If both lines are short, we just measure the distance of 253 # the middle points. 254 if math.hypot(ox_pt - sx_pt, oy_pt - sy_pt) < epsilon: 255 return [(0.5, 0.5)] 256 elif short_self: 257 p = closepoint(sx_pt, sy_pt, 258 other.x0_pt, other.y0_pt, other.x1_pt, other.y1_pt) 259 if p is not None: 260 return [(0.5, p)] 261 elif short_other: 262 p = closepoint(ox_pt, oy_pt, 263 self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt) 264 if p is not None: 265 return [(p, 0.5)] 266 else: 267 # For two long colinear lines, we need to test the 268 # beginning and end point of the two lines with respect to 269 # the other line, in all combinations. We return just one 270 # solution even when the lines intersect for a whole range. 271 p = closepoint(self.x0_pt, self.y0_pt, other.x0_pt, other.y0_pt, other.x1_pt, other.y1_pt) 272 if p is not None: 273 return [(0, p)] 274 p = closepoint(self.x1_pt, self.y1_pt, other.x0_pt, other.y0_pt, other.x1_pt, other.y1_pt) 275 if p is not None: 276 return [(1, p)] 277 p = closepoint(other.x0_pt, other.y0_pt, self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt) 278 if p is not None: 279 return [(p, 0)] 280 p = closepoint(other.x1_pt, other.y1_pt, self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt) 281 if p is not None: 282 return [(p, 1)] 283 return [] 284 285 det = 1.0 / invdet 286 287 ba_deltax0_pt = other.x0_pt - self.x0_pt 288 ba_deltay0_pt = other.y0_pt - self.y0_pt 289 290 a_t = (b_deltax_pt * ba_deltay0_pt - b_deltay_pt * ba_deltax0_pt) * det 291 b_t = (a_deltax_pt * ba_deltay0_pt - a_deltay_pt * ba_deltax0_pt) * det 292 293 # check for intersections out of bound 294 if not (0<=a_t<=1 and 0<=b_t<=1): 295 # correct the parameters, if the deviation is smaller than epsilon 296 a_t = min(1, max(0, a_t)) 297 b_t = min(1, max(0, b_t)) 298 a_x = self.x0_pt + a_deltax_pt*a_t 299 a_y = self.y0_pt + a_deltay_pt*a_t 300 b_x = other.x0_pt + b_deltax_pt*b_t 301 b_y = other.y0_pt + b_deltay_pt*b_t 302 if math.hypot(a_x - b_x, a_y - b_y) > epsilon: 303 return [] 304 305 # return parameters of intersection 306 return [(a_t, b_t)] 307 else: 308 return [(s_t, o_t) for o_t, s_t in other.intersect(self, epsilon)] 309 310 def modifiedbegin_pt(self, x_pt, y_pt): 311 return normline_pt(x_pt, y_pt, self.x1_pt, self.y1_pt) 312 313 def modifiedend_pt(self, x_pt, y_pt): 314 return normline_pt(self.x0_pt, self.y0_pt, x_pt, y_pt) 315 316 def _paramtoarclen_pt(self, params, epsilon): 317 totalarclen_pt = self.arclen_pt(epsilon) 318 arclens_pt = [totalarclen_pt * param for param in params + [1]] 319 return arclens_pt[:-1], arclens_pt[-1] 320 321 def pathitem(self): 322 from . import path 323 return path.lineto_pt(self.x1_pt, self.y1_pt) 324 325 def reversed(self): 326 return normline_pt(self.x1_pt, self.y1_pt, self.x0_pt, self.y0_pt) 327 328 def rotation(self, params): 329 return [trafo.rotate(math.degrees(math.atan2(self.y1_pt-self.y0_pt, self.x1_pt-self.x0_pt)))]*len(params) 330 331 def segments(self, params): 332 if len(params) < 2: 333 raise ValueError("at least two parameters needed in segments") 334 result = [] 335 xl_pt = yl_pt = None 336 for t in params: 337 xr_pt = self.x0_pt + (self.x1_pt-self.x0_pt)*t 338 yr_pt = self.y0_pt + (self.y1_pt-self.y0_pt)*t 339 if xl_pt is not None: 340 result.append(normline_pt(xl_pt, yl_pt, xr_pt, yr_pt)) 341 xl_pt = xr_pt 342 yl_pt = yr_pt 343 return result 344 345 def trafo(self, params): 346 rotate = trafo.rotate(math.degrees(math.atan2(self.y1_pt-self.y0_pt, self.x1_pt-self.x0_pt))) 347 return [trafo.translate_pt(*at_pt) * rotate 348 for param, at_pt in zip(params, self.at_pt(params))] 349 350 def transformed(self, trafo): 351 return normline_pt(*(trafo.apply_pt(self.x0_pt, self.y0_pt) + trafo.apply_pt(self.x1_pt, self.y1_pt))) 352 353 def outputPS(self, file, writer): 354 file.write("%g %g lineto\n" % (self.x1_pt, self.y1_pt)) 355 356 def outputPDF(self, file, writer): 357 file.write("%f %f l\n" % (self.x1_pt, self.y1_pt)) 358 359 def returnSVGdata(self, inverse_y): 360 if inverse_y: 361 return "L%g %g" % (self.x1_pt, -self.y1_pt) 362 return "L%g %g" % (self.x1_pt, self.y1_pt) 363 364 365class normcurve_pt(normsubpathitem): 366 367 """Bezier curve with control points x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt (coordinates in pts)""" 368 369 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt" 370 371 def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt): 372 self.x0_pt = x0_pt 373 self.y0_pt = y0_pt 374 self.x1_pt = x1_pt 375 self.y1_pt = y1_pt 376 self.x2_pt = x2_pt 377 self.y2_pt = y2_pt 378 self.x3_pt = x3_pt 379 self.y3_pt = y3_pt 380 381 def __str__(self): 382 return "normcurve_pt(%g, %g, %g, %g, %g, %g, %g, %g)" % (self.x0_pt, self.y0_pt, self.x1_pt, self.y1_pt, 383 self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt) 384 385 def _split(self, t=0.5, epsilon=None, intersect=False): 386 """Split curve into two parts 387 388 The splitting point is defined by the parameter t (in range 0 to 1). 389 When epsilon is None, the two resulting curves are returned. However, 390 when epsilon is set to a (small) float, the method can be used 391 recursively to reduce the complexity of a problem by turning a 392 normcurve_pt into several normline_pt segments. The method returns 393 normcurve_pt instances only, when they are not yet straight enough to 394 be replaceable by normline_pt instances. The criteria for returning a 395 line instead of a curve depends on the value of the boolean intersect. 396 When not set, the abort cirteria is defined by the error of the arclen 397 of the curve vs. the line not being larger than epsilon. When in 398 intersect mode, all points of the curve must be closer to the line than 399 epsilon. 400 """ 401 402 s = 1-t 403 404 # first, we have to calculate the midpoints between adjacent 405 # control points 406 x01_pt = s*self.x0_pt + t*self.x1_pt 407 y01_pt = s*self.y0_pt + t*self.y1_pt 408 x12_pt = s*self.x1_pt + t*self.x2_pt 409 y12_pt = s*self.y1_pt + t*self.y2_pt 410 x23_pt = s*self.x2_pt + t*self.x3_pt 411 y23_pt = s*self.y2_pt + t*self.y3_pt 412 413 # In the next iterative step, we need the midpoints between 01 and 12 414 # and between 12 and 23 415 x01_12_pt = s*x01_pt + t*x12_pt 416 y01_12_pt = s*y01_pt + t*y12_pt 417 x12_23_pt = s*x12_pt + t*x23_pt 418 y12_23_pt = s*y12_pt + t*y23_pt 419 420 # Finally the midpoint is given by 421 xmidpoint_pt = s*x01_12_pt + t*x12_23_pt 422 ymidpoint_pt = s*y01_12_pt + t*y12_23_pt 423 424 def subcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt, newline, newcurve): 425 if epsilon is None: 426 return normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt) 427 428 # Before returning the subcurve we check whether we can 429 # replace it by a normline within an error of epsilon pts. 430 l0_pt = math.hypot(x3_pt-x0_pt, y3_pt-y0_pt) 431 l1_pt = math.hypot(x1_pt-x0_pt, y1_pt-y0_pt) 432 l2_pt = math.hypot(x2_pt-x1_pt, y2_pt-y1_pt) 433 l3_pt = math.hypot(x3_pt-x2_pt, y3_pt-y2_pt) 434 435 # When arclen calculation is performed, the maximal error value is 436 # given by the modulus of the difference between the length of the 437 # control polygon (i.e. |P1-P0|+|P2-P1|+|P3-P2|), which consitutes 438 # an upper bound for the length, and the length of the straight 439 # line between start and end point of the normcurve (i.e. |P3-P1|), 440 # which represents a lower bound. 441 if not intersect and l1_pt+l2_pt+l3_pt-l0_pt < epsilon: 442 # We can ignore the sign of l1_pt, l2_pt and l3_pt, as the sum 443 # of the absolute values is close to l0_pt anyway. 444 return newline(x0_pt, y0_pt, x3_pt, y3_pt, l1_pt, l2_pt, l3_pt) 445 446 if intersect: 447 # For intersections we calculate the distance of (x1_pt, y1_pt) 448 # and (x2_pt, y2_pt) from the line defined by (x0_pt, y0_pt) 449 # and (x3_pt, y3_pt). We skip the division by l0_pt in the 450 # result and calculate d1_pt*l0_pt and d2_pt*l0_pt instead. 451 d1_pt_times_l0_pt = (x3_pt-x0_pt)*(y0_pt-y1_pt) - (x0_pt-x1_pt)*(y3_pt-y0_pt) 452 d2_pt_times_l0_pt = (x0_pt-x3_pt)*(y3_pt-y2_pt) - (x3_pt-x2_pt)*(y0_pt-y3_pt) 453 if abs(d1_pt_times_l0_pt) < epsilon*l0_pt and abs(d2_pt_times_l0_pt) < epsilon*l0_pt: 454 # We could return the line now, but for this to be correct, 455 # we would need to take into account the signs of l1_pt, 456 # l2_pt, and l3_pt. In addition, this could result in 457 # multiple parameters matching a position on the line. 458 s1 = (x1_pt-x0_pt)*(x3_pt-x0_pt)+(y1_pt-y0_pt)*(y3_pt-y0_pt) 459 s2 = (x2_pt-x1_pt)*(x3_pt-x0_pt)+(y2_pt-y1_pt)*(y3_pt-y0_pt) 460 s3 = (x2_pt-x3_pt)*(x0_pt-x3_pt)+(y2_pt-y3_pt)*(y0_pt-y3_pt) 461 462 # If the signs are negative (i.e. we have backwards 463 # directed segments in the control polygon), we can still 464 # continue, if the corresponding segment is smaller than 465 # epsilon. 466 if ((s1 > 0 or l1_pt < epsilon) and 467 (s2 > 0 or l2_pt < epsilon) and 468 (s3 > 0 or l3_pt < epsilon)): 469 # As the sign of the segments is either positive or the 470 # segments are short, we can continue with the unsigned 471 # values for the segment lengths, as for the arclen 472 # calculation. 473 return newline(x0_pt, y0_pt, x3_pt, y3_pt, l1_pt, l2_pt, l3_pt) 474 475 return newcurve(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt) 476 477 return (subcurve(self.x0_pt, self.y0_pt, 478 x01_pt, y01_pt, 479 x01_12_pt, y01_12_pt, 480 xmidpoint_pt, ymidpoint_pt, 481 _leftnormline_pt, _leftnormcurve_pt), 482 subcurve(xmidpoint_pt, ymidpoint_pt, 483 x12_23_pt, y12_23_pt, 484 x23_pt, y23_pt, 485 self.x3_pt, self.y3_pt, 486 _rightnormline_pt, _rightnormcurve_pt)) 487 488 def _arclentoparam_pt(self, lengths_pt, epsilon): 489 a, b = self._split(epsilon=epsilon) 490 params_a, arclen_a_pt = a._arclentoparam_pt(lengths_pt, 0.5*epsilon) 491 params_b, arclen_b_pt = b._arclentoparam_pt([length_pt - arclen_a_pt for length_pt in lengths_pt], 0.5*epsilon) 492 params = [] 493 for param_a, param_b, length_pt in zip(params_a, params_b, lengths_pt): 494 if length_pt > arclen_a_pt: 495 params.append(b.subparamtoparam(param_b)) 496 else: 497 params.append(a.subparamtoparam(param_a)) 498 return params, arclen_a_pt + arclen_b_pt 499 500 def arclentoparam_pt(self, lengths_pt, epsilon): 501 """return a tuple of params""" 502 return self._arclentoparam_pt(lengths_pt, epsilon)[0] 503 504 def arclen_pt(self, epsilon, upper=False): 505 a, b = self._split(epsilon=epsilon) 506 return a.arclen_pt(0.5*epsilon, upper=upper) + b.arclen_pt(0.5*epsilon, upper=upper) 507 508 def at_pt(self, params): 509 return [( (-self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*t*t*t + 510 (3*self.x0_pt-6*self.x1_pt+3*self.x2_pt )*t*t + 511 (-3*self.x0_pt+3*self.x1_pt )*t + 512 self.x0_pt, 513 (-self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*t*t*t + 514 (3*self.y0_pt-6*self.y1_pt+3*self.y2_pt )*t*t + 515 (-3*self.y0_pt+3*self.y1_pt )*t + 516 self.y0_pt ) 517 for t in params] 518 519 def atbegin_pt(self): 520 return self.x0_pt, self.y0_pt 521 522 def atend_pt(self): 523 return self.x3_pt, self.y3_pt 524 525 def bbox(self): 526 from . import path 527 xmin_pt, xmax_pt = path._bezierpolyrange(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt) 528 ymin_pt, ymax_pt = path._bezierpolyrange(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt) 529 return bboxmodule.bbox_pt(xmin_pt, ymin_pt, xmax_pt, ymax_pt) 530 531 def cbox(self): 532 return bboxmodule.bbox_pt(min(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt), 533 min(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt), 534 max(self.x0_pt, self.x1_pt, self.x2_pt, self.x3_pt), 535 max(self.y0_pt, self.y1_pt, self.y2_pt, self.y3_pt)) 536 537 def curvature_pt(self, params): 538 result = [] 539 # see notes in rotation 540 approxarclen = (math.hypot(self.x1_pt-self.x0_pt, self.y1_pt-self.y0_pt) + 541 math.hypot(self.x2_pt-self.x1_pt, self.y2_pt-self.y1_pt) + 542 math.hypot(self.x3_pt-self.x2_pt, self.y3_pt-self.y2_pt)) 543 for param in params: 544 xdot = ( 3 * (1-param)*(1-param) * (-self.x0_pt + self.x1_pt) + 545 6 * (1-param)*param * (-self.x1_pt + self.x2_pt) + 546 3 * param*param * (-self.x2_pt + self.x3_pt) ) 547 ydot = ( 3 * (1-param)*(1-param) * (-self.y0_pt + self.y1_pt) + 548 6 * (1-param)*param * (-self.y1_pt + self.y2_pt) + 549 3 * param*param * (-self.y2_pt + self.y3_pt) ) 550 xddot = ( 6 * (1-param) * (self.x0_pt - 2*self.x1_pt + self.x2_pt) + 551 6 * param * (self.x1_pt - 2*self.x2_pt + self.x3_pt) ) 552 yddot = ( 6 * (1-param) * (self.y0_pt - 2*self.y1_pt + self.y2_pt) + 553 6 * param * (self.y1_pt - 2*self.y2_pt + self.y3_pt) ) 554 555 hypot = math.hypot(xdot, ydot) 556 result.append((xdot*yddot - ydot*xddot) / hypot**3) 557 return result 558 559 def intersect(self, other, epsilon): 560 # There can be no intersection point if the control boxes do not 561 # overlap. Note that we use the control box instead of the bounding 562 # box here, because the former can be calculated more efficiently for 563 # Bezier curves. 564 if not self.cbox().enlarged_pt(epsilon).intersects(other.cbox()): 565 return [] 566 a, b = self._split(epsilon=epsilon, intersect=True) 567 # To improve the performance in the general case we alternate the 568 # splitting process between the two normsubpathitems 569 return ( [(a.subparamtoparam(a_t), o_t) for o_t, a_t in other.intersect(a, epsilon)] + 570 [(b.subparamtoparam(b_t), o_t) for o_t, b_t in other.intersect(b, epsilon)] ) 571 572 def modifiedbegin_pt(self, x_pt, y_pt): 573 return normcurve_pt(x_pt, y_pt, 574 self.x1_pt, self.y1_pt, 575 self.x2_pt, self.y2_pt, 576 self.x3_pt, self.y3_pt) 577 578 def modifiedend_pt(self, x_pt, y_pt): 579 return normcurve_pt(self.x0_pt, self.y0_pt, 580 self.x1_pt, self.y1_pt, 581 self.x2_pt, self.y2_pt, 582 x_pt, y_pt) 583 584 def _paramtoarclen_pt(self, params, epsilon): 585 arclens_pt = [segment.arclen_pt(epsilon) for segment in self.segments([0] + list(params) + [1])] 586 for i in range(1, len(arclens_pt)): 587 arclens_pt[i] += arclens_pt[i-1] 588 return arclens_pt[:-1], arclens_pt[-1] 589 590 def pathitem(self): 591 from . import path 592 return path.curveto_pt(self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt) 593 594 def reversed(self): 595 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) 596 597 def rotation(self, params): 598 result = [] 599 for param in params: 600 tdx_pt = (3*( -self.x0_pt+3*self.x1_pt-3*self.x2_pt+self.x3_pt)*param*param + 601 2*( 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt )*param + 602 (-3*self.x0_pt+3*self.x1_pt )) 603 tdy_pt = (3*( -self.y0_pt+3*self.y1_pt-3*self.y2_pt+self.y3_pt)*param*param + 604 2*( 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt )*param + 605 (-3*self.y0_pt+3*self.y1_pt )) 606 result.append(trafo.rotate(math.degrees(math.atan2(tdy_pt, tdx_pt)))) 607 return result 608 609 def segments(self, params): 610 if len(params) < 2: 611 raise ValueError("at least two parameters needed in segments") 612 613 # first, we calculate the coefficients corresponding to our 614 # original bezier curve. These represent a useful starting 615 # point for the following change of the polynomial parameter 616 a0x_pt = self.x0_pt 617 a0y_pt = self.y0_pt 618 a1x_pt = 3*(-self.x0_pt+self.x1_pt) 619 a1y_pt = 3*(-self.y0_pt+self.y1_pt) 620 a2x_pt = 3*(self.x0_pt-2*self.x1_pt+self.x2_pt) 621 a2y_pt = 3*(self.y0_pt-2*self.y1_pt+self.y2_pt) 622 a3x_pt = -self.x0_pt+3*(self.x1_pt-self.x2_pt)+self.x3_pt 623 a3y_pt = -self.y0_pt+3*(self.y1_pt-self.y2_pt)+self.y3_pt 624 625 result = [] 626 627 for i in range(len(params)-1): 628 t1 = params[i] 629 dt = params[i+1]-t1 630 631 # [t1,t2] part 632 # 633 # the new coefficients of the [t1,t1+dt] part of the bezier curve 634 # are then given by expanding 635 # a0 + a1*(t1+dt*u) + a2*(t1+dt*u)**2 + 636 # a3*(t1+dt*u)**3 in u, yielding 637 # 638 # a0 + a1*t1 + a2*t1**2 + a3*t1**3 + 639 # ( a1 + 2*a2 + 3*a3*t1**2 )*dt * u + 640 # ( a2 + 3*a3*t1 )*dt**2 * u**2 + 641 # a3*dt**3 * u**3 642 # 643 # from this values we obtain the new control points by inversion 644 # 645 # TODO: we could do this more efficiently by reusing for 646 # (x0_pt, y0_pt) the control point (x3_pt, y3_pt) from the previous 647 # Bezier curve 648 649 x0_pt = a0x_pt + a1x_pt*t1 + a2x_pt*t1*t1 + a3x_pt*t1*t1*t1 650 y0_pt = a0y_pt + a1y_pt*t1 + a2y_pt*t1*t1 + a3y_pt*t1*t1*t1 651 x1_pt = (a1x_pt+2*a2x_pt*t1+3*a3x_pt*t1*t1)*dt/3.0 + x0_pt 652 y1_pt = (a1y_pt+2*a2y_pt*t1+3*a3y_pt*t1*t1)*dt/3.0 + y0_pt 653 x2_pt = (a2x_pt+3*a3x_pt*t1)*dt*dt/3.0 - x0_pt + 2*x1_pt 654 y2_pt = (a2y_pt+3*a3y_pt*t1)*dt*dt/3.0 - y0_pt + 2*y1_pt 655 x3_pt = a3x_pt*dt*dt*dt + x0_pt - 3*x1_pt + 3*x2_pt 656 y3_pt = a3y_pt*dt*dt*dt + y0_pt - 3*y1_pt + 3*y2_pt 657 658 result.append(normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt)) 659 660 return result 661 662 def trafo(self, params): 663 result = [] 664 for rotation, at_pt in zip(self.rotation(params), self.at_pt(params)): 665 result.append(trafo.translate_pt(*at_pt) * rotation) 666 return result 667 668 def transformed(self, trafo): 669 x0_pt, y0_pt = trafo.apply_pt(self.x0_pt, self.y0_pt) 670 x1_pt, y1_pt = trafo.apply_pt(self.x1_pt, self.y1_pt) 671 x2_pt, y2_pt = trafo.apply_pt(self.x2_pt, self.y2_pt) 672 x3_pt, y3_pt = trafo.apply_pt(self.x3_pt, self.y3_pt) 673 return normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt) 674 675 def outputPS(self, file, writer): 676 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)) 677 678 def outputPDF(self, file, writer): 679 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)) 680 681 def returnSVGdata(self, inverse_y): 682 if inverse_y: 683 return "C%g %g %g %g %g %g" % (self.x1_pt, -self.y1_pt, self.x2_pt, -self.y2_pt, self.x3_pt, -self.y3_pt) 684 return "C%g %g %g %g %g %g" % (self.x1_pt, self.y1_pt, self.x2_pt, self.y2_pt, self.x3_pt, self.y3_pt) 685 686 def x_pt(self, t): 687 return ((( self.x3_pt-3*self.x2_pt+3*self.x1_pt-self.x0_pt)*t + 688 3*self.x0_pt-6*self.x1_pt+3*self.x2_pt)*t + 689 3*self.x1_pt-3*self.x0_pt)*t + self.x0_pt 690 691 def xdot_pt(self, t): 692 return ((3*self.x3_pt-9*self.x2_pt+9*self.x1_pt-3*self.x0_pt)*t + 693 6*self.x0_pt-12*self.x1_pt+6*self.x2_pt)*t + 3*self.x1_pt - 3*self.x0_pt 694 695 def xddot_pt(self, t): 696 return (6*self.x3_pt-18*self.x2_pt+18*self.x1_pt-6*self.x0_pt)*t + 6*self.x0_pt - 12*self.x1_pt + 6*self.x2_pt 697 698 def xdddot_pt(self, t): 699 return 6*self.x3_pt-18*self.x2_pt+18*self.x1_pt-6*self.x0_pt 700 701 def y_pt(self, t): 702 return ((( self.y3_pt-3*self.y2_pt+3*self.y1_pt-self.y0_pt)*t + 703 3*self.y0_pt-6*self.y1_pt+3*self.y2_pt)*t + 704 3*self.y1_pt-3*self.y0_pt)*t + self.y0_pt 705 706 def ydot_pt(self, t): 707 return ((3*self.y3_pt-9*self.y2_pt+9*self.y1_pt-3*self.y0_pt)*t + 708 6*self.y0_pt-12*self.y1_pt+6*self.y2_pt)*t + 3*self.y1_pt - 3*self.y0_pt 709 710 def yddot_pt(self, t): 711 return (6*self.y3_pt-18*self.y2_pt+18*self.y1_pt-6*self.y0_pt)*t + 6*self.y0_pt - 12*self.y1_pt + 6*self.y2_pt 712 713 def ydddot_pt(self, t): 714 return 6*self.y3_pt-18*self.y2_pt+18*self.y1_pt-6*self.y0_pt 715 716 717# curve replacements used by midpointsplit: 718# The replacements are normline_pt and normcurve_pt instances with an 719# additional subparamtoparam function for proper conversion of the 720# parametrization. Note that we only one direction (when a parameter 721# gets calculated), since the other way around direction midpointsplit 722# is not needed at all 723 724class _leftnormline_pt(normline_pt): 725 726 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "l1_pt", "l2_pt", "l3_pt" 727 728 def __init__(self, x0_pt, y0_pt, x1_pt, y1_pt, l1_pt, l2_pt, l3_pt): 729 normline_pt.__init__(self, x0_pt, y0_pt, x1_pt, y1_pt) 730 self.l1_pt = l1_pt 731 self.l2_pt = l2_pt 732 self.l3_pt = l3_pt 733 734 def arclen_pt(self, epsilon, upper=False): 735 if upper: 736 return self.l1_pt + self.l2_pt + self.l3_pt 737 else: 738 return math.hypot(self.x0_pt-self.x1_pt, self.y0_pt-self.y1_pt) 739 740 def subparamtoparam(self, param): 741 if 0 <= param <= 1: 742 params = mathutils.realpolyroots(self.l1_pt-2*self.l2_pt+self.l3_pt, 743 -3*self.l1_pt+3*self.l2_pt, 744 3*self.l1_pt, 745 -param*(self.l1_pt+self.l2_pt+self.l3_pt)) 746 # we might get several solutions and choose the one closest to 0.5 747 # (we want the solution to be in the range 0 <= param <= 1; in case 748 # we get several solutions in this range, they all will be close to 749 # each other since l1_pt+l2_pt+l3_pt-l0_pt < epsilon) 750 params.sort(key=lambda t: abs(t-0.5)) 751 return 0.5*params[0] 752 else: 753 # when we are outside the proper parameter range, we skip the non-linear 754 # transformation, since it becomes slow and it might even start to be 755 # numerically instable 756 return 0.5*param 757 758 759class _rightnormline_pt(_leftnormline_pt): 760 761 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "l1_pt", "l2_pt", "l3_pt" 762 763 def subparamtoparam(self, param): 764 return 0.5+_leftnormline_pt.subparamtoparam(self, param) 765 766 767class _leftnormcurve_pt(normcurve_pt): 768 769 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt" 770 771 def subparamtoparam(self, param): 772 return 0.5*param 773 774 775class _rightnormcurve_pt(normcurve_pt): 776 777 __slots__ = "x0_pt", "y0_pt", "x1_pt", "y1_pt", "x2_pt", "y2_pt", "x3_pt", "y3_pt" 778 779 def subparamtoparam(self, param): 780 return 0.5+0.5*param 781 782 783################################################################################ 784# normsubpath 785################################################################################ 786 787class normsubpath: 788 789 """sub path of a normalized path 790 791 A subpath consists of a list of normsubpathitems, i.e., normlines_pt and 792 normcurves_pt and can either be closed or not. 793 794 Some invariants, which have to be obeyed: 795 - All normsubpathitems have to be longer than epsilon pts. 796 - At the end there may be a normline (stored in self.skippedline) whose 797 length is shorter than epsilon -- it has to be taken into account 798 when adding further normsubpathitems 799 - The last point of a normsubpathitem and the first point of the next 800 element have to be equal. 801 - When the path is closed, the last point of last normsubpathitem has 802 to be equal to the first point of the first normsubpathitem. 803 - epsilon might be none, disallowing any numerics, but allowing for 804 arbitrary short paths. This is used in pdf output, where all paths need 805 to be transformed to normpaths. 806 """ 807 808 __slots__ = "normsubpathitems", "closed", "epsilon", "skippedline" 809 810 def __init__(self, normsubpathitems=[], closed=0, epsilon=_marker): 811 """construct a normsubpath""" 812 if epsilon is _marker: 813 epsilon = _epsilon 814 self.epsilon = epsilon 815 # If one or more items appended to the normsubpath have been 816 # skipped (because their total length was shorter than epsilon), 817 # we remember this fact by a line because we have to take it 818 # properly into account when appending further normsubpathitems 819 self.skippedline = None 820 821 self.normsubpathitems = [] 822 self.closed = 0 823 824 # a test (might be temporary) 825 for anormsubpathitem in normsubpathitems: 826 assert isinstance(anormsubpathitem, normsubpathitem), "only list of normsubpathitem instances allowed" 827 828 self.extend(normsubpathitems) 829 830 if closed: 831 self.close() 832 833 def __getitem__(self, i): 834 """return normsubpathitem i""" 835 return self.normsubpathitems[i] 836 837 def __len__(self): 838 """return number of normsubpathitems""" 839 return len(self.normsubpathitems) 840 841 def __str__(self): 842 l = ", ".join(map(str, self.normsubpathitems)) 843 if self.closed: 844 return "normsubpath([%s], closed=1)" % l 845 else: 846 return "normsubpath([%s])" % l 847 848 def _distributeparams(self, params): 849 """return a dictionary mapping normsubpathitemindices to a tuple 850 of a paramindices and normsubpathitemparams. 851 852 normsubpathitemindex specifies a normsubpathitem containing 853 one or several positions. paramindex specify the index of the 854 param in the original list and normsubpathitemparam is the 855 parameter value in the normsubpathitem. 856 """ 857 858 result = {} 859 for i, param in enumerate(params): 860 if param > 0: 861 index = int(param) 862 if index > len(self.normsubpathitems) - 1: 863 index = len(self.normsubpathitems) - 1 864 else: 865 index = 0 866 result.setdefault(index, ([], [])) 867 result[index][0].append(i) 868 result[index][1].append(param - index) 869 return result 870 871 def append(self, anormsubpathitem): 872 """append normsubpathitem 873 874 Fails on closed normsubpath. 875 """ 876 if self.epsilon is None: 877 self.normsubpathitems.append(anormsubpathitem) 878 else: 879 # consitency tests (might be temporary) 880 assert isinstance(anormsubpathitem, normsubpathitem), "only normsubpathitem instances allowed" 881 if self.skippedline: 882 assert math.hypot(*[x-y for x, y in zip(self.skippedline.atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match" 883 elif self.normsubpathitems: 884 assert math.hypot(*[x-y for x, y in zip(self.normsubpathitems[-1].atend_pt(), anormsubpathitem.atbegin_pt())]) < self.epsilon, "normsubpathitems do not match" 885 886 if self.closed: 887 raise NormpathException("Cannot append to closed normsubpath") 888 889 if self.skippedline: 890 anormsubpathitem = anormsubpathitem.modifiedbegin_pt(*self.skippedline.atbegin_pt()) 891 self.skippedline = None 892 893 if isinstance(anormsubpathitem, normline_pt): 894 if math.hypot(anormsubpathitem.x1_pt-anormsubpathitem.x0_pt, anormsubpathitem.y1_pt-anormsubpathitem.y0_pt) >= self.epsilon: 895 self.normsubpathitems.append(anormsubpathitem) 896 else: 897 self.skippedline = anormsubpathitem 898 else: 899 # it is a normcurve_pt 900 x0_pt = anormsubpathitem.x0_pt 901 y0_pt = anormsubpathitem.y0_pt 902 x1_pt = anormsubpathitem.x1_pt 903 y1_pt = anormsubpathitem.y1_pt 904 x2_pt = anormsubpathitem.x2_pt 905 y2_pt = anormsubpathitem.y2_pt 906 x3_pt = anormsubpathitem.x3_pt 907 y3_pt = anormsubpathitem.y3_pt 908 909 l03_pt = math.hypot(x3_pt-x0_pt, y3_pt-y0_pt) 910 l01_pt = math.hypot(x1_pt-x0_pt, y1_pt-y0_pt) 911 l02_pt = math.hypot(x2_pt-x0_pt, y2_pt-y0_pt) 912 l23_pt = math.hypot(x2_pt-x3_pt, y2_pt-y3_pt) 913 l13_pt = math.hypot(x1_pt-x3_pt, y1_pt-y3_pt) 914 915 if l03_pt >= self.epsilon or ( (l01_pt*3 >= self.epsilon or l02_pt*3 >= self.epsilon) and 916 (l23_pt*3 >= self.epsilon or l13_pt*3 >= self.epsilon) ): 917 # We first may shift (x1_pt, y1_pt) and (x2_pt, y2_pt) to 918 # have minimal derivates at the beginning and end point. 919 920 # keep a copy of (x1_pt, y1_pt) for shifting (x2_pt, y2_pt) 921 x1o_pt = x1_pt 922 y1o_pt = y1_pt 923 924 # When repositioning the control points, use a factor 2.9 925 # instead of 3 to get a derivative above the threshold as 926 # otherwise deep recursions can occur. 927 if l01_pt*3 < self.epsilon: 928 if l02_pt*3 >= self.epsilon: 929 x1_pt = x0_pt + (x2_pt-x0_pt)*self.epsilon/l02_pt/2.9 930 y1_pt = y0_pt + (y2_pt-y0_pt)*self.epsilon/l02_pt/2.9 931 else: 932 x1_pt = x0_pt + (x3_pt-x0_pt)*self.epsilon/l03_pt/2.9 933 y1_pt = y0_pt + (y3_pt-y0_pt)*self.epsilon/l03_pt/2.9 934 935 if l23_pt*3 < self.epsilon: 936 if l13_pt*3 >= self.epsilon: 937 x2_pt = x3_pt + (x1o_pt-x3_pt)*self.epsilon/l13_pt/2.9 938 y2_pt = y3_pt + (y1o_pt-y3_pt)*self.epsilon/l13_pt/2.9 939 else: 940 x2_pt = x3_pt + (x0_pt-x3_pt)*self.epsilon/l03_pt/2.9 941 y2_pt = y3_pt + (y0_pt-y3_pt)*self.epsilon/l03_pt/2.9 942 943 newitems = [normcurve_pt(x0_pt, y0_pt, x1_pt, y1_pt, x2_pt, y2_pt, x3_pt, y3_pt)] 944 945 # find extrema of the derivative 946 ax = x3_pt - 3*x2_pt + 3*x1_pt - x0_pt 947 bx = 2*x0_pt - 4*x1_pt + 2*x2_pt 948 cx = x1_pt - x0_pt 949 ay = y3_pt - 3*y2_pt + 3*y1_pt - y0_pt 950 by = 2*y0_pt - 4*y1_pt + 2*y2_pt 951 cy = y1_pt - y0_pt 952 roots = mathutils.realpolyroots(4*ax*ax + 4*ay*ay, 6*ax*bx + 6*ay*by, 4*ax*cx + 4*ay*cy + 2*bx*bx + 2*by*by, 2*bx*cx + 2*by*cy) 953 954 # split at points of too small derivative 955 splitpoints = [t for t in roots if 0 < t < 1 and 9*((ax*t*t+bx*t+cx)**2+(ay*t*t+by*t+cy)**2) < self.epsilon*self.epsilon] 956 if not splitpoints: 957 self.normsubpathitems.extend(newitems) 958 else: 959 splitpoints.sort() 960 for i, splitpoint in enumerate(splitpoints): 961 if i: 962 # take splitpoint relative to the subcurve 963 splitpoint = (splitpoint-splitpoints[i-1])/(1-splitpoints[i-1]) 964 newitems.extend(newitems.pop()._split(splitpoint)) 965 966 # Replace short curves by lines. Otherwise skippedline 967 # could shake up the short curve completely. 968 for i in range(len(newitems)): 969 l01_pt = math.hypot(newitems[i].x1_pt-newitems[i].x0_pt, newitems[i].y1_pt-newitems[i].y0_pt) 970 l12_pt = math.hypot(newitems[i].x2_pt-newitems[i].x1_pt, newitems[i].y2_pt-newitems[i].y1_pt) 971 l23_pt = math.hypot(newitems[i].x3_pt-newitems[i].x2_pt, newitems[i].y3_pt-newitems[i].y2_pt) 972 if l01_pt+l12_pt+l23_pt < self.epsilon: 973 newitems[i] = normline_pt(newitems[i].x0_pt, newitems[i].y0_pt, newitems[i].x3_pt, newitems[i].y3_pt) 974 975 self.extend(newitems) 976 else: 977 self.skippedline = normline_pt(anormsubpathitem.x0_pt, anormsubpathitem.y0_pt, anormsubpathitem.x3_pt, anormsubpathitem.y3_pt) 978 979 def arclen_pt(self, upper=False): 980 """return arc length in pts 981 982 When upper is set, the upper bound is calculated, otherwise the lower 983 bound is returned.""" 984 return sum([npitem.arclen_pt(self.epsilon, upper=upper) for npitem in self.normsubpathitems]) 985 986 def _arclentoparam_pt(self, lengths_pt): 987 """return a tuple of params and the total length arc length in pts""" 988 # work on a copy which is counted down to negative values 989 lengths_pt = lengths_pt[:] 990 results = [None] * len(lengths_pt) 991 992 totalarclen = 0 993 for normsubpathindex, normsubpathitem in enumerate(self.normsubpathitems): 994 params, arclen = normsubpathitem._arclentoparam_pt(lengths_pt, self.epsilon) 995 for i in range(len(results)): 996 if results[i] is None: 997 lengths_pt[i] -= arclen 998 if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpathitems) - 1: 999 # overwrite the results until the length has become negative 1000 results[i] = normsubpathindex + params[i] 1001 totalarclen += arclen 1002 1003 return results, totalarclen 1004 1005 def arclentoparam_pt(self, lengths_pt): 1006 """return a tuple of params""" 1007 return self._arclentoparam_pt(lengths_pt)[0] 1008 1009 def at_pt(self, params): 1010 """return coordinates at params in pts""" 1011 if not self.normsubpathitems and self.skippedline: 1012 return [self.skippedline.atbegin_pt()]*len(params) 1013 result = [None] * len(params) 1014 for normsubpathitemindex, (indices, params) in list(self._distributeparams(params).items()): 1015 for index, point_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].at_pt(params)): 1016 result[index] = point_pt 1017 return result 1018 1019 def atbegin_pt(self): 1020 """return coordinates of first point in pts""" 1021 if not self.normsubpathitems and self.skippedline: 1022 return self.skippedline.atbegin_pt() 1023 return self.normsubpathitems[0].atbegin_pt() 1024 1025 def atend_pt(self): 1026 """return coordinates of last point in pts""" 1027 if self.skippedline: 1028 return self.skippedline.atend_pt() 1029 return self.normsubpathitems[-1].atend_pt() 1030 1031 def bbox(self): 1032 """return bounding box of normsubpath""" 1033 if self.normsubpathitems: 1034 abbox = self.normsubpathitems[0].bbox() 1035 for anormpathitem in self.normsubpathitems[1:]: 1036 abbox += anormpathitem.bbox() 1037 return abbox 1038 else: 1039 return bboxmodule.empty() 1040 1041 def close(self): 1042 """close subnormpath 1043 1044 Fails on closed normsubpath. 1045 """ 1046 if self.closed: 1047 raise NormpathException("Cannot close already closed normsubpath") 1048 if not self.normsubpathitems: 1049 if self.skippedline is None: 1050 raise NormpathException("Cannot close empty normsubpath") 1051 else: 1052 raise NormpathException("Normsubpath too short, cannot be closed") 1053 1054 xs_pt, ys_pt = self.normsubpathitems[-1].atend_pt() 1055 xe_pt, ye_pt = self.normsubpathitems[0].atbegin_pt() 1056 self.append(normline_pt(xs_pt, ys_pt, xe_pt, ye_pt)) 1057 self.flushskippedline() 1058 self.closed = 1 1059 1060 def copy(self): 1061 """return copy of normsubpath""" 1062 # Since normsubpathitems are never modified inplace, we just 1063 # need to copy the normsubpathitems list. We do not pass the 1064 # normsubpathitems to the constructor to not repeat the checks 1065 # for minimal length of each normsubpathitem. 1066 result = normsubpath(epsilon=self.epsilon) 1067 result.normsubpathitems = self.normsubpathitems[:] 1068 result.closed = self.closed 1069 1070 # We can share the reference to skippedline, since it is a 1071 # normsubpathitem as well and thus not modified in place either. 1072 result.skippedline = self.skippedline 1073 1074 return result 1075 1076 def curvature_pt(self, params): 1077 """return the curvature at params in 1/pts""" 1078 result = [None] * len(params) 1079 for normsubpathitemindex, (indices, params) in list(self._distributeparams(params).items()): 1080 for index, curvature_pt in zip(indices, self.normsubpathitems[normsubpathitemindex].curvature_pt(params)): 1081 result[index] = curvature_pt 1082 return result 1083 1084 def extend(self, normsubpathitems): 1085 """extend path by normsubpathitems 1086 1087 Fails on closed normsubpath. 1088 """ 1089 for normsubpathitem in normsubpathitems: 1090 self.append(normsubpathitem) 1091 1092 def flushskippedline(self): 1093 """flush the skippedline, i.e. apply it to the normsubpath 1094 1095 remove the skippedline by modifying the end point of the existing normsubpath 1096 """ 1097 while self.skippedline: 1098 try: 1099 lastnormsubpathitem = self.normsubpathitems.pop() 1100 except IndexError: 1101 raise ValueError("normsubpath too short to flush the skippedline") 1102 lastnormsubpathitem = lastnormsubpathitem.modifiedend_pt(*self.skippedline.atend_pt()) 1103 self.skippedline = None 1104 self.append(lastnormsubpathitem) 1105 1106 def intersect(self, other): 1107 """intersect self with other normsubpath 1108 1109 Returns a tuple of lists consisting of the parameter values 1110 of the intersection points of the corresponding normsubpath. 1111 """ 1112 intersections_a = [] 1113 intersections_b = [] 1114 epsilon = min(self.epsilon, other.epsilon) 1115 # Intersect all subpaths of self with the subpaths of other, possibly including 1116 # one intersection point several times 1117 for t_a, pitem_a in enumerate(self.normsubpathitems): 1118 for t_b, pitem_b in enumerate(other.normsubpathitems): 1119 for intersection_a, intersection_b in pitem_a.intersect(pitem_b, epsilon): 1120 intersections_a.append(intersection_a + t_a) 1121 intersections_b.append(intersection_b + t_b) 1122 1123 # although intersectipns_a are sorted for the different normsubpathitems, 1124 # within a normsubpathitem, the ordering has to be ensured separately: 1125 intersections = list(zip(intersections_a, intersections_b)) 1126 intersections.sort() 1127 intersections_a = [a for a, b in intersections] 1128 intersections_b = [b for a, b in intersections] 1129 1130 # for symmetry reasons we enumerate intersections_a as well, although 1131 # they are already sorted (note we do not need to sort intersections_a) 1132 intersections_a = list(zip(intersections_a, list(range(len(intersections_a))))) 1133 intersections_b = list(zip(intersections_b, list(range(len(intersections_b))))) 1134 intersections_b.sort() 1135 1136 # now we search for intersections points which are closer together than epsilon 1137 # This task is handled by the following function 1138 def closepoints(normsubpath, intersections): 1139 split = normsubpath.segments([0] + [intersection for intersection, index in intersections] + [len(normsubpath)]) 1140 result = [] 1141 if normsubpath.closed: 1142 # note that the number of segments of a closed path is off by one 1143 # compared to an open path 1144 i = 0 1145 while i < len(split): 1146 splitnormsubpath = split[i] 1147 j = i 1148 while not splitnormsubpath.normsubpathitems: # i.e. while "is short" 1149 ip1, ip2 = intersections[i-1][1], intersections[j][1] 1150 if ip1<ip2: 1151 result.append((ip1, ip2)) 1152 else: 1153 result.append((ip2, ip1)) 1154 j += 1 1155 if j == len(split): 1156 j = 0 1157 if j < len(split): 1158 splitnormsubpath = splitnormsubpath.joined(split[j]) 1159 else: 1160 break 1161 i += 1 1162 else: 1163 i = 1 1164 while i < len(split)-1: 1165 splitnormsubpath = split[i] 1166 j = i 1167 while not splitnormsubpath.normsubpathitems: # i.e. while "is short" 1168 ip1, ip2 = intersections[i-1][1], intersections[j][1] 1169 if ip1<ip2: 1170 result.append((ip1, ip2)) 1171 else: 1172 result.append((ip2, ip1)) 1173 j += 1 1174 if j < len(split)-1: 1175 splitnormsubpath = splitnormsubpath.joined(split[j]) 1176 else: 1177 break 1178 i += 1 1179 return result 1180 1181 closepoints_a = closepoints(self, intersections_a) 1182 closepoints_b = closepoints(other, intersections_b) 1183 1184 # map intersection point to lowest point which is equivalent to the 1185 # point 1186 equivalentpoints = list(range(len(intersections_a))) 1187 1188 for closepoint_a in closepoints_a: 1189 for closepoint_b in closepoints_b: 1190 if closepoint_a == closepoint_b: 1191 for i in range(closepoint_a[1], len(equivalentpoints)): 1192 if equivalentpoints[i] == closepoint_a[1]: 1193 equivalentpoints[i] = closepoint_a[0] 1194 1195 # determine the remaining intersection points 1196 intersectionpoints = {} 1197 for point in equivalentpoints: 1198 intersectionpoints[point] = 1 1199 1200 # build result 1201 result = [] 1202 intersectionpointskeys = list(intersectionpoints.keys()) 1203 intersectionpointskeys.sort() 1204 for point in intersectionpointskeys: 1205 for intersection_a, index_a in intersections_a: 1206 if index_a == point: 1207 result_a = intersection_a 1208 for intersection_b, index_b in intersections_b: 1209 if index_b == point: 1210 result_b = intersection_b 1211 result.append((result_a, result_b)) 1212 # note that the result is sorted in a, since we sorted 1213 # intersections_a in the very beginning 1214 1215 return [x for x, y in result], [y for x, y in result] 1216 1217 def join(self, other): 1218 """join other normsubpath inplace 1219 1220 Fails on closed normsubpath. Fails to join closed normsubpath. 1221 """ 1222 if other.closed: 1223 raise NormpathException("Cannot join closed normsubpath") 1224 1225 if self.normsubpathitems: 1226 # insert connection line 1227 x0_pt, y0_pt = self.atend_pt() 1228 x1_pt, y1_pt = other.atbegin_pt() 1229 self.append(normline_pt(x0_pt, y0_pt, x1_pt, y1_pt)) 1230 1231 # append other normsubpathitems 1232 self.extend(other.normsubpathitems) 1233 if other.skippedline: 1234 self.append(other.skippedline) 1235 1236 def joined(self, other): 1237 """return joined self and other 1238 1239 Fails on closed normsubpath. Fails to join closed normsubpath. 1240 """ 1241 result = self.copy() 1242 result.join(other) 1243 return result 1244 1245 def _paramtoarclen_pt(self, params): 1246 """return a tuple of arc lengths and the total arc length in pts""" 1247 if not self.normsubpathitems: 1248 return [0] * len(params), 0 1249 result = [None] * len(params) 1250 totalarclen_pt = 0 1251 distributeparams = self._distributeparams(params) 1252 for normsubpathitemindex in range(len(self.normsubpathitems)): 1253 if normsubpathitemindex in distributeparams: 1254 indices, params = distributeparams[normsubpathitemindex] 1255 arclens_pt, normsubpathitemarclen_pt = self.normsubpathitems[normsubpathitemindex]._paramtoarclen_pt(params, self.epsilon) 1256 for index, arclen_pt in zip(indices, arclens_pt): 1257 result[index] = totalarclen_pt + arclen_pt 1258 totalarclen_pt += normsubpathitemarclen_pt 1259 else: 1260 totalarclen_pt += self.normsubpathitems[normsubpathitemindex].arclen_pt(self.epsilon) 1261 return result, totalarclen_pt 1262 1263 def pathitems(self): 1264 """return list of pathitems""" 1265 1266 from . import path 1267 1268 if not self.normsubpathitems: 1269 return [] 1270 1271 # remove trailing normline_pt of closed subpaths 1272 if self.closed and isinstance(self.normsubpathitems[-1], normline_pt): 1273 normsubpathitems = self.normsubpathitems[:-1] 1274 else: 1275 normsubpathitems = self.normsubpathitems 1276 1277 result = [path.moveto_pt(*self.atbegin_pt())] 1278 for normsubpathitem in normsubpathitems: 1279 result.append(normsubpathitem.pathitem()) 1280 if self.closed: 1281 result.append(path.closepath()) 1282 return result 1283 1284 def reversed(self): 1285 """return reversed normsubpath""" 1286 nnormpathitems = [] 1287 for i in range(len(self.normsubpathitems)): 1288 nnormpathitems.append(self.normsubpathitems[-(i+1)].reversed()) 1289 return normsubpath(nnormpathitems, self.closed, self.epsilon) 1290 1291 def rotation(self, params): 1292 """return rotations at params""" 1293 result = [None] * len(params) 1294 for normsubpathitemindex, (indices, params) in list(self._distributeparams(params).items()): 1295 for index, rotation in zip(indices, self.normsubpathitems[normsubpathitemindex].rotation(params)): 1296 result[index] = rotation 1297 return result 1298 1299 def segments(self, params): 1300 """return segments of the normsubpath 1301 1302 The returned list of normsubpaths for the segments between 1303 the params. params need to contain at least two values. 1304 1305 For a closed normsubpath the last segment result is joined to 1306 the first one when params starts with 0 and ends with len(self). 1307 or params starts with len(self) and ends with 0. Thus a segments 1308 operation on a closed normsubpath might properly join those the 1309 first and the last part to take into account the closed nature of 1310 the normsubpath. However, for intermediate parameters, closepath 1311 is not taken into account, i.e. when walking backwards you do not 1312 loop over the closepath forwardly. The special values 0 and 1313 len(self) for the first and the last parameter should be given as 1314 integers, i.e. no finite precision is used when checking for 1315 equality.""" 1316 1317 if len(params) < 2: 1318 raise ValueError("at least two parameters needed in segments") 1319 if not self.normsubpathitems: 1320 assert not self.closed # "empty" normsubpath cannot be closed 1321 return [self]*(len(params)-1) 1322 1323 result = [normsubpath(epsilon=self.epsilon)] 1324 1325 # instead of distribute the parameters, we need to keep their 1326 # order and collect parameters for the needed segments of 1327 # normsubpathitem with index collectindex 1328 collectparams = [] 1329 collectindex = None 1330 for param in params: 1331 # calculate index and parameter for corresponding normsubpathitem 1332 if param > 0: 1333 index = int(param) 1334 if index > len(self.normsubpathitems) - 1: 1335 index = len(self.normsubpathitems) - 1 1336 param -= index 1337 else: 1338 index = 0 1339 if index != collectindex: 1340 if collectindex is not None: 1341 # append end point depening on the forthcoming index 1342 if index > collectindex: 1343 collectparams.append(1) 1344 else: 1345 collectparams.append(0) 1346 # get segments of the normsubpathitem and add them to the result 1347 segments = self.normsubpathitems[collectindex].segments(collectparams) 1348 result[-1].append(segments[0]) 1349 result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]]) 1350 # add normsubpathitems and first segment parameter to close the 1351 # gap to the forthcoming index 1352 if index > collectindex: 1353 for i in range(collectindex+1, index): 1354 result[-1].append(self.normsubpathitems[i]) 1355 collectparams = [0] 1356 else: 1357 for i in range(collectindex-1, index, -1): 1358 result[-1].append(self.normsubpathitems[i].reversed()) 1359 collectparams = [1] 1360 collectindex = index 1361 collectparams.append(param) 1362 # add remaining collectparams to the result 1363 segments = self.normsubpathitems[collectindex].segments(collectparams) 1364 result[-1].append(segments[0]) 1365 result.extend([normsubpath([segment], epsilon=self.epsilon) for segment in segments[1:]]) 1366 1367 if self.closed: 1368 # join last and first segment together if the normsubpath was 1369 # originally closed and first and the last parameters are the 1370 # beginning and end points of the normsubpath 1371 if ( ( params[0] == 0 and params[-1] == len(self.normsubpathitems) ) or 1372 ( params[-1] == 0 and params[0] == len(self.normsubpathitems) ) ): 1373 result[-1].normsubpathitems.extend(result[0].normsubpathitems) 1374 result = result[-1:] + result[1:-1] 1375 1376 return result 1377 1378 def trafo(self, params): 1379 """return transformations at params""" 1380 result = [None] * len(params) 1381 for normsubpathitemindex, (indices, params) in list(self._distributeparams(params).items()): 1382 for index, trafo in zip(indices, self.normsubpathitems[normsubpathitemindex].trafo(params)): 1383 result[index] = trafo 1384 return result 1385 1386 def transformed(self, trafo): 1387 """return transformed path""" 1388 nnormsubpath = normsubpath(epsilon=self.epsilon) 1389 for pitem in self.normsubpathitems: 1390 nnormsubpath.append(pitem.transformed(trafo)) 1391 if self.closed: 1392 nnormsubpath.close() 1393 elif self.skippedline is not None: 1394 nnormsubpath.append(self.skippedline.transformed(trafo)) 1395 return nnormsubpath 1396 1397 def outputPS(self, file, writer): 1398 # if the normsubpath is closed, we must not output a normline at 1399 # the end 1400 if not self.normsubpathitems: 1401 return 1402 if self.closed and isinstance(self.normsubpathitems[-1], normline_pt): 1403 assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt" 1404 normsubpathitems = self.normsubpathitems[:-1] 1405 else: 1406 normsubpathitems = self.normsubpathitems 1407 file.write("%g %g moveto\n" % self.atbegin_pt()) 1408 for anormsubpathitem in normsubpathitems: 1409 anormsubpathitem.outputPS(file, writer) 1410 if self.closed: 1411 file.write("closepath\n") 1412 1413 def outputPDF(self, file, writer): 1414 # if the normsubpath is closed, we must not output a normline at 1415 # the end 1416 if not self.normsubpathitems: 1417 return 1418 if self.closed and isinstance(self.normsubpathitems[-1], normline_pt): 1419 assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt" 1420 normsubpathitems = self.normsubpathitems[:-1] 1421 else: 1422 normsubpathitems = self.normsubpathitems 1423 file.write("%f %f m\n" % self.atbegin_pt()) 1424 for anormsubpathitem in normsubpathitems: 1425 anormsubpathitem.outputPDF(file, writer) 1426 if self.closed: 1427 file.write("h\n") 1428 1429 def returnSVGdata(self, inverse_y): 1430 # if the normsubpath is closed, we must not output a normline at 1431 # the end 1432 if not self.normsubpathitems: 1433 return "" 1434 if self.closed and isinstance(self.normsubpathitems[-1], normline_pt): 1435 assert len(self.normsubpathitems) > 1, "a closed normsubpath should contain more than a single normline_pt" 1436 normsubpathitems = self.normsubpathitems[:-1] 1437 else: 1438 normsubpathitems = self.normsubpathitems 1439 x_pt, y_pt = self.atbegin_pt() 1440 if inverse_y: 1441 y_pt = -y_pt 1442 data = ["M%g %g" % (x_pt, y_pt)] 1443 for anormsubpathitem in normsubpathitems: 1444 data.append(anormsubpathitem.returnSVGdata(inverse_y)) 1445 if self.closed: 1446 data.append("Z") 1447 return "".join(data) 1448 1449 1450 1451################################################################################ 1452# normpath 1453################################################################################ 1454 1455@functools.total_ordering 1456class normpathparam: 1457 1458 """parameter of a certain point along a normpath""" 1459 1460 __slots__ = "normpath", "normsubpathindex", "normsubpathparam" 1461 1462 def __init__(self, normpath, normsubpathindex, normsubpathparam): 1463 self.normpath = normpath 1464 self.normsubpathindex = normsubpathindex 1465 self.normsubpathparam = normsubpathparam 1466 1467 def __str__(self): 1468 return "normpathparam(%s, %s, %s)" % (self.normpath, self.normsubpathindex, self.normsubpathparam) 1469 1470 def __add__(self, other): 1471 if isinstance(other, normpathparam): 1472 assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath" 1473 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) + 1474 other.normpath.paramtoarclen_pt(other)) 1475 else: 1476 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) + unit.topt(other)) 1477 1478 __radd__ = __add__ 1479 1480 def __sub__(self, other): 1481 if isinstance(other, normpathparam): 1482 assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath" 1483 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) - 1484 other.normpath.paramtoarclen_pt(other)) 1485 else: 1486 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) - unit.topt(other)) 1487 1488 def __rsub__(self, other): 1489 # other has to be a length in this case 1490 return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self) + unit.topt(other)) 1491 1492 def __mul__(self, factor): 1493 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) * factor) 1494 1495 __rmul__ = __mul__ 1496 1497 def __div__(self, divisor): 1498 return self.normpath.arclentoparam_pt(self.normpath.paramtoarclen_pt(self) / divisor) 1499 1500 def __neg__(self): 1501 return self.normpath.arclentoparam_pt(-self.normpath.paramtoarclen_pt(self)) 1502 1503 def __eq__(self, other): 1504 if isinstance(other, normpathparam): 1505 assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath" 1506 return (self.normsubpathindex, self.normsubpathparam) == (other.normsubpathindex, other.normsubpathparam) 1507 else: 1508 return self.normpath.paramtoarclen_pt(self) == unit.topt(other) 1509 1510 def __lt__(self, other): 1511 if isinstance(other, normpathparam): 1512 assert self.normpath is other.normpath, "normpathparams have to belong to the same normpath" 1513 return (self.normsubpathindex, self.normsubpathparam) < (other.normsubpathindex, other.normsubpathparam) 1514 else: 1515 return self.normpath.paramtoarclen_pt(self) < unit.topt(other) 1516 1517 def arclen_pt(self): 1518 """return arc length in pts corresponding to the normpathparam """ 1519 return self.normpath.paramtoarclen_pt(self) 1520 1521 def arclen(self): 1522 """return arc length corresponding to the normpathparam """ 1523 return self.normpath.paramtoarclen(self) 1524 1525 1526def _valueorlistmethod(method): 1527 """Creates a method which takes a single argument or a list and 1528 returns a single value or a list out of method, which always 1529 works on lists.""" 1530 1531 @functools.wraps(method) 1532 def wrappedmethod(self, valueorlist, *args, **kwargs): 1533 try: 1534 for item in valueorlist: 1535 break 1536 except: 1537 return method(self, [valueorlist], *args, **kwargs)[0] 1538 return method(self, valueorlist, *args, **kwargs) 1539 return wrappedmethod 1540 1541 1542class normpath: 1543 1544 """normalized path 1545 1546 A normalized path consists of a list of normsubpaths. 1547 """ 1548 1549 def __init__(self, normsubpaths=None): 1550 """construct a normpath from a list of normsubpaths""" 1551 1552 if normsubpaths is None: 1553 self.normsubpaths = [] # make a fresh list 1554 else: 1555 self.normsubpaths = normsubpaths 1556 for subpath in normsubpaths: 1557 assert isinstance(subpath, normsubpath), "only list of normsubpath instances allowed" 1558 1559 def __add__(self, other): 1560 """create new normpath out of self and other""" 1561 result = self.copy() 1562 result += other 1563 return result 1564 1565 def __iadd__(self, other): 1566 """add other inplace""" 1567 for normsubpath in other.normpath().normsubpaths: 1568 self.normsubpaths.append(normsubpath.copy()) 1569 return self 1570 1571 def __getitem__(self, i): 1572 """return normsubpath i""" 1573 return self.normsubpaths[i] 1574 1575 def __len__(self): 1576 """return the number of normsubpaths""" 1577 return len(self.normsubpaths) 1578 1579 def __str__(self): 1580 return "normpath([%s])" % ", ".join(map(str, self.normsubpaths)) 1581 1582 def _convertparams(self, params, convertmethod): 1583 """return params with all non-normpathparam arguments converted by convertmethod 1584 1585 usecases: 1586 - self._convertparams(params, self.arclentoparam_pt) 1587 - self._convertparams(params, self.arclentoparam) 1588 """ 1589 1590 converttoparams = [] 1591 convertparamindices = [] 1592 for i, param in enumerate(params): 1593 if not isinstance(param, normpathparam): 1594 converttoparams.append(param) 1595 convertparamindices.append(i) 1596 if converttoparams: 1597 params = params[:] 1598 for i, param in zip(convertparamindices, convertmethod(converttoparams)): 1599 params[i] = param 1600 return params 1601 1602 def _distributeparams(self, params): 1603 """return a dictionary mapping subpathindices to a tuple of a paramindices and subpathparams 1604 1605 subpathindex specifies a subpath containing one or several positions. 1606 paramindex specify the index of the normpathparam in the original list and 1607 subpathparam is the parameter value in the subpath. 1608 """ 1609 1610 result = {} 1611 for i, param in enumerate(params): 1612 assert param.normpath is self, "normpathparam has to belong to this path" 1613 result.setdefault(param.normsubpathindex, ([], [])) 1614 result[param.normsubpathindex][0].append(i) 1615 result[param.normsubpathindex][1].append(param.normsubpathparam) 1616 return result 1617 1618 def append(self, item): 1619 """append a normpath by a normsubpath or a pathitem""" 1620 from . import path 1621 if isinstance(item, normsubpath): 1622 # the normsubpaths list can be appended by a normsubpath only 1623 self.normsubpaths.append(item) 1624 elif isinstance(item, path.pathitem): 1625 # ... but we are kind and allow for regular path items as well 1626 # in order to make a normpath to behave more like a regular path 1627 if self.normsubpaths: 1628 context = path.context(*(self.normsubpaths[-1].atend_pt() + 1629 self.normsubpaths[-1].atbegin_pt())) 1630 item.updatenormpath(self, context) 1631 else: 1632 self.normsubpaths = item.createnormpath(self).normsubpaths 1633 1634 def arclen_pt(self, upper=False): 1635 """return arc length in pts 1636 1637 When upper is set, the upper bound is calculated, otherwise the lower 1638 bound is returned.""" 1639 return sum([normsubpath.arclen_pt(upper=upper) for normsubpath in self.normsubpaths]) 1640 1641 def arclen(self, upper=False): 1642 """return arc length 1643 1644 When upper is set, the upper bound is calculated, otherwise the lower 1645 bound is returned.""" 1646 return self.arclen_pt(upper=upper) * unit.t_pt 1647 1648 def _arclentoparam_pt(self, lengths_pt): 1649 """return the params matching the given lengths_pt""" 1650 # work on a copy which is counted down to negative values 1651 lengths_pt = lengths_pt[:] 1652 results = [None] * len(lengths_pt) 1653 1654 for normsubpathindex, normsubpath in enumerate(self.normsubpaths): 1655 params, arclen = normsubpath._arclentoparam_pt(lengths_pt) 1656 done = 1 1657 for i, result in enumerate(results): 1658 if results[i] is None: 1659 lengths_pt[i] -= arclen 1660 if lengths_pt[i] < 0 or normsubpathindex == len(self.normsubpaths) - 1: 1661 # overwrite the results until the length has become negative 1662 results[i] = normpathparam(self, normsubpathindex, params[i]) 1663 done = 0 1664 if done: 1665 break 1666 1667 return results 1668 1669 arclentoparam_pt = _valueorlistmethod(_arclentoparam_pt) 1670 1671 @_valueorlistmethod 1672 def arclentoparam(self, lengths): 1673 """return the param(s) matching the given length(s)""" 1674 return self._arclentoparam_pt([unit.topt(l) for l in lengths]) 1675 1676 def _at_pt(self, params): 1677 """return coordinates of normpath in pts at params""" 1678 result = [None] * len(params) 1679 for normsubpathindex, (indices, params) in list(self._distributeparams(params).items()): 1680 for index, point_pt in zip(indices, self.normsubpaths[normsubpathindex].at_pt(params)): 1681 result[index] = point_pt 1682 return result 1683 1684 @_valueorlistmethod 1685 def at_pt(self, params): 1686 """return coordinates of normpath in pts at param(s) or lengths in pts""" 1687 return self._at_pt(self._convertparams(params, self.arclentoparam_pt)) 1688 1689 @_valueorlistmethod 1690 def at(self, params): 1691 """return coordinates of normpath at param(s) or arc lengths""" 1692 return [(x_pt * unit.t_pt, y_pt * unit.t_pt) 1693 for x_pt, y_pt in self._at_pt(self._convertparams(params, self.arclentoparam))] 1694 1695 def atbegin_pt(self): 1696 """return coordinates of the beginning of first subpath in normpath in pts""" 1697 if self.normsubpaths: 1698 return self.normsubpaths[0].atbegin_pt() 1699 else: 1700 raise NormpathException("cannot return first point of empty path") 1701 1702 def atbegin(self): 1703 """return coordinates of the beginning of first subpath in normpath""" 1704 x, y = self.atbegin_pt() 1705 return x * unit.t_pt, y * unit.t_pt 1706 1707 def atend_pt(self): 1708 """return coordinates of the end of last subpath in normpath in pts""" 1709 if self.normsubpaths: 1710 return self.normsubpaths[-1].atend_pt() 1711 else: 1712 raise NormpathException("cannot return last point of empty path") 1713 1714 def atend(self): 1715 """return coordinates of the end of last subpath in normpath""" 1716 x, y = self.atend_pt() 1717 return x * unit.t_pt, y * unit.t_pt 1718 1719 def bbox(self): 1720 """return bbox of normpath""" 1721 abbox = bboxmodule.empty() 1722 for normsubpath in self.normsubpaths: 1723 abbox += normsubpath.bbox() 1724 return abbox 1725 1726 def begin(self): 1727 """return param corresponding of the beginning of the normpath""" 1728 if self.normsubpaths: 1729 return normpathparam(self, 0, 0) 1730 else: 1731 raise NormpathException("empty path") 1732 1733 def copy(self): 1734 """return copy of normpath""" 1735 result = normpath() 1736 for normsubpath in self.normsubpaths: 1737 result.append(normsubpath.copy()) 1738 return result 1739 1740 @_valueorlistmethod 1741 def curvature_pt(self, params): 1742 """return the curvature in 1/pt at params or arc length(s) in pts""" 1743 1744 result = [None] * len(params) 1745 for normsubpathindex, (indices, params) in list(self._distributeparams(self._convertparams(params, self.arclentoparam_pt)).items()): 1746 for index, curvature_pt in zip(indices, self.normsubpaths[normsubpathindex].curvature_pt(params)): 1747 result[index] = curvature_pt 1748 return result 1749 1750 def end(self): 1751 """return param corresponding of the end of the path""" 1752 if self.normsubpaths: 1753 return normpathparam(self, len(self)-1, len(self.normsubpaths[-1])) 1754 else: 1755 raise NormpathException("empty path") 1756 1757 def extend(self, normsubpaths): 1758 """extend path by normsubpaths or pathitems""" 1759 for anormsubpath in normsubpaths: 1760 # use append to properly handle regular path items as well as normsubpaths 1761 self.append(anormsubpath) 1762 1763 def intersect(self, other): 1764 """intersect self with other path 1765 1766 Returns a tuple of lists consisting of the parameter values 1767 of the intersection points of the corresponding normpath. 1768 """ 1769 other = other.normpath() 1770 1771 # here we build up the result 1772 intersections = ([], []) 1773 1774 # Intersect all normsubpaths of self with the normsubpaths of 1775 # other. 1776 for ia, normsubpath_a in enumerate(self.normsubpaths): 1777 for ib, normsubpath_b in enumerate(other.normsubpaths): 1778 for intersection in zip(*normsubpath_a.intersect(normsubpath_b)): 1779 intersections[0].append(normpathparam(self, ia, intersection[0])) 1780 intersections[1].append(normpathparam(other, ib, intersection[1])) 1781 return intersections 1782 1783 def join(self, other): 1784 """join other normsubpath inplace 1785 1786 Both normpaths must contain at least one normsubpath. 1787 The last normsubpath of self will be joined to the first 1788 normsubpath of other. 1789 """ 1790 other = other.normpath() 1791 1792 if not self.normsubpaths: 1793 raise NormpathException("cannot join to empty path") 1794 if not other.normsubpaths: 1795 raise NormpathException("cannot join empty path") 1796 self.normsubpaths[-1].join(other.normsubpaths[0]) 1797 self.normsubpaths.extend(other.normsubpaths[1:]) 1798 1799 def joined(self, other): 1800 """return joined self and other 1801 1802 Both normpaths must contain at least one normsubpath. 1803 The last normsubpath of self will be joined to the first 1804 normsubpath of other. 1805 """ 1806 result = self.copy() 1807 result.join(other.normpath()) 1808 return result 1809 1810 # << operator also designates joining 1811 __lshift__ = joined 1812 1813 def normpath(self): 1814 """return a normpath, i.e. self""" 1815 return self 1816 1817 def _paramtoarclen_pt(self, params): 1818 """return arc lengths in pts matching the given params""" 1819 result = [None] * len(params) 1820 totalarclen_pt = 0 1821 distributeparams = self._distributeparams(params) 1822 for normsubpathindex in range(max(distributeparams.keys()) + 1): 1823 if normsubpathindex in distributeparams: 1824 indices, params = distributeparams[normsubpathindex] 1825 arclens_pt, normsubpatharclen_pt = self.normsubpaths[normsubpathindex]._paramtoarclen_pt(params) 1826 for index, arclen_pt in zip(indices, arclens_pt): 1827 result[index] = totalarclen_pt + arclen_pt 1828 totalarclen_pt += normsubpatharclen_pt 1829 else: 1830 totalarclen_pt += self.normsubpaths[normsubpathindex].arclen_pt() 1831 return result 1832 1833 paramtoarclen_pt = _valueorlistmethod(_paramtoarclen_pt) 1834 1835 @_valueorlistmethod 1836 def paramtoarclen(self, params): 1837 """return arc length(s) matching the given param(s)""" 1838 return [arclen_pt * unit.t_pt for arclen_pt in self._paramtoarclen_pt(params)] 1839 1840 def path(self): 1841 """return path corresponding to normpath""" 1842 from . import path 1843 pathitems = [] 1844 for normsubpath in self.normsubpaths: 1845 pathitems.extend(normsubpath.pathitems()) 1846 return path.path(*pathitems) 1847 1848 def reversed(self): 1849 """return reversed path""" 1850 nnormpath = normpath() 1851 for i in range(len(self.normsubpaths)): 1852 nnormpath.normsubpaths.append(self.normsubpaths[-(i+1)].reversed()) 1853 return nnormpath 1854 1855 def _rotation(self, params): 1856 """return rotation at params""" 1857 result = [None] * len(params) 1858 for normsubpathindex, (indices, params) in list(self._distributeparams(params).items()): 1859 for index, rotation in zip(indices, self.normsubpaths[normsubpathindex].rotation(params)): 1860 result[index] = rotation 1861 return result 1862 1863 @_valueorlistmethod 1864 def rotation_pt(self, params): 1865 """return rotation at param(s) or arc length(s) in pts""" 1866 return self._rotation(self._convertparams(params, self.arclentoparam_pt)) 1867 1868 @_valueorlistmethod 1869 def rotation(self, params): 1870 """return rotation at param(s) or arc length(s)""" 1871 return self._rotation(self._convertparams(params, self.arclentoparam)) 1872 1873 def _split_pt(self, params): 1874 """split path at params and return list of normpaths""" 1875 if not params: 1876 return [self.copy()] 1877 1878 # instead of distributing the parameters, we need to keep their 1879 # order and collect parameters for splitting of normsubpathitem 1880 # with index collectindex 1881 collectindex = None 1882 for param in params: 1883 if param.normsubpathindex != collectindex: 1884 if collectindex is not None: 1885 # append end point depening on the forthcoming index 1886 if param.normsubpathindex > collectindex: 1887 collectparams.append(len(self.normsubpaths[collectindex])) 1888 else: 1889 collectparams.append(0) 1890 # get segments of the normsubpath and add them to the result 1891 segments = self.normsubpaths[collectindex].segments(collectparams) 1892 result[-1].append(segments[0]) 1893 result.extend([normpath([segment]) for segment in segments[1:]]) 1894 # add normsubpathitems and first segment parameter to close the 1895 # gap to the forthcoming index 1896 if param.normsubpathindex > collectindex: 1897 for i in range(collectindex+1, param.normsubpathindex): 1898 result[-1].append(self.normsubpaths[i]) 1899 collectparams = [0] 1900 else: 1901 for i in range(collectindex-1, param.normsubpathindex, -1): 1902 result[-1].append(self.normsubpaths[i].reversed()) 1903 collectparams = [len(self.normsubpaths[param.normsubpathindex])] 1904 else: 1905 result = [normpath(self.normsubpaths[:param.normsubpathindex])] 1906 collectparams = [0] 1907 collectindex = param.normsubpathindex 1908 collectparams.append(param.normsubpathparam) 1909 # add remaining collectparams to the result 1910 collectparams.append(len(self.normsubpaths[collectindex])) 1911 segments = self.normsubpaths[collectindex].segments(collectparams) 1912 result[-1].append(segments[0]) 1913 result.extend([normpath([segment]) for segment in segments[1:]]) 1914 result[-1].extend(self.normsubpaths[collectindex+1:]) 1915 return result 1916 1917 def split_pt(self, params): 1918 """split path at param(s) or arc length(s) in pts and return list of normpaths""" 1919 try: 1920 for param in params: 1921 break 1922 except: 1923 params = [params] 1924 return self._split_pt(self._convertparams(params, self.arclentoparam_pt)) 1925 1926 def split(self, params): 1927 """split path at param(s) or arc length(s) and return list of normpaths""" 1928 try: 1929 for param in params: 1930 break 1931 except: 1932 params = [params] 1933 return self._split_pt(self._convertparams(params, self.arclentoparam)) 1934 1935 def _tangent(self, params, length_pt): 1936 """return tangent vector of path at params 1937 1938 If length_pt in pts is not None, the tangent vector will be scaled to 1939 the desired length. 1940 """ 1941 from . import path 1942 result = [None] * len(params) 1943 tangenttemplate = path.line_pt(0, 0, length_pt, 0).normpath() 1944 for normsubpathindex, (indices, params) in list(self._distributeparams(params).items()): 1945 for index, atrafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)): 1946 result[index] = tangenttemplate.transformed(atrafo) 1947 return result 1948 1949 @_valueorlistmethod 1950 def tangent_pt(self, params, length_pt): 1951 """return tangent vector of path at param(s) or arc length(s) in pts 1952 1953 If length in pts is not None, the tangent vector will be scaled to 1954 the desired length. 1955 """ 1956 return self._tangent(self._convertparams(params, self.arclentoparam_pt), length_pt) 1957 1958 @_valueorlistmethod 1959 def tangent(self, params, length=1): 1960 """return tangent vector of path at param(s) or arc length(s) 1961 1962 If length is not None, the tangent vector will be scaled to 1963 the desired length. 1964 """ 1965 return self._tangent(self._convertparams(params, self.arclentoparam), unit.topt(length)) 1966 1967 def _trafo(self, params): 1968 """return transformation at params""" 1969 result = [None] * len(params) 1970 for normsubpathindex, (indices, params) in list(self._distributeparams(params).items()): 1971 for index, trafo in zip(indices, self.normsubpaths[normsubpathindex].trafo(params)): 1972 result[index] = trafo 1973 return result 1974 1975 @_valueorlistmethod 1976 def trafo_pt(self, params): 1977 """return transformation at param(s) or arc length(s) in pts""" 1978 return self._trafo(self._convertparams(params, self.arclentoparam_pt)) 1979 1980 @_valueorlistmethod 1981 def trafo(self, params): 1982 """return transformation at param(s) or arc length(s)""" 1983 return self._trafo(self._convertparams(params, self.arclentoparam)) 1984 1985 def transformed(self, trafo): 1986 """return transformed normpath""" 1987 return normpath([normsubpath.transformed(trafo) for normsubpath in self.normsubpaths]) 1988 1989 def outputPS(self, file, writer): 1990 for normsubpath in self.normsubpaths: 1991 normsubpath.outputPS(file, writer) 1992 1993 def outputPDF(self, file, writer): 1994 for normsubpath in self.normsubpaths: 1995 normsubpath.outputPDF(file, writer) 1996 1997 def returnSVGdata(self, inverse_y=True): 1998 return "".join(normsubpath.returnSVGdata(inverse_y) for normsubpath in self.normsubpaths) 1999 2000