1use std::f64::consts::TAU;
6
7pub const COLLINEAR_SINE: f64 = 1e-12;
12
13pub const MAX_RADIUS: f64 = 1e7;
19
20#[derive(Debug, Clone, Copy, PartialEq)]
22pub struct ThreePointArc {
23 pub center: [f64; 2],
24 pub radius: f64,
25 pub start_angle: f64,
27 pub sweep: f64,
30}
31
32impl ThreePointArc {
33 pub fn through(start: [f64; 2], mid: [f64; 2], end: [f64; 2]) -> Option<ThreePointArc> {
36 let (center, radius) = circumcircle(start, mid, end)?;
37 let angle = |p: [f64; 2]| (p[1] - center[1]).atan2(p[0] - center[0]);
38 let (a0, am, a1) = (angle(start), angle(mid), angle(end));
39 let ccw = (a1 - a0).rem_euclid(TAU);
40 let sweep = if (am - a0).rem_euclid(TAU) <= ccw {
41 ccw
42 } else {
43 ccw - TAU
44 };
45 Some(ThreePointArc {
46 center,
47 radius,
48 start_angle: a0,
49 sweep,
50 })
51 }
52
53 pub fn at(&self, t: f64) -> [f64; 2] {
55 let angle = self.start_angle + self.sweep * t;
56 [
57 self.center[0] + self.radius * angle.cos(),
58 self.center[1] + self.radius * angle.sin(),
59 ]
60 }
61}
62
63pub fn circumcircle(a: [f64; 2], b: [f64; 2], c: [f64; 2]) -> Option<([f64; 2], f64)> {
67 let len = |p: [f64; 2], q: [f64; 2]| (p[0] - q[0]).hypot(p[1] - q[1]);
68 let d = 2.0 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]));
69 if d.abs() <= 2.0 * COLLINEAR_SINE * len(a, b) * len(a, c) {
70 return None;
71 }
72 let sq = |p: [f64; 2]| p[0] * p[0] + p[1] * p[1];
73 let center = [
74 (sq(a) * (b[1] - c[1]) + sq(b) * (c[1] - a[1]) + sq(c) * (a[1] - b[1])) / d,
75 (sq(a) * (c[0] - b[0]) + sq(b) * (a[0] - c[0]) + sq(c) * (b[0] - a[0])) / d,
76 ];
77 let radius = len(center, a);
78 (radius <= MAX_RADIUS).then_some((center, radius))
79}
80
81#[cfg(test)]
82mod tests {
83 use super::*;
84
85 #[test]
89 fn an_arc_runs_from_its_start_through_its_middle_to_its_end() {
90 let c = [3.0, -2.0];
91 let r = 7.0;
92 let on = |a: f64| [c[0] + r * a.cos(), c[1] + r * a.sin()];
93 let dist = |p: [f64; 2], q: [f64; 2]| (p[0] - q[0]).hypot(p[1] - q[1]);
94 for (a0, sweep) in [(0.3, 0.1), (1.0, 2.5), (-2.0, 3.5), (0.5, 6.2)] {
95 for sweep in [sweep, -sweep] {
96 let (start, mid, end) = (on(a0), on(a0 + sweep / 2.0), on(a0 + sweep));
97 let arc = ThreePointArc::through(start, mid, end).unwrap();
98 assert!((arc.sweep - sweep).abs() < 1e-12, "{sweep}: {}", arc.sweep);
99 for i in 0..=10 {
100 let t = i as f64 / 10.0;
101 assert!(
102 dist(arc.at(t), on(a0 + sweep * t)) < 1e-12,
103 "{sweep} at {t}"
104 );
105 }
106 }
107 }
108 }
109
110 #[test]
113 fn three_points_make_a_circle_by_shape_up_to_a_radius() {
114 for size in [1e-7, 1e-6, 1e-5] {
115 let bulged =
116 |sine: f64| circumcircle([0.0, 0.0], [size / 2.0, sine * size / 2.0], [size, 0.0]);
117 assert!(bulged(2e-12).is_some(), "{size}");
118 assert!(bulged(5e-13).is_none(), "{size}");
119 }
120 let flat = |radius: f64| {
121 let (chord, half) = (10.0, (5.0 / radius).asin());
122 circumcircle(
123 [0.0, 0.0],
124 [chord / 2.0, radius * (1.0 - half.cos())],
125 [chord, 0.0],
126 )
127 };
128 assert!(flat(0.5 * MAX_RADIUS).is_some());
129 assert!(flat(2.0 * MAX_RADIUS).is_none());
130 assert!(circumcircle([1.0, 1.0], [1.0, 1.0], [2.0, 0.0]).is_none());
131 }
132}