Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1""" 

2A module providing some utility functions regarding Bezier path manipulation. 

3""" 

4 

5import numpy as np 

6 

7import matplotlib.cbook as cbook 

8from matplotlib.path import Path 

9 

10 

11class NonIntersectingPathException(ValueError): 

12 pass 

13 

14# some functions 

15 

16 

17def get_intersection(cx1, cy1, cos_t1, sin_t1, 

18 cx2, cy2, cos_t2, sin_t2): 

19 """ 

20 Return the intersection between the line through (*cx1*, *cy1*) at angle 

21 *t1* and the line through (*cx2*, *cy2*) at angle *t2*. 

22 """ 

23 

24 # line1 => sin_t1 * (x - cx1) - cos_t1 * (y - cy1) = 0. 

25 # line1 => sin_t1 * x + cos_t1 * y = sin_t1*cx1 - cos_t1*cy1 

26 

27 line1_rhs = sin_t1 * cx1 - cos_t1 * cy1 

28 line2_rhs = sin_t2 * cx2 - cos_t2 * cy2 

29 

30 # rhs matrix 

31 a, b = sin_t1, -cos_t1 

32 c, d = sin_t2, -cos_t2 

33 

34 ad_bc = a * d - b * c 

35 if np.abs(ad_bc) < 1.0e-12: 

36 raise ValueError("Given lines do not intersect. Please verify that " 

37 "the angles are not equal or differ by 180 degrees.") 

38 

39 # rhs_inverse 

40 a_, b_ = d, -b 

41 c_, d_ = -c, a 

42 a_, b_, c_, d_ = [k / ad_bc for k in [a_, b_, c_, d_]] 

43 

44 x = a_ * line1_rhs + b_ * line2_rhs 

45 y = c_ * line1_rhs + d_ * line2_rhs 

46 

47 return x, y 

48 

49 

50def get_normal_points(cx, cy, cos_t, sin_t, length): 

51 """ 

52 For a line passing through (*cx*, *cy*) and having an angle *t*, return 

53 locations of the two points located along its perpendicular line at the 

54 distance of *length*. 

55 """ 

56 

57 if length == 0.: 

58 return cx, cy, cx, cy 

59 

60 cos_t1, sin_t1 = sin_t, -cos_t 

61 cos_t2, sin_t2 = -sin_t, cos_t 

62 

63 x1, y1 = length * cos_t1 + cx, length * sin_t1 + cy 

64 x2, y2 = length * cos_t2 + cx, length * sin_t2 + cy 

65 

66 return x1, y1, x2, y2 

67 

68 

69# BEZIER routines 

70 

71# subdividing bezier curve 

72# http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html 

73 

74 

75def _de_casteljau1(beta, t): 

76 next_beta = beta[:-1] * (1 - t) + beta[1:] * t 

77 return next_beta 

78 

79 

80def split_de_casteljau(beta, t): 

81 """ 

82 Split a Bezier segment defined by its control points *beta* into two 

83 separate segments divided at *t* and return their control points. 

84 """ 

85 beta = np.asarray(beta) 

86 beta_list = [beta] 

87 while True: 

88 beta = _de_casteljau1(beta, t) 

89 beta_list.append(beta) 

90 if len(beta) == 1: 

91 break 

92 left_beta = [beta[0] for beta in beta_list] 

93 right_beta = [beta[-1] for beta in reversed(beta_list)] 

94 

95 return left_beta, right_beta 

96 

97 

98@cbook._rename_parameter("3.1", "tolerence", "tolerance") 

99def find_bezier_t_intersecting_with_closedpath( 

100 bezier_point_at_t, inside_closedpath, t0=0., t1=1., tolerance=0.01): 

101 """ 

102 Find the intersection of the Bezier curve with a closed path. 

103 

104 The intersection point *t* is approximated by two parameters *t0*, *t1* 

105 such that *t0* <= *t* <= *t1*. 

106 

107 Search starts from *t0* and *t1* and uses a simple bisecting algorithm 

108 therefore one of the end points must be inside the path while the other 

109 doesn't. The search stops when the distance of the points parametrized by 

110 *t0* and *t1* gets smaller than the given *tolerance*. 

111 

112 Parameters 

113 ---------- 

114 bezier_point_at_t : callable 

115 A function returning x, y coordinates of the Bezier at parameter *t*. 

116 It must have the signature:: 

117 

118 bezier_point_at_t(t: float) -> Tuple[float, float] 

119 

120 inside_closedpath : callable 

121 A function returning True if a given point (x, y) is inside the 

122 closed path. It must have the signature:: 

123 

124 inside_closedpath(point: Tuple[float, float]) -> bool 

125 

126 t0, t1 : float 

127 Start parameters for the search. 

128 

129 tolerance : float 

130 Maximal allowed distance between the final points. 

131 

132 Returns 

133 ------- 

134 t0, t1 : float 

135 The Bezier path parameters. 

136 """ 

