use crate::math::Vec2;
pub(super) fn orient(a: Vec2, b: Vec2, c: Vec2) -> f64 {
let l = (a.x - c.x) * (b.y - c.y);
let r = (a.y - c.y) * (b.x - c.x);
let det = l - r;
let bound = 3.4e-16 * (l.abs() + r.abs());
if det.abs() > bound {
return det;
}
exact_orient(a, b, c)
}
fn exact_orient(a: Vec2, b: Vec2, c: Vec2) -> f64 {
let terms = [
(a.x, b.y),
(-a.x, c.y),
(-c.x, b.y),
(-a.y, b.x),
(a.y, c.x),
(c.y, b.x),
];
let mut e: Vec<f64> = Vec::with_capacity(12);
for (p, q) in terms {
let hi = p * q;
let lo = p.mul_add(q, -hi);
grow(&mut e, lo);
grow(&mut e, hi);
}
e.last().copied().unwrap_or(0.0)
}
fn grow(e: &mut Vec<f64>, b: f64) {
let mut q = b;
let mut out = Vec::with_capacity(e.len() + 1);
for &x in e.iter() {
let s = q + x;
let bv = s - q;
let err = (q - (s - bv)) + (x - bv);
if err != 0.0 {
out.push(err);
}
q = s;
}
if q != 0.0 {
out.push(q);
}
*e = out;
}
pub(super) fn in_circle(a: Vec2, b: Vec2, c: Vec2, d: Vec2) -> bool {
let (ax, ay) = (a.x - d.x, a.y - d.y);
let (bx, by) = (b.x - d.x, b.y - d.y);
let (cx, cy) = (c.x - d.x, c.y - d.y);
let (a2, b2, c2) = (ax * ax + ay * ay, bx * bx + by * by, cx * cx + cy * cy);
let det = a2 * (bx * cy - cx * by) - b2 * (ax * cy - cx * ay) + c2 * (ax * by - bx * ay);
let scale = a2 * (bx * cy).abs().max((cx * by).abs())
+ b2 * (ax * cy).abs().max((cx * ay).abs())
+ c2 * (ax * by).abs().max((bx * ay).abs());
det > 1e-12 * scale
}
pub(super) fn circumcenter(a: Vec2, b: Vec2, c: Vec2) -> Option<Vec2> {
let (b, c) = (b - a, c - a);
let d = 2.0 * b.cross(c);
if d == 0.0 {
return None;
}
let (b2, c2) = (b.dot(b), c.dot(c));
let center = Vec2::new(c.y * b2 - b.y * c2, b.x * c2 - c.x * b2) / d;
let out = a + center;
(out.x.is_finite() && out.y.is_finite()).then_some(out)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn orientation_is_exact_on_nearly_collinear_points() {
let a = Vec2::new(0.5, 0.5);
let b = Vec2::new(12.0, 12.0);
let c = Vec2::new(24.0, 24.0);
assert_eq!(orient(a, b, c), 0.0);
let tiny = Vec2::new(0.5 + f64::EPSILON, 0.5);
assert!(orient(tiny, b, c) < 0.0);
let up = Vec2::new(0.5, 0.5 + f64::EPSILON);
assert!(orient(up, b, c) > 0.0);
assert!(
orient(
Vec2::new(0.0, 0.0),
Vec2::new(1.0, 0.0),
Vec2::new(0.0, 1.0)
) > 0.0
);
}
#[test]
fn circumcenter_of_a_right_triangle_is_its_hypotenuse_midpoint() {
let c = circumcenter(
Vec2::new(0.0, 0.0),
Vec2::new(2.0, 0.0),
Vec2::new(0.0, 2.0),
);
assert_eq!(c, Some(Vec2::new(1.0, 1.0)));
assert!(in_circle(
Vec2::new(0.0, 0.0),
Vec2::new(2.0, 0.0),
Vec2::new(0.0, 2.0),
Vec2::new(1.0, 1.0)
));
}
}