jarvis_scan.rs

use crate::geometry::Point;
use crate::geometry::Segment;

// Returns a Vec of Points that make up the convex hull of `points`. Returns an empty Vec if there
// is no convex hull.
pub fn jarvis_march(points: Vec<Point>) -> Vec<Point> {
    if points.len() <= 2 {
        return vec![];
    }

    let mut convex_hull = vec![];
    let mut left_point = 0;
    for i in 1..points.len() {
        // Find the initial point, which is the leftmost point. In the case of a tie, we take the
        // bottom-most point. This helps prevent adding colinear points on the last segment to the hull.
        if points[i].x < points[left_point].x
            || (points[i].x == points[left_point].x && points[i].y < points[left_point].y)
        {
            left_point = i;
        }
    }
    convex_hull.push(points[left_point].clone());

    let mut p = left_point;
    loop {
        // Find the next counter-clockwise point.
        let mut next_p = (p + 1) % points.len();
        for i in 0..points.len() {
            let orientation = points[p].consecutive_orientation(&points[i], &points[next_p]);
            if orientation > 0.0 {
                next_p = i;
            }
        }

        if next_p == left_point {
            // Completed constructing the hull. Exit the loop.
            break;
        }
        p = next_p;

        let last = convex_hull.len() - 1;
        if convex_hull.len() > 1
            && Segment::from_points(points[p].clone(), convex_hull[last - 1].clone())
                .on_segment(&convex_hull[last])
        {
            // If the last point lies on the segment with the new point and the second to last
            // point, we can remove the last point from the hull.
            convex_hull[last] = points[p].clone();
        } else {
            convex_hull.push(points[p].clone());
        }
    }

    if convex_hull.len() <= 2 {
        return vec![];
    }
    let last = convex_hull.len() - 1;
    if Segment::from_points(convex_hull[0].clone(), convex_hull[last - 1].clone())
        .on_segment(&convex_hull[last])
    {
        // Check for the edge case where the last point lies on the segment with the zero'th and
        // second the last point. In this case, we remove the last point from the hull.
        convex_hull.pop();
        if convex_hull.len() == 2 {
            return vec![];
        }
    }
    convex_hull
}

#[cfg(test)]
mod tests {
    use super::jarvis_march;
    use super::Point;

    fn test_jarvis(convex_hull: Vec<Point>, others: Vec<Point>) {
        let mut points = others.clone();
        points.append(&mut convex_hull.clone());
        let jarvis = jarvis_march(points);
        for point in convex_hull {
            assert!(jarvis.contains(&point));
        }
        for point in others {
            assert!(!jarvis.contains(&point));
        }
    }

    #[test]
    fn too_few_points() {
        test_jarvis(vec![], vec![]);
        test_jarvis(vec![], vec![Point::new(0.0, 0.0)]);
    }

    #[test]
    fn duplicate_point() {
        let p = Point::new(0.0, 0.0);
        test_jarvis(vec![], vec![p.clone(), p.clone(), p.clone(), p.clone(), p]);
    }

    #[test]
    fn points_same_line() {
        let p1 = Point::new(1.0, 0.0);
        let p2 = Point::new(2.0, 0.0);
        let p3 = Point::new(3.0, 0.0);
        let p4 = Point::new(4.0, 0.0);
        let p5 = Point::new(5.0, 0.0);
        // let p6 = Point::new(1.0, 1.0);
        test_jarvis(vec![], vec![p1, p2, p3, p4, p5]);
    }

    #[test]
    fn triangle() {
        let p1 = Point::new(1.0, 1.0);
        let p2 = Point::new(2.0, 1.0);
        let p3 = Point::new(1.5, 2.0);
        let points = vec![p1, p2, p3];
        test_jarvis(points, vec![]);
    }

    #[test]
    fn rectangle() {
        let p1 = Point::new(1.0, 1.0);
        let p2 = Point::new(2.0, 1.0);
        let p3 = Point::new(2.0, 2.0);
        let p4 = Point::new(1.0, 2.0);
        let points = vec![p1, p2, p3, p4];
        test_jarvis(points, vec![]);
    }

    #[test]
    fn triangle_with_points_in_middle() {
        let p1 = Point::new(1.0, 1.0);
        let p2 = Point::new(2.0, 1.0);
        let p3 = Point::new(1.5, 2.0);
        let p4 = Point::new(1.5, 1.5);
        let p5 = Point::new(1.2, 1.3);
        let p6 = Point::new(1.8, 1.2);
        let p7 = Point::new(1.5, 1.9);
        let hull = vec![p1, p2, p3];
        let others = vec![p4, p5, p6, p7];
        test_jarvis(hull, others);
    }

    #[test]
    fn rectangle_with_points_in_middle() {
        let p1 = Point::new(1.0, 1.0);
        let p2 = Point::new(2.0, 1.0);
        let p3 = Point::new(2.0, 2.0);
        let p4 = Point::new(1.0, 2.0);
        let p5 = Point::new(1.5, 1.5);
        let p6 = Point::new(1.2, 1.3);
        let p7 = Point::new(1.8, 1.2);
        let p8 = Point::new(1.9, 1.7);
        let p9 = Point::new(1.4, 1.9);
        let hull = vec![p1, p2, p3, p4];
        let others = vec![p5, p6, p7, p8, p9];
        test_jarvis(hull, others);
    }

    #[test]
    fn star() {
        // A single stroke star shape (kind of). Only the tips(p1-5) are part of the convex hull. The
        // other points would create angles >180 degrees if they were part of the polygon.
        let p1 = Point::new(-5.0, 6.0);
        let p2 = Point::new(-11.0, 0.0);
        let p3 = Point::new(-9.0, -8.0);
        let p4 = Point::new(4.0, 4.0);
        let p5 = Point::new(6.0, -7.0);
        let p6 = Point::new(-7.0, -2.0);
        let p7 = Point::new(-2.0, -4.0);
        let p8 = Point::new(0.0, 1.0);
        let p9 = Point::new(1.0, 0.0);
        let p10 = Point::new(-6.0, 1.0);
        let hull = vec![p1, p2, p3, p4, p5];
        let others = vec![p6, p7, p8, p9, p10];
        test_jarvis(hull, others);
    }

    #[test]
    fn rectangle_with_points_on_same_line() {
        let p1 = Point::new(1.0, 1.0);
        let p2 = Point::new(2.0, 1.0);
        let p3 = Point::new(2.0, 2.0);
        let p4 = Point::new(1.0, 2.0);
        let p5 = Point::new(1.5, 1.0);
        let p6 = Point::new(1.0, 1.5);
        let p7 = Point::new(2.0, 1.5);
        let p8 = Point::new(1.5, 2.0);
        let hull = vec![p1, p2, p3, p4];
        let others = vec![p5, p6, p7, p8];
        test_jarvis(hull, others);
    }
}