use super::expansion::{
det3_exact, det3_with_precancel_bound, diff_expansion, expansion_sum, product_of_expansions,
rescale_for_sign_only, sign_only_expansion_sign,
};
use super::sign::Sign;
use crate::primitives::Point2;
const INCIRCLE_ERR_BOUND_FACTOR: f64 = 24.0 * f64::EPSILON / 2.0;
pub fn incircle(a: Point2, b: Point2, c: Point2, d: Point2) -> Sign {
let adx = a.x() - d.x();
let ady = a.y() - d.y();
let bdx = b.x() - d.x();
let bdy = b.y() - d.y();
let cdx = c.x() - d.x();
let cdy = c.y() - d.y();
let adz = adx * adx + ady * ady;
let bdz = bdx * bdx + bdy * bdy;
let cdz = cdx * cdx + cdy * cdy;
let (det, precancel_bound) =
det3_with_precancel_bound((adx, ady, adz), (bdx, bdy, bdz), (cdx, cdy, cdz));
let bound = INCIRCLE_ERR_BOUND_FACTOR * precancel_bound;
if bound > 0.0 && det.abs() > bound {
return Sign::of(det);
}
incircle_exact(a, b, c, d)
}
fn incircle_exact(a: Point2, b: Point2, c: Point2, d: Point2) -> Sign {
let [ax, ay, bx, by, cx, cy, dx, dy] =
rescale_for_sign_only([a.x(), a.y(), b.x(), b.y(), c.x(), c.y(), d.x(), d.y()]);
let adx = diff_expansion(ax, dx);
let ady = diff_expansion(ay, dy);
let bdx = diff_expansion(bx, dx);
let bdy = diff_expansion(by, dy);
let cdx = diff_expansion(cx, dx);
let cdy = diff_expansion(cy, dy);
let adz = expansion_sum(
&product_of_expansions(&adx, &adx),
&product_of_expansions(&ady, &ady),
);
let bdz = expansion_sum(
&product_of_expansions(&bdx, &bdx),
&product_of_expansions(&bdy, &bdy),
);
let cdz = expansion_sum(
&product_of_expansions(&cdx, &cdx),
&product_of_expansions(&cdy, &cdy),
);
let det = det3_exact((&adx, &ady, &adz), (&bdx, &bdy, &bdz), (&cdx, &cdy, &cdz));
sign_only_expansion_sign(&det)
}
#[cfg(test)]
mod tests {
use super::*;
fn pt(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[test]
fn center_is_inside() {
assert_eq!(
incircle(pt(1.0, 0.0), pt(0.0, 1.0), pt(-1.0, 0.0), pt(0.0, 0.0)),
Sign::Positive
);
}
#[test]
fn far_point_is_outside() {
assert_eq!(
incircle(pt(1.0, 0.0), pt(0.0, 1.0), pt(-1.0, 0.0), pt(100.0, 100.0)),
Sign::Negative
);
}
#[test]
fn on_circle_is_zero() {
assert_eq!(
incircle(pt(1.0, 0.0), pt(0.0, 1.0), pt(-1.0, 0.0), pt(0.0, -1.0)),
Sign::Zero
);
}
#[test]
fn all_four_points_collinear_is_zero() {
assert_eq!(
incircle(pt(0.0, 0.0), pt(1.0, 0.0), pt(2.0, 0.0), pt(0.5, 0.0)),
Sign::Zero
);
}
#[test]
fn collinear_abc_with_d_off_line_is_not_zero() {
assert_eq!(
incircle(pt(0.0, 0.0), pt(1.0, 0.0), pt(2.0, 0.0), pt(0.5, 1.0)),
Sign::Positive
);
}
#[test]
fn duplicate_point_is_zero() {
let p = pt(1.0, 2.0);
assert_eq!(incircle(p, p, pt(3.0, 4.0), pt(5.0, 6.0)), Sign::Zero);
}
#[test]
fn exact_fallback_does_not_panic_on_near_cocircular() {
let a = pt(1e15, 0.0);
let b = pt(0.0, 1e15);
let c = pt(-1e15, 0.0);
let d = pt(0.0, -1e15 + 1e-3);
let _ = incircle(a, b, c, d);
}
}