use super::super::expansion::{expansion_sum, negate, product_of_expansions, scale_expansion};
use super::rounding::correctly_rounded_divide;
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))
}
#[cfg(test)]
mod tests {
use super::super::super::expansion::expansion_sign;
use super::super::super::sign::Sign;
use super::super::rounding::MAX_DIVIDE_ITERS;
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[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"
);
}
}