137 start = bezier_point_at_t(t0) 

138 end = bezier_point_at_t(t1) 

139 

140 start_inside = inside_closedpath(start) 

141 end_inside = inside_closedpath(end) 

142 

143 if start_inside == end_inside and start != end: 

144 raise NonIntersectingPathException( 

145 "Both points are on the same side of the closed path") 

146 

147 while True: 

148 

149 # return if the distance is smaller than the tolerance 

150 if np.hypot(start[0] - end[0], start[1] - end[1]) < tolerance: 

151 return t0, t1 

152 

153 # calculate the middle point 

154 middle_t = 0.5 * (t0 + t1) 

155 middle = bezier_point_at_t(middle_t) 

156 middle_inside = inside_closedpath(middle) 

157 

158 if start_inside ^ middle_inside: 

159 t1 = middle_t 

160 end = middle 

161 end_inside = middle_inside 

162 else: 

163 t0 = middle_t 

164 start = middle 

165 start_inside = middle_inside 

166 

167 

168class BezierSegment: 

169 """ 

170 A 2-dimensional Bezier segment. 

171 

172 Parameters 

173 ---------- 

174 control_points : array-like (N, 2) 

175 A list of the (x, y) positions of control points of the Bezier line. 

176 This must contain N points, where N is the order of the Bezier line. 

177 1 <= N <= 3 is supported. 

178 """ 

179 # Higher order Bezier lines can be supported by simplying adding 

180 # corresponding values. 

181 _binom_coeff = {1: np.array([1., 1.]), 

182 2: np.array([1., 2., 1.]), 

183 3: np.array([1., 3., 3., 1.])} 

184 

185 def __init__(self, control_points): 

186 _o = len(control_points) 

187 self._orders = np.arange(_o) 

188 

189 _coeff = BezierSegment._binom_coeff[_o - 1] 

190 xx, yy = np.asarray(control_points).T 

191 self._px = xx * _coeff 

192 self._py = yy * _coeff 

193 

194 def point_at_t(self, t): 

195 """Return the point (x, y) at parameter *t*.""" 

196 tt = ((1 - t) ** self._orders)[::-1] * t ** self._orders 

197 _x = np.dot(tt, self._px) 

198 _y = np.dot(tt, self._py) 

199 return _x, _y 

200 

201 

202@cbook._rename_parameter("3.1", "tolerence", "tolerance") 

203def split_bezier_intersecting_with_closedpath( 

204 bezier, inside_closedpath, tolerance=0.01): 

205 """ 

206 Split a Bezier curve into two at the intersection with a closed path. 

207 

208 Parameters 

209 ---------- 

210 bezier : array-like(N, 2) 

211 Control points of the Bezier segment. See `.BezierSegment`. 

212 inside_closedpath : callable 

213 A function returning True if a given point (x, y) is inside the 

214 closed path. See also `.find_bezier_t_intersecting_with_closedpath`. 

215 tolerance : float 

216 The tolerance for the intersection. See also 

217 `.find_bezier_t_intersecting_with_closedpath`. 

218 

219 Returns 

220 ------- 

221 left, right 

222 Lists of control points for the two Bezier segments. 

223 """ 

224 

225 bz = BezierSegment(bezier) 

226 bezier_point_at_t = bz.point_at_t 

227 

228 t0, t1 = find_bezier_t_intersecting_with_closedpath( 

229 bezier_point_at_t, inside_closedpath, tolerance=tolerance) 

230 

231 _left, _right = split_de_casteljau(bezier, (t0 + t1) / 2.) 

232 return _left, _right 

233 

234 

235@cbook.deprecated("3.1") 

236@cbook._rename_parameter("3.1", "tolerence", "tolerance") 

