Function graham_scan

pub fn graham_scan<I>(points: &[(I, I)]) -> Vec<(I, I)>
where
    I: PrimInt,

Returns a subset of the input points representing their convex hull.

Points are returned in counterclockwise order, starting with the point that has the smallest y value (and smallest x value if there is a tie).

This function uses Graham’s scan to find the convex hull. To keep things generic and simple, this function takes 2-tulples of integers.

Panics

Panics if any of the calculations overflow and debug assertions are on.

Example

use rust_dsa::graham_scan;

let points = [
    (6, 0), (-4, 10), (-9, -6), (-15, -6), (15, 14), (1, -16), (3, -19), (17, 11),
    (5, -7), (2, 3), (10, 3), (20, 3), (-8, 1), (20, -13), (-10, 1), (8, 16),
];
let expected_hull = [(3, -19), (20, -13), (20, 3), (17, 11), (15, 14), (8, 16), (-4, 10), (-15, -6)];

assert_eq!(graham_scan(&points), expected_hull.to_vec());


let points = [(0, 0), (1, 2), (4, 0), (2, 4), (0, 8)];
let expected_hull = [(0, 0), (4, 0), (0, 8)];

assert_eq!(graham_scan(&points), expected_hull.to_vec());