use super::expansion::{
diff_expansion, expansion_sum, product_of_expansions, rescale_for_sign_only,
sign_only_expansion_sign,
};
use super::sign::{Orientation, Sign};
use crate::primitives::Point2;
const ORIENT2D_ERR_BOUND_FACTOR: f64 = 7.0 * f64::EPSILON / 2.0;
pub fn orient2d(a: Point2, b: Point2, c: Point2) -> Orientation {
let acx = a.x() - c.x();
let acy = a.y() - c.y();
let bcx = b.x() - c.x();
let bcy = b.y() - c.y();
let left = acx * bcy;
let right = acy * bcx;
let det = left - right;
let bound = ORIENT2D_ERR_BOUND_FACTOR * (left.abs() + right.abs());
if bound > 0.0 && det.abs() > bound {
return Orientation::from(Sign::of(det));
}
Orientation::from(orient2d_exact(a, b, c))
}
fn orient2d_exact(a: Point2, b: Point2, c: Point2) -> Sign {
let [ax, ay, bx, by, cx, cy] =
rescale_for_sign_only([a.x(), a.y(), b.x(), b.y(), c.x(), c.y()]);
let acx = diff_expansion(ax, cx);
let acy = diff_expansion(ay, cy);
let bcx = diff_expansion(bx, cx);
let bcy = diff_expansion(by, cy);
let left = product_of_expansions(&acx, &bcy);
let right = product_of_expansions(&acy, &bcx);
let neg_right: Vec<f64> = right.iter().map(|v| -v).collect();
let det = expansion_sum(&left, &neg_right);
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 counterclockwise_triangle() {
assert_eq!(
orient2d(pt(0.0, 0.0), pt(1.0, 0.0), pt(0.0, 1.0)),
Orientation::CounterClockwise
);
}
#[test]
fn clockwise_triangle() {
assert_eq!(
orient2d(pt(0.0, 0.0), pt(0.0, 1.0), pt(1.0, 0.0)),
Orientation::Clockwise
);
}
#[test]
fn collinear_points() {
assert_eq!(
orient2d(pt(0.0, 0.0), pt(1.0, 1.0), pt(2.0, 2.0)),
Orientation::Collinear
);
}
#[test]
fn duplicate_point_is_collinear() {
let p = pt(3.0, 4.0);
assert_eq!(orient2d(p, p, pt(5.0, 6.0)), Orientation::Collinear);
assert_eq!(orient2d(p, pt(5.0, 6.0), p), Orientation::Collinear);
}
#[test]
fn antisymmetric_under_swap() {
let (a, b, c) = (pt(0.1, 0.2), pt(4.3, -1.5), pt(-2.0, 7.0));
let orig = orient2d(a, b, c);
let swapped = orient2d(b, a, c);
match (orig, swapped) {
(Orientation::CounterClockwise, Orientation::Clockwise) => {}
(Orientation::Clockwise, Orientation::CounterClockwise) => {}
(Orientation::Collinear, Orientation::Collinear) => {}
other => panic!("swap did not flip orientation: {other:?}"),
}
}
#[test]
fn exact_fallback_triggers_on_near_collinear() {
let a = pt(0.0, 0.0);
let b = pt(1e15, 1.0);
let c = pt(2e15, 2.0 + 1e-9);
let _ = orient2d(a, b, c);
}
#[test]
fn signed_zero_matches_positive_zero() {
let a = pt(0.0, 0.0);
let b = pt(1.0, 0.0);
let c_pos = pt(0.0, 0.0);
let c_neg = pt(-0.0, -0.0);
assert_eq!(orient2d(a, b, c_pos), orient2d(a, b, c_neg));
}
}