Convex Hull (Graham Scan)

Welcome to a fascinating journey through the world of Convex Hull! In this lesson, we'll explore the Graham Scan algorithm, a powerful tool for finding the convex hull of a set of points in a plane. Let's dive in! 🎯

What is Convex Hull?

A convex hull is the smallest convex polygon that can enclose a set of points in a plane. It's a fundamental concept in computer graphics, geometry, and algorithm design. Let's understand it with an example:

Convex Hull Example

In this example, the red polygon is the convex hull of the given points.

Understanding the Graham Scan Algorithm

The Graham Scan algorithm is designed to find the convex hull of a set of points in a plane. It has three main phases:

Sorting the points: We sort the points based on their angles to a given reference line. The goal is to find a point with the smallest positive angle and a point with the largest negative angle.
Building the left hull: We build the left hull, which is the part of the convex hull that lies to the left of the reference line. This process involves adding points to the hull one by one.
Building the right hull: Once we have the left hull, we can easily find the right hull, which is the part of the convex hull that lies to the right of the reference line.

Implementing the Graham Scan Algorithm

Here's a step-by-step implementation of the Graham Scan algorithm:

Choose a point (p0) as the reference point. Typically, we choose the point with the smallest y-coordinate.
Sort the remaining points based on their angles to the line passing through p0 and the x-axis. The angle is calculated as atan2(y - p0.y, x - p0.x). The points are sorted in ascending order of their angles.
The first point (p1) and the last point (pl) in the sorted list form the initial line of the left hull.
For each point pi (i > 1) in the sorted list, do the following:

a. Draw a line from the current point on the left hull (ph) to the current point (pi).

b. If the line does not go outside the convex hull (i.e., it does not intersect the line segment between ph and the next point on the left hull), update the hull by moving to the next point on the left hull.

c. If the line intersects the line segment between ph and the next point on the left hull, or if ph is on the left side of the line, replace ph with pi.
Once we have the left hull, we can easily find the right hull by reversing the order of the points and following the same process.

Code Example 1 - Sorting Points

python

def sort_points(points):
    points.sort(key=lambda point: math.atan2(point[1] - points[0][1], point[0] - points[0][0]))

Code Example 2 - Building the Convex Hull

python

def build_convex_hull(points):
    sorted_points = sort_points(points)

    left_hull = [sorted_points[0], sorted_points[-1]]
    right_hull = []

    for point in sorted_points:
        while len(left_hull) > 1 and is_left_turn(left_hull[-2], left_hull[-1], point):
            left_hull.pop()
        left_hull.append(point)

    for point in reversed(sorted_points):
        while len(right_hull) > 1 and is_left_turn(right_hull[-2], right_hull[-1], point):
            right_hull.pop()
        right_hull.append(point)

    return left_hull + right_hull[::-1]

def is_left_turn(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p2[1]) > (p2[1] - p1[1]) * (p3[0] - p2[0])

Quiz Time! 📝

Summary

Congratulations on learning the Graham Scan algorithm for finding the convex hull of a set of points in a plane! This algorithm is a valuable tool for anyone working in computer graphics, geometry, and algorithm design. We hope this lesson has been helpful in understanding the concept and implementation of the Graham Scan algorithm. 💡

Remember to practice implementing the algorithm with different sets of points to solidify your understanding. Happy coding! ✅