use crate::polygon::Polygon2;
use crate::predicates::{Orientation, orient2d};
use crate::primitives::Point2;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum HullBoundaryPoints {
#[default]
ExtremesOnly,
KeepAllOnBoundary,
}
pub fn convex_hull2(points: &[Point2], boundary: HullBoundaryPoints) -> Polygon2 {
let pts = dedup_sorted(points);
if pts.len() <= 2 {
return Polygon2::new(pts);
}
if is_collinear(&pts) {
return match boundary {
HullBoundaryPoints::ExtremesOnly => {
let last = pts[pts.len() - 1];
Polygon2::new(vec![pts[0], last])
}
HullBoundaryPoints::KeepAllOnBoundary => Polygon2::new(pts),
};
}
let keep_all = boundary == HullBoundaryPoints::KeepAllOnBoundary;
let mut lower = chain(&pts, keep_all);
let mut reversed = pts;
reversed.reverse();
let mut upper = chain(&reversed, keep_all);
lower.pop();
upper.pop();
lower.extend(upper);
Polygon2::new(lower)
}
fn chain(pts: &[Point2], keep_all: bool) -> Vec<Point2> {
let mut result: Vec<Point2> = Vec::with_capacity(pts.len());
for &p in pts {
while result.len() >= 2 {
let a = result[result.len() - 2];
let b = result[result.len() - 1];
let turn = orient2d(a, b, p);
let should_pop = if keep_all {
turn == Orientation::Clockwise
} else {
turn != Orientation::CounterClockwise
};
if should_pop {
result.pop();
} else {
break;
}
}
result.push(p);
}
result
}
fn is_collinear(pts: &[Point2]) -> bool {
let first = pts[0];
let last = pts[pts.len() - 1];
pts.iter()
.all(|&p| orient2d(first, last, p) == Orientation::Collinear)
}
fn normalize_zero(v: f64) -> f64 {
if v == 0.0 { 0.0 } else { v }
}
pub(crate) fn dedup_sorted(points: &[Point2]) -> Vec<Point2> {
let mut pts: Vec<Point2> = points.to_vec();
pts.sort_by(|a, b| {
normalize_zero(a.x())
.total_cmp(&normalize_zero(b.x()))
.then(normalize_zero(a.y()).total_cmp(&normalize_zero(b.y())))
});
pts.dedup();
pts
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn is_ccw(vertices: &[Point2]) -> bool {
Polygon2::new(vertices.to_vec()).orientation() == Orientation::CounterClockwise
}
#[test]
fn empty_input() {
let hull = convex_hull2(&[], HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices(), &[]);
}
#[test]
fn single_point() {
let hull = convex_hull2(&[p(1.0, 1.0)], HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices(), &[p(1.0, 1.0)]);
}
#[test]
fn two_points() {
let pts = [p(1.0, 1.0), p(2.0, 2.0)];
for mode in [
HullBoundaryPoints::ExtremesOnly,
HullBoundaryPoints::KeepAllOnBoundary,
] {
let hull = convex_hull2(&pts, mode);
assert_eq!(hull.vertices().len(), 2);
}
}
#[test]
fn duplicate_points_collapse() {
let pts = [p(0.0, 0.0), p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices().len(), 3);
}
#[test]
fn signed_zero_duplicate_collapses() {
let pts = [p(-0.0, 5.0), p(0.0, 3.0), p(0.0, 5.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::KeepAllOnBoundary);
assert_eq!(hull.vertices().len(), 2);
}
#[test]
fn square_extremes_only_drops_no_corner() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices().len(), 4);
assert!(is_ccw(hull.vertices()));
}
#[test]
fn square_with_edge_midpoint_extremes_only_drops_it() {
let pts = [
p(0.0, 0.0),
p(2.0, 0.0), p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices().len(), 4);
assert!(!hull.vertices().contains(&p(2.0, 0.0)));
}
#[test]
fn square_with_edge_midpoint_keep_all_keeps_it() {
let pts = [
p(0.0, 0.0),
p(2.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
];
let hull = convex_hull2(&pts, HullBoundaryPoints::KeepAllOnBoundary);
assert_eq!(hull.vertices().len(), 5);
assert!(hull.vertices().contains(&p(2.0, 0.0)));
assert!(is_ccw(hull.vertices()));
}
#[test]
fn interior_point_dropped() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0), ];
for mode in [
HullBoundaryPoints::ExtremesOnly,
HullBoundaryPoints::KeepAllOnBoundary,
] {
let hull = convex_hull2(&pts, mode);
assert_eq!(hull.vertices().len(), 4);
assert!(!hull.vertices().contains(&p(2.0, 2.0)));
}
}
#[test]
fn fully_collinear_extremes_only() {
let pts = [p(0.0, 0.0), p(3.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices(), &[p(0.0, 0.0), p(3.0, 0.0)]);
}
#[test]
fn fully_collinear_keep_all_no_duplication() {
let pts = [p(0.0, 0.0), p(3.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::KeepAllOnBoundary);
assert_eq!(
hull.vertices(),
&[p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)]
);
}
#[test]
fn fully_collinear_vertical_line() {
let pts = [p(5.0, 0.0), p(5.0, 3.0), p(5.0, 1.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices(), &[p(5.0, 0.0), p(5.0, 3.0)]);
}
#[test]
fn output_starts_at_lexicographically_smallest_point() {
let pts = [p(4.0, 4.0), p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert_eq!(hull.vertices()[0], p(0.0, 0.0));
}
#[test]
fn output_is_ccw() {
let pts = [p(0.0, 0.0), p(0.0, 4.0), p(4.0, 4.0), p(4.0, 0.0)];
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
assert!(is_ccw(hull.vertices()));
}
#[test]
fn valley_shape_is_not_treated_as_collinear() {
let pts: Vec<Point2> = (-5..=5).map(|x| p(x as f64, (x * x) as f64)).collect();
let hull = convex_hull2(&pts, HullBoundaryPoints::KeepAllOnBoundary);
assert!(hull.vertices().len() > 2);
assert_ne!(
Polygon2::new(hull.vertices().to_vec()).orientation(),
Orientation::Collinear
);
}
#[test]
fn permutation_invariant() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
p(2.0, 0.0),
];
let mut shuffled = pts;
shuffled.reverse();
for mode in [
HullBoundaryPoints::ExtremesOnly,
HullBoundaryPoints::KeepAllOnBoundary,
] {
let a = convex_hull2(&pts, mode);
let b = convex_hull2(&shuffled, mode);
assert_eq!(a.vertices(), b.vertices());
}
}
#[test]
fn idempotent() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
];
let once = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
let twice = convex_hull2(once.vertices(), HullBoundaryPoints::ExtremesOnly);
assert_eq!(once.vertices(), twice.vertices());
}
}