use super::super::expansion::{
expansion_sign, expansion_sum, negate, 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 max_coord = [a.x(), a.y(), b.x(), b.y(), c.x(), c.y(), d.x(), d.y()]
.into_iter()
.fold(0.0_f64, |acc, v| acc.max(v.abs()));
if max_coord <= RESCALE_THRESHOLD {
return line_intersection_raw(a, b, c, d);
}
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 = line_intersection_raw(scale(a), scale(b), scale(c), scale(d));
let inv_s = 2f64.powi(k);
Point2::new_unchecked(scaled.x() * inv_s, scaled.y() * inv_s)
}
const RESCALE_THRESHOLD: f64 = 1e90;
fn line_intersection_raw(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 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
}
}
fn is_proper_shape(a: Point2, b: Point2, c: Point2, d: Point2) -> bool {
let d1 = expansion_sign(&orient2d_expansion(c, d, a));
let d2 = expansion_sign(&orient2d_expansion(c, d, b));
let d3 = expansion_sign(&orient2d_expansion(a, b, c));
let d4 = expansion_sign(&orient2d_expansion(a, b, d));
d1 != Sign::Zero
&& d2 != Sign::Zero
&& d3 != Sign::Zero
&& d4 != Sign::Zero
&& d1 != d2
&& d3 != d4
}
fn deterministic_crossing(m: f64, k: f64) -> (Point2, Point2, Point2, Point2) {
(p(-m, 0.0), p(m, 0.0), p(-k, -k), p(k, k))
}
#[test]
fn extreme_uniform_magnitude_is_finite() {
let mut checked = 0u32;
for exp in [
90, 95, 100, 102, 103, 105, 110, 120, 130, 140, 150, 153, 155, 160,
] {
let scale = 10f64.powi(exp);
let (a, b, c, d) = deterministic_crossing(scale, scale);
if !is_proper_shape(a, b, c, d) {
continue;
}
checked += 1;
let q = line_intersection(a, b, c, d);
assert!(
q.x().is_finite() && q.y().is_finite(),
"line_intersection produced a non-finite coordinate at uniform magnitude 1e{exp}: {q:?}"
);
}
assert!(
checked > 0,
"no case in the sweep was even Proper-shaped -- test is vacuous"
);
eprintln!(
"line_intersection: uniform-magnitude ceiling sweep checked {checked} cases, all finite"
);
}
#[test]
fn extreme_mixed_magnitude_is_finite() {
let mut checked = 0u32;
for &(k_exp, m_exp) in &[
(120, 70),
(150, 50),
(100, 100),
(130, 100),
(140, 90),
(160, 40),
(154, 60),
(70, 120),
(50, 150),
] {
let k = 10f64.powi(k_exp);
let m = 10f64.powi(m_exp);
let (a, b, c, d) = deterministic_crossing(m, k);
if !is_proper_shape(a, b, c, d) {
continue;
}
checked += 1;
let q = line_intersection(a, b, c, d);
assert!(
q.x().is_finite() && q.y().is_finite(),
"line_intersection produced a non-finite coordinate at mixed magnitude k=1e{k_exp}, m=1e{m_exp}: {q:?}"
);
}
assert!(
checked > 0,
"no case in the sweep was even Proper-shaped -- test is vacuous"
);
eprintln!(
"line_intersection: mixed-magnitude ceiling sweep checked {checked} cases, all finite"
);
}
#[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"
);
}
}