use super::expansion::{expansion_sign, expansion_sum, merge_all, product_expansion};
use super::sign::Orientation;
use crate::primitives::Point2;
pub(crate) fn polygon_orientation(vertices: &[Point2]) -> Orientation {
let n = vertices.len();
if n < 3 {
return Orientation::Collinear;
}
let terms: Vec<Vec<f64>> = (0..n)
.map(|i| {
let j = (i + 1) % n;
let (xi, yi) = (vertices[i].x(), vertices[i].y());
let (xj, yj) = (vertices[j].x(), vertices[j].y());
let pos = product_expansion(xi, yj);
let neg = product_expansion(xj, yi);
expansion_sum(&pos, &[-neg[0], -neg[1]])
})
.collect();
let total = merge_all(terms);
Orientation::from(expansion_sign(&total))
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[test]
fn ccw_square() {
let v = [p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)];
assert_eq!(polygon_orientation(&v), Orientation::CounterClockwise);
}
#[test]
fn cw_square() {
let v = [p(0.0, 0.0), p(0.0, 4.0), p(4.0, 4.0), p(4.0, 0.0)];
assert_eq!(polygon_orientation(&v), Orientation::Clockwise);
}
#[test]
fn too_few_vertices_is_collinear() {
assert_eq!(polygon_orientation(&[]), Orientation::Collinear);
assert_eq!(polygon_orientation(&[p(0.0, 0.0)]), Orientation::Collinear);
assert_eq!(
polygon_orientation(&[p(0.0, 0.0), p(1.0, 1.0)]),
Orientation::Collinear
);
}
#[test]
fn all_collinear_vertices_is_collinear() {
let v = [p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)];
assert_eq!(polygon_orientation(&v), Orientation::Collinear);
}
}