use super::expansion::{diff_expansion, expansion_sign, expansion_sum, product_of_expansions};
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 bdy_cdz = bdy * cdz;
let bdz_cdy = bdz * cdy;
let bdx_cdz = bdx * cdz;
let bdz_cdx = bdz * cdx;
let bdx_cdy = bdx * cdy;
let bdy_cdx = bdy * cdx;
let term_a = adx * (bdy_cdz - bdz_cdy);
let term_b = ady * (bdx_cdz - bdz_cdx);
let term_c = adz * (bdx_cdy - bdy_cdx);
let det = term_a - term_b + term_c;
let bound = INCIRCLE_ERR_BOUND_FACTOR
* (adx.abs() * (bdy_cdz.abs() + bdz_cdy.abs())
+ ady.abs() * (bdx_cdz.abs() + bdz_cdx.abs())
+ adz.abs() * (bdx_cdy.abs() + bdy_cdx.abs()));
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 adx = diff_expansion(a.x(), d.x());
let ady = diff_expansion(a.y(), d.y());
let bdx = diff_expansion(b.x(), d.x());
let bdy = diff_expansion(b.y(), d.y());
let cdx = diff_expansion(c.x(), d.x());
let cdy = diff_expansion(c.y(), d.y());
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 bc_yz = expansion_sum(
&product_of_expansions(&bdy, &cdz),
&negate(&product_of_expansions(&bdz, &cdy)),
);
let bc_xz = expansion_sum(
&product_of_expansions(&bdx, &cdz),
&negate(&product_of_expansions(&bdz, &cdx)),
);
let bc_xy = expansion_sum(
&product_of_expansions(&bdx, &cdy),
&negate(&product_of_expansions(&bdy, &cdx)),
);
let term_a = product_of_expansions(&adx, &bc_yz);
let term_b = product_of_expansions(&ady, &bc_xz);
let term_c = product_of_expansions(&adz, &bc_xy);
let det = expansion_sum(&expansion_sum(&term_a, &negate(&term_b)), &term_c);
expansion_sign(&det)
}
fn negate(e: &[f64]) -> Vec<f64> {
e.iter().map(|v| -v).collect()
}
#[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);
}
}