1const STRAIGHT_THRESHOLD: f32 = 20.0;
6
7#[derive(Clone, Copy, Debug, PartialEq)]
15pub struct CubicBezier {
16 pub p0: (f32, f32), pub p1: (f32, f32), pub p2: (f32, f32), pub p3: (f32, f32), }
21
22impl CubicBezier {
23 pub fn from_endpoints(
31 start_x: f32,
32 start_y: f32,
33 end_x: f32,
34 end_y: f32,
35 zoom: f32,
36 min_offset: f32,
37 ) -> Self {
38 let dx = end_x - start_x;
39 let dy = end_y - start_y;
40 let dist_sq = dx * dx + dy * dy;
41 let threshold = STRAIGHT_THRESHOLD * zoom;
42
43 if dist_sq < threshold * threshold {
44 return CubicBezier {
47 p0: (start_x, start_y),
48 p1: (start_x, start_y),
49 p2: (end_x, end_y),
50 p3: (end_x, end_y),
51 };
52 }
53
54 let dist = dist_sq.sqrt();
55 let full_offset = (dx.abs() * 0.5).max(min_offset * zoom);
56 let ramp = ((dist - threshold) / (3.0 * threshold)).clamp(0.0, 1.0);
57 let offset = full_offset * ramp;
58
59 let sign = if dx >= 0.0 { 1.0 } else { -1.0 };
61 CubicBezier {
62 p0: (start_x, start_y),
63 p1: (start_x + sign * offset, start_y),
64 p2: (end_x - sign * offset, end_y),
65 p3: (end_x, end_y),
66 }
67 }
68
69 pub fn is_straight(&self) -> bool {
71 self.p1 == self.p0 && self.p2 == self.p3
72 }
73
74 pub fn commands_from(&self, origin: (f32, f32)) -> String {
79 let (ox, oy) = origin;
80 if self.is_straight() {
81 return format!(
82 "M {} {} L {} {}",
83 self.p0.0 - ox,
84 self.p0.1 - oy,
85 self.p3.0 - ox,
86 self.p3.1 - oy
87 );
88 }
89 format!(
90 "M {} {} C {} {} {} {} {} {}",
91 self.p0.0 - ox,
92 self.p0.1 - oy,
93 self.p1.0 - ox,
94 self.p1.1 - oy,
95 self.p2.0 - ox,
96 self.p2.1 - oy,
97 self.p3.0 - ox,
98 self.p3.1 - oy
99 )
100 }
101
102 pub fn bounds(&self) -> (f32, f32, f32, f32) {
109 let xs = [self.p0.0, self.p1.0, self.p2.0, self.p3.0];
110 let ys = [self.p0.1, self.p1.1, self.p2.1, self.p3.1];
111 let min_x = xs.iter().copied().fold(f32::INFINITY, f32::min);
112 let max_x = xs.iter().copied().fold(f32::NEG_INFINITY, f32::max);
113 let min_y = ys.iter().copied().fold(f32::INFINITY, f32::min);
114 let max_y = ys.iter().copied().fold(f32::NEG_INFINITY, f32::max);
115 (min_x, min_y, max_x - min_x, max_y - min_y)
116 }
117
118 pub fn to_link_path<T>(&self, make: impl FnOnce(String, f32, f32, f32, f32) -> T) -> T {
125 let (x, y, width, height) = self.bounds();
126 make(self.commands_from((x, y)), x, y, width, height)
127 }
128
129 pub fn split_at(&self, t: f32) -> CubicBezier {
131 let q0 = lerp_point(self.p0, self.p1, t);
132 let q1 = lerp_point(self.p1, self.p2, t);
133 let q2 = lerp_point(self.p2, self.p3, t);
134
135 let r0 = lerp_point(q0, q1, t);
136 let r1 = lerp_point(q1, q2, t);
137
138 let s = lerp_point(r0, r1, t);
139
140 CubicBezier {
141 p0: self.p0,
142 p1: q0,
143 p2: r0,
144 p3: s,
145 }
146 }
147
148 pub fn eval(&self, t: f32) -> (f32, f32) {
150 let t2 = t * t;
151 let t3 = t2 * t;
152 let mt = 1.0 - t;
153 let mt2 = mt * mt;
154 let mt3 = mt2 * mt;
155
156 let x = mt3 * self.p0.0
157 + 3.0 * mt2 * t * self.p1.0
158 + 3.0 * mt * t2 * self.p2.0
159 + t3 * self.p3.0;
160 let y = mt3 * self.p0.1
161 + 3.0 * mt2 * t * self.p1.1
162 + 3.0 * mt * t2 * self.p2.1
163 + t3 * self.p3.1;
164
165 (x, y)
166 }
167}
168
169pub fn generate_bezier_path(
183 start_x: f32,
184 start_y: f32,
185 end_x: f32,
186 end_y: f32,
187 zoom: f32,
188 min_offset: f32,
189) -> String {
190 CubicBezier::from_endpoints(start_x, start_y, end_x, end_y, zoom, min_offset)
191 .commands_from((0.0, 0.0))
192}
193
194pub fn generate_partial_bezier_path(
208 start_x: f32,
209 start_y: f32,
210 end_x: f32,
211 end_y: f32,
212 zoom: f32,
213 min_offset: f32,
214 progress: f32,
215) -> String {
216 let t = progress.clamp(0.0, 1.0);
217 let curve = CubicBezier::from_endpoints(start_x, start_y, end_x, end_y, zoom, min_offset);
218
219 if t >= 1.0 {
220 return curve.commands_from((0.0, 0.0));
221 }
222
223 if t <= 0.0 || curve.is_straight() {
224 let x = start_x + (end_x - start_x) * t;
228 let y = start_y + (end_y - start_y) * t;
229 return format!("M {} {} L {} {}", start_x, start_y, x, y);
230 }
231
232 curve.split_at(t).commands_from((0.0, 0.0))
233}
234
235fn lerp_point(a: (f32, f32), b: (f32, f32), t: f32) -> (f32, f32) {
237 (a.0 + (b.0 - a.0) * t, a.1 + (b.1 - a.1) * t)
238}
239
240fn distance_to_line_segment_sq(point: (f32, f32), a: (f32, f32), b: (f32, f32)) -> f32 {
242 let ab = (b.0 - a.0, b.1 - a.1);
243 let ap = (point.0 - a.0, point.1 - a.1);
244
245 let ab_len_sq = ab.0 * ab.0 + ab.1 * ab.1;
246
247 if ab_len_sq < f32::EPSILON {
248 return ap.0 * ap.0 + ap.1 * ap.1;
250 }
251
252 let t = ((ap.0 * ab.0 + ap.1 * ab.1) / ab_len_sq).clamp(0.0, 1.0);
254
255 let closest = (a.0 + t * ab.0, a.1 + t * ab.1);
257
258 let dx = point.0 - closest.0;
260 let dy = point.1 - closest.1;
261 dx * dx + dy * dy
262}
263
264pub fn distance_to_bezier(point: (f32, f32), bezier: &CubicBezier, num_samples: usize) -> f32 {
273 let num_samples = if num_samples == 0 { 20 } else { num_samples };
274
275 let mut min_dist_sq = f32::MAX;
276 let mut prev_point = bezier.eval(0.0);
277
278 for i in 1..=num_samples {
279 let t = i as f32 / num_samples as f32;
280 let curr_point = bezier.eval(t);
281
282 let dist_sq = distance_to_line_segment_sq(point, prev_point, curr_point);
283 if dist_sq < min_dist_sq {
284 min_dist_sq = dist_sq;
285 }
286
287 prev_point = curr_point;
288 }
289
290 min_dist_sq.sqrt()
291}
292
293#[cfg(test)]
294mod tests {
295 use super::*;
296
297 #[test]
302 fn test_bezier_path() {
303 let path = generate_bezier_path(0.0, 50.0, 100.0, 50.0, 1.0, 50.0);
304 assert!(path.starts_with("M 0 50 C"));
305 assert!(path.ends_with("100 50"));
306 }
307
308 #[test]
309 fn test_bezier_path_format() {
310 let path = generate_bezier_path(10.0, 20.0, 100.0, 80.0, 1.0, 50.0);
311 assert!(path.starts_with("M 10 20 C"));
313 assert!(path.ends_with("100 80"));
314 }
315
316 #[test]
317 fn test_bezier_path_small_distance() {
318 let path = generate_bezier_path(0.0, 0.0, 5.0, 0.0, 1.0, 50.0);
320 assert!(path.contains(" L "));
321 assert!(!path.contains(" C "));
322
323 let path2 = generate_bezier_path(0.0, 0.0, 25.0, 0.0, 1.0, 50.0);
325 assert!(path2.contains(" C "));
326 assert!(!path2.contains(" L "));
327 }
328
329 #[test]
330 fn test_bezier_path_zero_distance() {
331 let path = generate_bezier_path(50.0, 50.0, 50.0, 50.0, 1.0, 50.0);
333 assert!(path.starts_with("M "));
334 assert!(path.contains(" L "));
335 assert!(!path.contains(" C "));
336 }
337
338 #[test]
339 fn test_bezier_path_negative_coords() {
340 let path = generate_bezier_path(-100.0, -50.0, 100.0, 50.0, 1.0, 50.0);
341 assert!(path.starts_with("M -100 -50 C"));
342 assert!(path.ends_with("100 50"));
343 }
344
345 #[test]
346 fn test_bezier_path_zoom_affects_offset() {
347 let path1 = generate_bezier_path(0.0, 0.0, 50.0, 0.0, 1.0, 50.0);
348 let path2 = generate_bezier_path(0.0, 0.0, 50.0, 0.0, 2.0, 50.0);
349 assert_ne!(path1, path2);
351 }
352
353 #[test]
358 fn test_bezier_from_endpoints_creates_correct_points() {
359 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 100.0, 1.0, 50.0);
360
361 assert_eq!(bezier.p0, (0.0, 0.0));
362 assert_eq!(bezier.p3, (100.0, 100.0));
363 assert_eq!(bezier.p1.1, 0.0); assert_eq!(bezier.p2.1, 100.0); }
367
368 #[test]
369 fn test_bezier_from_endpoints_horizontal_control_points() {
370 let bezier = CubicBezier::from_endpoints(0.0, 50.0, 100.0, 50.0, 1.0, 50.0);
371
372 assert!(bezier.p1.0 > bezier.p0.0);
374 assert!(bezier.p2.0 < bezier.p3.0);
376 }
377
378 #[test]
383 fn test_bezier_eval_at_t0_returns_start() {
384 let bezier = CubicBezier::from_endpoints(10.0, 20.0, 100.0, 80.0, 1.0, 50.0);
385 let point = bezier.eval(0.0);
386
387 assert!((point.0 - 10.0).abs() < 0.001);
388 assert!((point.1 - 20.0).abs() < 0.001);
389 }
390
391 #[test]
392 fn test_bezier_eval_at_t1_returns_end() {
393 let bezier = CubicBezier::from_endpoints(10.0, 20.0, 100.0, 80.0, 1.0, 50.0);
394 let point = bezier.eval(1.0);
395
396 assert!((point.0 - 100.0).abs() < 0.001);
397 assert!((point.1 - 80.0).abs() < 0.001);
398 }
399
400 #[test]
401 fn test_bezier_eval_at_midpoint() {
402 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
403 let point = bezier.eval(0.5);
404
405 assert!(point.0 > 40.0 && point.0 < 60.0);
407 assert!((point.1 - 0.0).abs() < 0.001);
409 }
410
411 #[test]
412 fn test_bezier_eval_with_explicit_control_points() {
413 let bezier = CubicBezier {
415 p0: (0.0, 0.0),
416 p1: (33.33, 33.33),
417 p2: (66.66, 66.66),
418 p3: (100.0, 100.0),
419 };
420
421 let mid = bezier.eval(0.5);
423 assert!((mid.0 - 50.0).abs() < 1.0);
424 assert!((mid.1 - 50.0).abs() < 1.0);
425 }
426
427 #[test]
428 fn test_bezier_eval_degenerate_point() {
429 let bezier = CubicBezier {
431 p0: (50.0, 50.0),
432 p1: (50.0, 50.0),
433 p2: (50.0, 50.0),
434 p3: (50.0, 50.0),
435 };
436
437 assert_eq!(bezier.eval(0.0), (50.0, 50.0));
439 assert_eq!(bezier.eval(0.5), (50.0, 50.0));
440 assert_eq!(bezier.eval(1.0), (50.0, 50.0));
441 }
442
443 #[test]
448 fn test_distance_to_bezier_point_on_start() {
449 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
450 let dist = distance_to_bezier((0.0, 0.0), &bezier, 20);
451
452 assert!(dist < 1.0);
454 }
455
456 #[test]
457 fn test_distance_to_bezier_point_on_end() {
458 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
459 let dist = distance_to_bezier((100.0, 0.0), &bezier, 20);
460
461 assert!(dist < 1.0);
463 }
464
465 #[test]
466 fn test_distance_to_bezier_point_near_curve() {
467 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
468 let dist = distance_to_bezier((50.0, 5.0), &bezier, 20);
470
471 assert!(dist < 10.0);
473 assert!(dist > 2.0);
474 }
475
476 #[test]
477 fn test_distance_to_bezier_point_far_away() {
478 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
479 let dist = distance_to_bezier((50.0, 100.0), &bezier, 20);
480
481 assert!(dist > 90.0);
483 }
484
485 #[test]
486 fn test_distance_to_bezier_zero_samples_uses_default() {
487 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
488 let dist = distance_to_bezier((50.0, 10.0), &bezier, 0);
490
491 assert!(dist.is_finite());
492 assert!(dist >= 0.0);
493 }
494
495 #[test]
496 fn test_distance_to_bezier_one_sample() {
497 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
498 let dist = distance_to_bezier((50.0, 10.0), &bezier, 1);
500
501 assert!(dist.is_finite());
502 assert!(dist >= 0.0);
503 }
504
505 #[test]
506 fn test_distance_to_bezier_more_samples_more_accurate() {
507 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
508 let point = (50.0, 1.0); let dist_low = distance_to_bezier(point, &bezier, 5);
511 let dist_high = distance_to_bezier(point, &bezier, 100);
512
513 assert!(dist_high <= dist_low + 0.5); }
516
517 #[test]
518 fn test_distance_to_bezier_always_non_negative() {
519 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 100.0, 1.0, 50.0);
520
521 let points = [
523 (50.0, 50.0),
524 (-100.0, -100.0),
525 (200.0, 200.0),
526 (0.0, 100.0),
527 (100.0, 0.0),
528 ];
529
530 for point in points {
531 let dist = distance_to_bezier(point, &bezier, 20);
532 assert!(
533 dist >= 0.0,
534 "Distance should be non-negative for {:?}",
535 point
536 );
537 }
538 }
539
540 #[test]
541 fn test_distance_to_bezier_negative_coords() {
542 let bezier = CubicBezier::from_endpoints(-100.0, -50.0, 100.0, 50.0, 1.0, 50.0);
543 let dist = distance_to_bezier((-100.0, -50.0), &bezier, 20);
544
545 assert!(dist < 1.0);
547 }
548
549 #[test]
554 fn test_from_endpoints_matches_generated_path() {
555 for (sx, sy, ex, ey) in [
559 (0.0, 0.0, 15.0, 0.0),
560 (0.0, 0.0, 25.0, 0.0),
561 (10.0, 20.0, 100.0, 80.0),
562 (100.0, 0.0, 0.0, 50.0),
563 ] {
564 let curve = CubicBezier::from_endpoints(sx, sy, ex, ey, 1.0, 50.0);
565 assert_eq!(
566 curve.commands_from((0.0, 0.0)),
567 generate_bezier_path(sx, sy, ex, ey, 1.0, 50.0),
568 "curve and drawn path disagree for ({sx},{sy})->({ex},{ey})"
569 );
570 }
571 }
572
573 #[test]
574 fn test_short_link_is_straight() {
575 let curve = CubicBezier::from_endpoints(0.0, 0.0, 5.0, 0.0, 1.0, 50.0);
576 assert!(curve.is_straight());
577 assert!(!CubicBezier::from_endpoints(0.0, 0.0, 25.0, 0.0, 1.0, 50.0).is_straight());
578 }
579
580 #[test]
585 fn test_bounds_contains_the_curve() {
586 let curve = CubicBezier::from_endpoints(0.0, 0.0, 200.0, 120.0, 1.0, 50.0);
587 let (x, y, w, h) = curve.bounds();
588
589 for i in 0..=50 {
590 let (px, py) = curve.eval(i as f32 / 50.0);
591 assert!(
592 px >= x - 0.001 && px <= x + w + 0.001,
593 "x {px} outside {x}..{}",
594 x + w
595 );
596 assert!(
597 py >= y - 0.001 && py <= y + h + 0.001,
598 "y {py} outside {y}..{}",
599 y + h
600 );
601 }
602 }
603
604 #[test]
605 fn test_bounds_of_horizontal_link_has_zero_height() {
606 let curve = CubicBezier::from_endpoints(0.0, 50.0, 300.0, 50.0, 1.0, 50.0);
609 let (_, y, _, h) = curve.bounds();
610 assert_eq!(y, 50.0);
611 assert_eq!(h, 0.0);
612 }
613
614 #[test]
615 fn test_bounds_spans_the_control_points_not_just_the_endpoints() {
616 let curve = CubicBezier::from_endpoints(100.0, 0.0, 110.0, 300.0, 1.0, 50.0);
619 let (x, _, w, _) = curve.bounds();
620 assert!(
621 x < 100.0,
622 "box should start left of the start point, got {x}"
623 );
624 assert!(
625 x + w > 110.0,
626 "box should end right of the end point, got {}",
627 x + w
628 );
629 assert!(w > 50.0, "box should be at least the offset wide, got {w}");
630 }
631
632 #[test]
633 fn test_bounds_of_straight_link_is_the_segment() {
634 let curve = CubicBezier::from_endpoints(10.0, 20.0, 15.0, 24.0, 1.0, 50.0);
635 assert_eq!(curve.bounds(), (10.0, 20.0, 5.0, 4.0));
636 }
637
638 #[test]
643 fn test_commands_from_bounds_origin_are_box_relative() {
644 let curve = CubicBezier::from_endpoints(100.0, 40.0, 300.0, 160.0, 1.0, 50.0);
645 let (x, y, w, h) = curve.bounds();
646 let commands = curve.commands_from((x, y));
647
648 let coords: Vec<f32> = commands
649 .split_whitespace()
650 .filter_map(|t| t.parse::<f32>().ok())
651 .collect();
652 assert_eq!(coords.len(), 8);
653 for pair in coords.chunks(2) {
654 assert!(
655 pair[0] >= -0.001 && pair[0] <= w + 0.001,
656 "x {} outside 0..{w}",
657 pair[0]
658 );
659 assert!(
660 pair[1] >= -0.001 && pair[1] <= h + 0.001,
661 "y {} outside 0..{h}",
662 pair[1]
663 );
664 }
665 }
666
667 #[test]
668 fn test_to_link_path_hands_over_relative_commands_and_the_box() {
669 let curve = CubicBezier::from_endpoints(100.0, 40.0, 300.0, 160.0, 1.0, 50.0);
670 let (bx, by, bw, bh) = curve.bounds();
671
672 let (commands, x, y, width, height) = curve.to_link_path(|c, x, y, w, h| (c, x, y, w, h));
673
674 assert_eq!((x, y, width, height), (bx, by, bw, bh));
675 assert_eq!(commands, curve.commands_from((bx, by)));
676 }
677
678 #[test]
683 fn test_split_at_traces_the_same_curve() {
684 let curve = CubicBezier::from_endpoints(0.0, 0.0, 200.0, 100.0, 1.0, 50.0);
685 let half = curve.split_at(0.5);
686
687 assert_eq!(half.p0, curve.p0);
688 let end = half.eval(1.0);
691 let mid = curve.eval(0.5);
692 assert!((end.0 - mid.0).abs() < 0.01 && (end.1 - mid.1).abs() < 0.01);
693
694 let quarter = curve.eval(0.25);
695 let half_mid = half.eval(0.5);
696 assert!((half_mid.0 - quarter.0).abs() < 0.01 && (half_mid.1 - quarter.1).abs() < 0.01);
697 }
698
699 #[test]
700 fn test_partial_path_grows_from_the_start() {
701 let full = generate_partial_bezier_path(0.0, 0.0, 200.0, 100.0, 1.0, 50.0, 1.0);
702 assert_eq!(
703 full,
704 generate_bezier_path(0.0, 0.0, 200.0, 100.0, 1.0, 50.0)
705 );
706
707 let none = generate_partial_bezier_path(0.0, 0.0, 200.0, 100.0, 1.0, 50.0, 0.0);
708 assert_eq!(none, "M 0 0 L 0 0");
709
710 let part = generate_partial_bezier_path(0.0, 0.0, 200.0, 100.0, 1.0, 50.0, 0.5);
711 assert!(part.starts_with("M 0 0 C"));
712 assert_ne!(part, full);
713 }
714
715 #[test]
716 fn test_partial_path_of_short_link_stays_straight() {
717 let part = generate_partial_bezier_path(0.0, 0.0, 10.0, 0.0, 1.0, 50.0, 0.5);
718 assert_eq!(part, "M 0 0 L 5 0");
719 }
720
721 #[test]
726 fn test_bezier_symmetry() {
727 let bezier = CubicBezier::from_endpoints(0.0, 0.0, 100.0, 0.0, 1.0, 50.0);
729
730 let left = bezier.eval(0.25);
731 let right = bezier.eval(0.75);
732
733 assert!((left.1 - right.1).abs() < 0.001);
735 assert!((left.0 + right.0 - 100.0).abs() < 0.1);
737 }
738
739 #[test]
740 fn test_bezier_monotonic_x_for_horizontal() {
741 let bezier = CubicBezier::from_endpoints(0.0, 50.0, 100.0, 50.0, 1.0, 50.0);
742
743 let mut prev_x = bezier.eval(0.0).0;
745 for i in 1..=20 {
746 let t = i as f32 / 20.0;
747 let curr_x = bezier.eval(t).0;
748 assert!(
749 curr_x >= prev_x - 0.001,
750 "X should be monotonic at t={}: {} < {}",
751 t,
752 curr_x,
753 prev_x
754 );
755 prev_x = curr_x;
756 }
757 }
758}