237def find_r_to_boundary_of_closedpath( 

238 inside_closedpath, xy, cos_t, sin_t, rmin=0., rmax=1., tolerance=0.01): 

239 """ 

240 Find a radius r (centered at *xy*) between *rmin* and *rmax* at 

241 which it intersect with the path. 

242 

243 Parameters 

244 ---------- 

245 inside_closedpath : callable 

246 A function returning True if a given point (x, y) is inside the 

247 closed path. 

248 xy : float, float 

249 The center of the radius. 

250 cos_t, sin_t : float 

251 Cosine and sine for the angle. 

252 rmin, rmax : float 

253 Starting parameters for the radius search. 

254 """ 

255 cx, cy = xy 

256 

257 def _f(r): 

258 return cos_t * r + cx, sin_t * r + cy 

259 

260 find_bezier_t_intersecting_with_closedpath( 

261 _f, inside_closedpath, t0=rmin, t1=rmax, tolerance=tolerance) 

262 

263# matplotlib specific 

264 

265 

266@cbook._rename_parameter("3.1", "tolerence", "tolerance") 

267def split_path_inout(path, inside, tolerance=0.01, reorder_inout=False): 

268 """ 

269 Divide a path into two segments at the point where ``inside(x, y)`` becomes 

270 False. 

271 """ 

272 path_iter = path.iter_segments() 

273 

274 ctl_points, command = next(path_iter) 

275 begin_inside = inside(ctl_points[-2:]) # true if begin point is inside 

276 

277 ctl_points_old = ctl_points 

278 

279 concat = np.concatenate 

280 

281 iold = 0 

282 i = 1 

283 

284 for ctl_points, command in path_iter: 

285 iold = i 

286 i += len(ctl_points) // 2 

287 if inside(ctl_points[-2:]) != begin_inside: 

288 bezier_path = concat([ctl_points_old[-2:], ctl_points]) 

289 break 

290 ctl_points_old = ctl_points 

291 else: 

292 raise ValueError("The path does not intersect with the patch") 

293 

294 bp = bezier_path.reshape((-1, 2)) 

295 left, right = split_bezier_intersecting_with_closedpath( 

296 bp, inside, tolerance) 

297 if len(left) == 2: 

298 codes_left = [Path.LINETO] 

299 codes_right = [Path.MOVETO, Path.LINETO] 

300 elif len(left) == 3: 

301 codes_left = [Path.CURVE3, Path.CURVE3] 

302 codes_right = [Path.MOVETO, Path.CURVE3, Path.CURVE3] 

303 elif len(left) == 4: 

304 codes_left = [Path.CURVE4, Path.CURVE4, Path.CURVE4] 

305 codes_right = [Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4] 

306 else: 

307 raise AssertionError("This should never be reached") 

308 

309 verts_left = left[1:] 

310 verts_right = right[:] 

311 

312 if path.codes is None: 

313 path_in = Path(concat([path.vertices[:i], verts_left])) 

314 path_out = Path(concat([verts_right, path.vertices[i:]])) 

315 

316 else: 

317 path_in = Path(concat([path.vertices[:iold], verts_left]), 

318 concat([path.codes[:iold], codes_left])) 

319 

320 path_out = Path(concat([verts_right, path.vertices[i:]]), 

321 concat([codes_right, path.codes[i:]])) 

322 

323 if reorder_inout and not begin_inside: 

324 path_in, path_out = path_out, path_in 

325 

326 return path_in, path_out 

327 

328 

329def inside_circle(cx, cy, r): 

330 """ 

331 Return a function that checks whether a point is in a circle with center 

332 (*cx*, *cy*) and radius *r*. 

333 

334 The returned function has the signature:: 

335 

336 f(xy: Tuple[float, float]) -> bool 

337 """ 

338 r2 = r ** 2 

339 

340 def _f(xy): 

341 x, y = xy 

342 return (x - cx) ** 2 + (y - cy) ** 2 < r2 

343 return _f 

344 

345 

346# quadratic Bezier lines 

347 

348def get_cos_sin(x0, y0, x1, y1): 

349 dx, dy = x1 - x0, y1 - y0 

350 d = (dx * dx + dy * dy) ** .5 

351 # Account for divide by zero 

352 if d == 0: 

353 return 0.0, 0.0 

