use super::super::expansion::{
expansion_sign, expansion_sum, product_of_expansions, scale_expansion,
};
use super::super::sign::Sign;
use crate::primitives::Point2;
pub(crate) fn line_intersection(a: Point2, b: Point2, c: Point2, d: Point2) -> Point2 {
let d1 = orient2d_expansion(c, d, a);
let d2 = orient2d_expansion(c, d, b);
let denom = expansion_sum(&d1, &negate(&d2));
let num_x = expansion_sum(
&scale_expansion(&d1, b.x()),
&negate(&scale_expansion(&d2, a.x())),
);
let num_y = expansion_sum(
&scale_expansion(&d1, b.y()),
&negate(&scale_expansion(&d2, a.y())),
);
let x = correctly_rounded_divide(&num_x, &denom);
let y = correctly_rounded_divide(&num_y, &denom);
Point2::new_unchecked(x, y)
}
fn orient2d_expansion(p: Point2, q: Point2, r: Point2) -> Vec<f64> {
use super::super::expansion::diff_expansion;
let prx = diff_expansion(p.x(), r.x());
let pry = diff_expansion(p.y(), r.y());
let qrx = diff_expansion(q.x(), r.x());
let qry = diff_expansion(q.y(), r.y());
let left = product_of_expansions(&prx, &qry);
let right = product_of_expansions(&pry, &qrx);
expansion_sum(&left, &negate(&right))
}
fn negate(e: &[f64]) -> Vec<f64> {
e.iter().map(|v| -v).collect()
}
fn next_up(x: f64) -> f64 {
if x == 0.0 {
return f64::from_bits(1); }
let bits = x.to_bits();
f64::from_bits(if x > 0.0 { bits + 1 } else { bits - 1 })
}
fn next_down(x: f64) -> f64 {
-next_up(-x)
}
fn correctly_rounded_divide(num: &[f64], denom: &[f64]) -> f64 {
let denom_sign = expansion_sign(denom);
let mut q: f64 = num.iter().sum::<f64>() / denom.iter().sum::<f64>();
for iter in 0..8u32 {
let r = expansion_sum(num, &negate(&scale_expansion(denom, q)));
let r_sign = expansion_sign(&r);
if r_sign == Sign::Zero {
record_iters(iter);
return q;
}
let quotient_positive = r_sign == denom_sign;
let neighbor = if quotient_positive {
next_up(q)
} else {
next_down(q)
};
let half_ulp = 0.5 * (neighbor - q).abs();
let r_abs = if r_sign == Sign::Positive {
r
} else {
negate(&r)
};
let denom_abs = if denom_sign == Sign::Positive {
denom.to_vec()
} else {
negate(denom)
};
let threshold = scale_expansion(&denom_abs, half_ulp);
match expansion_sign(&expansion_sum(&r_abs, &negate(&threshold))) {
Sign::Negative => {
record_iters(iter);
return q;
}
Sign::Positive => q = neighbor,
Sign::Zero => {
record_iters(iter);
let q_is_even = (q.to_bits() & 1) == 0;
return if q_is_even { q } else { neighbor };
}
}
}
record_iters(8);
q
}
#[cfg(test)]
fn record_iters(n: u32) {
MAX_DIVIDE_ITERS.with(|c| c.set(c.get().max(n)));
}
#[cfg(not(test))]
#[inline(always)]
fn record_iters(_n: u32) {}
#[cfg(test)]
thread_local! {
static MAX_DIVIDE_ITERS: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[test]
fn next_up_down_basic() {
assert!(next_up(1.0) > 1.0);
assert_eq!(next_down(next_up(1.0)), 1.0);
assert_eq!(next_up(0.0), f64::from_bits(1));
assert_eq!(next_up(-0.0), f64::from_bits(1));
assert_eq!(next_down(0.0), -f64::from_bits(1));
assert!(next_up(-1.0) > -1.0);
assert_eq!(next_down(next_up(-1.0)), -1.0);
}
fn assert_exact_tie_rounds_to_even(q0: f64) {
use super::super::super::expansion::two_sum;
for neighbor in [next_up(q0), next_down(q0)] {
let (hi, lo) = two_sum(q0, neighbor);
let midpoint = scale_expansion(&[lo, hi], 0.5);
let got = correctly_rounded_divide(&midpoint, &[1.0]);
let expected = if (q0.to_bits() & 1) == 0 {
q0
} else {
neighbor
};
assert_eq!(
got, expected,
"tie between {q0} and {neighbor} should round to the even one"
);
}
}
#[test]
fn exact_tie_rounds_to_even_normal_range() {
assert_exact_tie_rounds_to_even(3.0);
}
#[test]
fn exact_tie_rounds_to_even_at_power_of_two_boundary() {
assert_exact_tie_rounds_to_even(4.0);
}
#[test]
fn simple_crossing_matches_naive_computation() {
let (a, b, c, d) = (p(0.0, 0.0), p(4.0, 4.0), p(0.0, 4.0), p(4.0, 0.0));
assert_eq!(line_intersection(a, b, c, d), p(2.0, 2.0));
}
#[test]
fn exact_half_integer_result() {
let (a, b, c, d) = (p(0.0, 0.0), p(3.0, 3.0), p(0.0, 3.0), p(3.0, 0.0));
assert_eq!(line_intersection(a, b, c, d), p(1.5, 1.5));
}
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
}
}
#[test]
fn divide_loop_iteration_bound_is_generous() {
MAX_DIVIDE_ITERS.with(|c| c.set(0));
let mut rng = Xorshift64(0x51ED_270D_1727_1A9B);
for &scale in &[1.0_f64, 1e-6, 1e6, 1e30, 1e-30, 1e100, 1e-80, 1e-300] {
for _ in 0..200 {
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 * (0.3 + rng.next_f64_in(1.0).abs()), cy + r);
let d = p(cx + r * (0.3 + rng.next_f64_in(1.0).abs()), cy - r);
line_intersection(a, b, c, d);
}
for k in 1..=200i32 {
let tiny = scale.max(1.0) * 2.0_f64.powi(-k.min(60));
let a = p(-scale, 0.0);
let b = p(scale, 0.0);
let c = p(-scale, tiny);
let d = p(
scale,
-tiny + rng.next_f64_in(tiny.abs().max(f64::MIN_POSITIVE) * 1e-3),
);
if a == b || c == d {
continue;
}
line_intersection(a, b, c, d);
}
}
let max_iters = MAX_DIVIDE_ITERS.with(|c| c.get());
eprintln!("correctly_rounded_divide: measured max iterations = {max_iters}");
assert!(
max_iters <= 3,
"correctly_rounded_divide used {max_iters} iterations on some input \
-- the 0..8 bound's assumed headroom is thinner than measured, \
investigate before trusting it"
);
}
}