use super::super::expansion::{
diff_expansion, expansion_sign, expansion_sum, negate, product_of_expansions, scale_expansion,
};
use super::super::sign::Sign;
use super::rounding::correctly_rounded_divide;
use crate::primitives::Point2;
pub(crate) fn circumcenter(a: Point2, b: Point2, c: Point2) -> Option<Point2> {
let max_coord = [a.x(), a.y(), b.x(), b.y(), c.x(), c.y()]
.into_iter()
.fold(0.0_f64, |acc, v| acc.max(v.abs()));
if max_coord <= RESCALE_THRESHOLD {
return circumcenter_raw(a, b, c);
}
let k = max_coord.log2().ceil() as i32;
let s = 2f64.powi(-k);
let scale = |p: Point2| Point2::new_unchecked(p.x() * s, p.y() * s);
let scaled = circumcenter_raw(scale(a), scale(b), scale(c))?;
let inv_s = 2f64.powi(k);
let x = scaled.x() * inv_s;
let y = scaled.y() * inv_s;
if x.is_finite() && y.is_finite() {
Some(Point2::new_unchecked(x, y))
} else {
None
}
}
const RESCALE_THRESHOLD: f64 = 1e90;
fn circumcenter_raw(a: Point2, b: Point2, c: Point2) -> Option<Point2> {
let dx1 = diff_expansion(b.x(), a.x());
let dy1 = diff_expansion(b.y(), a.y());
let dx2 = diff_expansion(c.x(), a.x());
let dy2 = diff_expansion(c.y(), a.y());
let dx1_dy2 = product_of_expansions(&dx1, &dy2);
let dy1_dx2 = product_of_expansions(&dy1, &dx2);
let half_d = expansion_sum(&dx1_dy2, &negate(&dy1_dx2));
let d = scale_expansion(&half_d, 2.0);
if expansion_sign(&d) == Sign::Zero {
return None;
}
let sq1 = expansion_sum(
&product_of_expansions(&dx1, &dx1),
&product_of_expansions(&dy1, &dy1),
);
let sq2 = expansion_sum(
&product_of_expansions(&dx2, &dx2),
&product_of_expansions(&dy2, &dy2),
);
let num_x = expansion_sum(
&expansion_sum(
&scale_expansion(&d, a.x()),
&product_of_expansions(&dy2, &sq1),
),
&negate(&product_of_expansions(&dy1, &sq2)),
);
let num_y = expansion_sum(
&expansion_sum(
&scale_expansion(&d, a.y()),
&product_of_expansions(&dx1, &sq2),
),
&negate(&product_of_expansions(&dx2, &sq1)),
);
let x = correctly_rounded_divide(&num_x, &d);
let y = correctly_rounded_divide(&num_y, &d);
if x.is_finite() && y.is_finite() {
Some(Point2::new_unchecked(x, y))
} else {
None
}
}
#[cfg(test)]
mod tests {
use super::super::rounding::MAX_DIVIDE_ITERS;
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[test]
fn right_triangle_circumcenter_is_hypotenuse_midpoint() {
assert_eq!(
circumcenter(p(0.0, 0.0), p(2.0, 0.0), p(0.0, 2.0)),
Some(p(1.0, 1.0))
);
assert_eq!(
circumcenter(p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)),
Some(p(2.0, 2.0))
);
}
#[test]
fn equilateral_triangle_circumcenter_matches_hand_computation() {
let sqrt3 = 3.0_f64.sqrt();
let got = circumcenter(p(0.0, 0.0), p(2.0, 0.0), p(1.0, sqrt3)).unwrap();
assert!((got.x() - 1.0).abs() < 1e-12);
assert!((got.y() - 1.0 / sqrt3).abs() < 1e-12);
}
#[test]
fn order_independent_up_to_which_vertex_is_a() {
let (a, b, c) = (p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0));
let v1 = circumcenter(a, b, c);
let v2 = circumcenter(b, c, a);
let v3 = circumcenter(c, a, b);
assert_eq!(v1, v2);
assert_eq!(v2, v3);
}
#[test]
fn exactly_collinear_points_return_none() {
assert_eq!(circumcenter(p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)), None);
assert_eq!(circumcenter(p(1.0, 1.0), p(2.0, 2.0), p(5.0, 5.0)), None);
assert_eq!(circumcenter(p(1.0, 1.0), p(1.0, 1.0), p(2.0, 3.0)), None);
}
#[test]
fn thin_triangle_overflow_returns_none_not_a_panic() {
let l = 1e75;
let h = 1e-170;
let a = p(0.0, 0.0);
let b = p(l, 0.0);
let c = p(l / 2.0, h);
assert_eq!(
crate::predicates::orient2d(a, b, c),
crate::predicates::Orientation::CounterClockwise,
"fixture must be a genuine, non-degenerate triangle, not an accidentally-collinear one"
);
assert_eq!(circumcenter(a, b, c), None);
}
#[test]
fn thin_but_representable_triangle_is_some_and_finite() {
for exp in [1, 10, 50, 100, 200, 250] {
let eps = 2f64.powi(-exp);
let got = circumcenter(p(0.0, 0.0), p(1.0, 0.0), p(0.5, eps));
assert!(
got.is_some(),
"expected Some at eps=2^-{exp}, got None (overflowed sooner than expected)"
);
let got = got.unwrap();
assert!(got.x().is_finite() && got.y().is_finite());
}
}
#[test]
fn extreme_uniform_magnitude_is_finite_or_none_not_a_panic() {
for exp in [90, 100, 120, 150, 200, 250, 300] {
let scale = 10f64.powi(exp);
let got = circumcenter(p(0.0, 0.0), p(scale, 0.0), p(0.0, scale));
if let Some(pt) = got {
assert!(
pt.x().is_finite() && pt.y().is_finite(),
"circumcenter produced a non-finite Point2 at scale 1e{exp} -- should be None instead"
);
}
}
}
#[test]
fn divide_loop_iteration_bound_is_generous() {
MAX_DIVIDE_ITERS.with(|c| c.set(0));
let mut rng = Xorshift64(0x1EE7_C1CC_1E77_5EED_u64);
for &scale in &[1.0_f64, 1e-6, 1e6, 1e30, 1e-30, 1e60, 1e-60] {
for _ in 0..300 {
let cx = rng.next_f64_in(scale);
let cy = rng.next_f64_in(scale);
let r = scale.max(f64::MIN_POSITIVE) * (0.1 + rng.next_f64_in(1.0).abs());
let a = p(cx - r, cy - r * (0.3 + rng.next_f64_in(1.0).abs()));
let b = p(cx + r, cy + r * (0.3 + rng.next_f64_in(1.0).abs()));
let c = p(cx + r * rng.next_f64_in(1.0), cy + r);
if is_nondegenerate(a, b, c) {
circumcenter(a, b, c);
}
}
}
for &radius in &[1e3, 1e6, 1e10, 1e20, 1e40, 1e60, 1e80] {
for i in 0..300u32 {
let theta_a = (i as f64) * 0.618_033_988_75 * std::f64::consts::TAU;
let theta_b = theta_a + 1.9 + rng.next_f64_in(0.3);
let theta_c = theta_a + 4.0 + rng.next_f64_in(0.3);
let a = p(radius * theta_a.cos(), radius * theta_a.sin());
let b = p(radius * theta_b.cos(), radius * theta_b.sin());
let c = p(radius * theta_c.cos(), radius * theta_c.sin());
if is_nondegenerate(a, b, c) {
circumcenter(a, b, c);
}
}
}
let max_iters = MAX_DIVIDE_ITERS.with(|c| c.get());
eprintln!("circumcenter: measured max correctly_rounded_divide iterations = {max_iters}");
assert!(
max_iters <= 3,
"correctly_rounded_divide used {max_iters} iterations on some circumcenter input \
-- re-examine before trusting the 0..8 bound for this construction"
);
}
fn is_nondegenerate(a: Point2, b: Point2, c: Point2) -> bool {
let dx1 = b.x() - a.x();
let dy1 = b.y() - a.y();
let dx2 = c.x() - a.x();
let dy2 = c.y() - a.y();
let d = dx1 * dy2 - dy1 * dx2;
d.is_finite() && d != 0.0
}
struct Xorshift64(u64);
impl Xorshift64 {
fn next_u64(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn next_f64_in(&mut self, scale: f64) -> f64 {
let bits = self.next_u64();
let unit = (bits >> 11) as f64 * (1.0 / (1u64 << 53) as f64);
(unit * 2.0 - 1.0) * scale
}
}
}