354 return dx / d, dy / d 

355 

356 

357@cbook._rename_parameter("3.1", "tolerence", "tolerance") 

358def check_if_parallel(dx1, dy1, dx2, dy2, tolerance=1.e-5): 

359 """ 

360 Check if two lines are parallel. 

361 

362 Parameters 

363 ---------- 

364 dx1, dy1, dx2, dy2 : float 

365 The gradients *dy*/*dx* of the two lines. 

366 tolerance : float 

367 The angular tolerance in radians up to which the lines are considered 

368 parallel. 

369 

370 Returns 

371 ------- 

372 is_parallel 

373 - 1 if two lines are parallel in same direction. 

374 - -1 if two lines are parallel in opposite direction. 

375 - False otherwise. 

376 """ 

377 theta1 = np.arctan2(dx1, dy1) 

378 theta2 = np.arctan2(dx2, dy2) 

379 dtheta = np.abs(theta1 - theta2) 

380 if dtheta < tolerance: 

381 return 1 

382 elif np.abs(dtheta - np.pi) < tolerance: 

383 return -1 

384 else: 

385 return False 

386 

387 

388def get_parallels(bezier2, width): 

389 """ 

390 Given the quadratic Bezier control points *bezier2*, returns 

391 control points of quadratic Bezier lines roughly parallel to given 

392 one separated by *width*. 

393 """ 

394 

395 # The parallel Bezier lines are constructed by following ways. 

396 # c1 and c2 are control points representing the begin and end of the 

397 # Bezier line. 

398 # cm is the middle point 

399 

400 c1x, c1y = bezier2[0] 

401 cmx, cmy = bezier2[1] 

402 c2x, c2y = bezier2[2] 

403 

404 parallel_test = check_if_parallel(c1x - cmx, c1y - cmy, 

405 cmx - c2x, cmy - c2y) 

406 

407 if parallel_test == -1: 

408 cbook._warn_external( 

409 "Lines do not intersect. A straight line is used instead.") 

410 cos_t1, sin_t1 = get_cos_sin(c1x, c1y, c2x, c2y) 

411 cos_t2, sin_t2 = cos_t1, sin_t1 

412 else: 

413 # t1 and t2 is the angle between c1 and cm, cm, c2. They are 

414 # also a angle of the tangential line of the path at c1 and c2 

415 cos_t1, sin_t1 = get_cos_sin(c1x, c1y, cmx, cmy) 

416 cos_t2, sin_t2 = get_cos_sin(cmx, cmy, c2x, c2y) 

417 

418 # find c1_left, c1_right which are located along the lines 

419 # through c1 and perpendicular to the tangential lines of the 

420 # Bezier path at a distance of width. Same thing for c2_left and 

421 # c2_right with respect to c2. 

422 c1x_left, c1y_left, c1x_right, c1y_right = ( 

423 get_normal_points(c1x, c1y, cos_t1, sin_t1, width) 

424 ) 

425 c2x_left, c2y_left, c2x_right, c2y_right = ( 

426 get_normal_points(c2x, c2y, cos_t2, sin_t2, width) 

427 ) 

428 

429 # find cm_left which is the intersecting point of a line through 

430 # c1_left with angle t1 and a line through c2_left with angle 

431 # t2. Same with cm_right. 

432 try: 

433 cmx_left, cmy_left = get_intersection(c1x_left, c1y_left, cos_t1, 

434 sin_t1, c2x_left, c2y_left, 

435 cos_t2, sin_t2) 

436 cmx_right, cmy_right = get_intersection(c1x_right, c1y_right, cos_t1, 

437 sin_t1, c2x_right, c2y_right, 

438 cos_t2, sin_t2) 

439 except ValueError: 

440 # Special case straight lines, i.e., angle between two lines is 

441 # less than the threshold used by get_intersection (we don't use 

442 # check_if_parallel as the threshold is not the same). 

443 cmx_left, cmy_left = ( 

444 0.5 * (c1x_left + c2x_left), 0.5 * (c1y_left + c2y_left) 

445 ) 

446 cmx_right, cmy_right = ( 

447 0.5 * (c1x_right + c2x_right), 0.5 * (c1y_right + c2y_right) 

448 ) 

449 

450 # the parallel Bezier lines are created with control points of 

451 # [c1_left, cm_left, c2_left] and [c1_right, cm_right, c2_right] 

452 path_left = [(c1x_left, c1y_left), 

453 (cmx_left, cmy_left), 

454 (c2x_left, c2y_left)] 

455 path_right = [(c1x_right, c1y_right), 

456 (cmx_right, cmy_right), 

457 (c2x_right, c2y_right)] 

458 

459 return path_left, path_right 

460 

461 

462def find_control_points(c1x, c1y, mmx, mmy, c2x, c2y): 

463 """ 

464 Find control points of the Bezier curve passing through (*c1x*, *c1y*), 

465 (*mmx*, *mmy*), and (*c2x*, *c2y*), at parametric values 0, 0.5, and 1. 

466 """ 

467 cmx = .5 * (4 * mmx - (c1x + c2x)) 

468 cmy = .5 * (4 * mmy - (c1y + c2y)) 

469 return [(c1x, c1y), (cmx, cmy), (c2x, c2y)] 

470 

471 

472def make_wedged_bezier2(bezier2, width, w1=1., wm=0.5, w2=0.): 

473 """ 

474 Being similar to get_parallels, returns control points of two quadratic 

475 Bezier lines having a width roughly parallel to given one separated by 

476 *width*. 

477 """ 

478 

479 # c1, cm, c2 

480 c1x, c1y = bezier2[0] 

481 cmx, cmy = bezier2[1] 

482 c3x, c3y = bezier2[2] 

483 

484 # t1 and t2 is the angle between c1 and cm, cm, c3. 

485 # They are also a angle of the tangential line of the path at c1 and c3 

486 cos_t1, sin_t1 = get_cos_sin(c1x, c1y, cmx, cmy) 

487 cos_t2, sin_t2 = get_cos_sin(cmx, cmy, c3x, c3y) 

488 

489 # find c1_left, c1_right which are located along the lines 

490 # through c1 and perpendicular to the tangential lines of the 

491 # Bezier path at a distance of width. Same thing for c3_left and 

492 # c3_right with respect to c3. 

493 c1x_left, c1y_left, c1x_right, c1y_right = ( 

494 get_normal_points(c1x, c1y, cos_t1, sin_t1, width * w1) 

495 ) 

496 c3x_left, c3y_left, c3x_right, c3y_right = ( 

497 get_normal_points(c3x, c3y, cos_t2, sin_t2, width * w2) 

498 ) 

499 

500 # find c12, c23 and c123 which are middle points of c1-cm, cm-c3 and 

501 # c12-c23 

502 c12x, c12y = (c1x + cmx) * .5, (c1y + cmy) * .5 

503 c23x, c23y = (cmx + c3x) * .5, (cmy + c3y) * .5 

504 c123x, c123y = (c12x + c23x) * .5, (c12y + c23y) * .5 

505 

506 # tangential angle of c123 (angle between c12 and c23) 

507 cos_t123, sin_t123 = get_cos_sin(c12x, c12y, c23x, c23y) 

508 

509 c123x_left, c123y_left, c123x_right, c123y_right = ( 

510 get_normal_points(c123x, c123y, cos_t123, sin_t123, width * wm) 

511 ) 

512 

513 path_left = find_control_points(c1x_left, c1y_left, 

514 c123x_left, c123y_left, 

515 c3x_left, c3y_left) 

516 path_right = find_control_points(c1x_right, c1y_right, 

517 c123x_right, c123y_right, 

518 c3x_right, c3y_right) 

519 

520 return path_left, path_right 

521 

522 

523def make_path_regular(p): 

524 """ 

525 If the :attr:`codes` attribute of `Path` *p* is None, return a copy of *p* 

526 with the :attr:`codes` set to (MOVETO, LINETO, LINETO, ..., LINETO); 

527 otherwise return *p* itself. 

528 """ 

529 c = p.codes 

530 if c is None: 

531 c = np.full(len(p.vertices), Path.LINETO, dtype=Path.code_type) 

532 c[0] = Path.MOVETO 

533 return Path(p.vertices, c) 

534 else: 

535 return p 

536 

537 

538def concatenate_paths(paths): 

539 """Concatenate a list of paths into a single path.""" 

540 vertices = np.concatenate([p.vertices for p in paths]) 

541 codes = np.concatenate([make_path_regular(p).codes for p in paths]) 

542 return Path(vertices, codes)