Given a set of points in the plane, find the smallest convex polygon that encloses all points.

Problem: Convex Hull (Graham Scan) – Given a set of points in the plane, find the smallest convex polygon that encloses all points.

Topic: Computational Geometry

Understanding Convex Hull and Graham Scan

Convex Hull

In computational geometry, the Convex Hull of a set of points is the smallest convex polygon that encloses all the points. Imagine stretching a rubber band around a set of nails on a board and then letting it go. The shape formed by the rubber band is the convex hull.

Graham Scan Algorithm

The Graham Scan algorithm is an efficient way to find the Convex Hull of a set of points. It operates in (O(n \log n)) time, where (n) is the number of points. This efficiency comes from sorting the points and then making a single pass to build the hull.

Steps for the Graham Scan Algorithm

1. Find the Pivot Point:

• Select the point with the lowest y-coordinate (and in case of a tie, the leftmost x-coordinate) as the pivot. This point will be the starting point for the convex hull.

1. Sort the Points:

• Sort all the points based on the polar angle with respect to the pivot point. This helps in processing points in a circular manner around the pivot.

1. Build the Hull:

• Initialize an empty stack and push the pivot point onto it.
• Iterate over the sorted points and use a stack to maintain the convex hull. For each point, determine whether moving from the last two points to the current point makes a left turn or a right turn. If it’s a right turn, pop the last point from the stack.

1. Finalizing the Hull:

• After processing all the points, the stack will contain the vertices of the convex hull in counter-clockwise order.

Detailed Code and Explanation

Let’s write the code step-by-step. We’ll be using Python for this implementation.

Step 1: Import Required Libraries

import math

We use the math library for trigonometric calculations and distance measurements.

Step 2: Define Helper Functions

1. Calculate the Polar Angle The polar angle is used to sort the points around the pivot.

   def polar_angle(p0, p1):
       """Calculate the polar angle between p0 and p1."""
       return math.atan2(p1[1] - p0[1], p1[0] - p0[0])

2. Calculate the Cross Product The cross product helps determine the orientation of the turn (left or right).

   def cross_product(o, a, b):
       """Return the cross product of vectors OA and OB
       A positive cross product indicates a left turn, a negative indicates a right turn, and zero indicates a collinear point."""
       return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

Step 3: Define the Main Function to Compute the Convex Hull

def graham_scan(points):
    """Compute the convex hull of a set of 2D points."""
    # Step 1: Find the pivot point
    pivot = min(points, key=lambda p: (p[1], p[0]))

    # Step 2: Sort the points by polar angle with respect to the pivot
    sorted_points = sorted(points, key=lambda p: (polar_angle(pivot, p), -p[0], p[1]))

    # Step 3: Build the convex hull using a stack
    hull = []

    for p in sorted_points:
        # While we do not have a counter-clockwise turn, pop the top of the stack
        while len(hull) >= 2 and cross_product(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)

    return hull

Explanation of the Main Function

1. Finding the Pivot Point:

• We select the lowest y-coordinate point. If there are ties (multiple points with the same y-coordinate), we choose the one with the smallest x-coordinate.

1. Sorting Points:

• Points are sorted based on the polar angle with respect to the pivot. This ensures we process them in a circular order around the pivot.

1. Building the Hull:

• We maintain a stack to keep track of the points on the convex hull. For each point in the sorted list, we ensure that we always make a counter-clockwise turn by checking the cross product.

Full Code with Example

Here’s the complete Python script including the example usage:

import math

def polar_angle(p0, p1):
    return math.atan2(p1[1] - p0[1], p1[0] - p0[0])

def cross_product(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def graham_scan(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))
    sorted_points = sorted(points, key=lambda p: (polar_angle(pivot, p), -p[0], p[1]))

    hull = []

    for p in sorted_points:
        while len(hull) >= 2 and cross_product(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)

    return hull

# Example usage
points = [(0, 0), (1, 1), (2, 2), (2, 0), (1, -1), (0, 2)]
hull = graham_scan(points)
print("Convex Hull:", hull)

Detailed Explanation

Let’s dive deeper into the Graham Scan algorithm, its components, and how they work together in detail.

Convex Hull Concept

The Convex Hull of a set of points is essentially the smallest convex boundary that can encompass all the points. Mathematically, a set of points is convex if the line segment between any two points in the set lies within the set. The Convex Hull problem is fundamental in computational geometry and has various applications such as in computer graphics, pattern recognition, and geographic information systems.

Graham Scan Algorithm Overview

The Graham Scan algorithm is an elegant and efficient way to solve the Convex Hull problem. It’s based on sorting the points and then processing them to build the convex boundary. The algorithm proceeds in two main phases:

1. Finding the Pivot:

• The pivot is the point with the lowest y-coordinate (and in case of ties, the smallest x-coordinate). This point serves as the starting point for the scan.

1. Sorting and Building the Hull:

• Points are sorted around the pivot based on their polar angle. The convex hull is constructed by iterating through the sorted points and maintaining a stack of points that form the convex boundary.

Detailed Steps

Step 1: Finding the Pivot Point

The pivot point is crucial because it determines the reference for sorting other points. It’s the point from which all other points’ polar angles are calculated. By choosing the point with the smallest y-coordinate (and smallest x in case of ties), we ensure that our sorting will always place the pivot in the “lowest” position, making the sorting step straightforward.

def find_pivot(points):
    """Find the pivot point with the lowest y-coordinate, and in case of tie, the leftmost x-coordinate."""
    return min(points, key=lambda p: (p[1], p[0]))

Step 2: Calculating Polar Angles

Polar angles are used to determine the relative positions of points around the pivot. The angle is calculated using the atan2 function, which returns the angle in radians between the positive x-axis and the line segment from the origin to the point.

def polar_angle(p0, p1):
    """Calculate the polar angle of point p1 with respect to the pivot p0."""
    return math.atan2(p1[1] - p0[1], p1[0] - p0[0])

Step 3: Cross Product to Determine Turn Direction

The cross product is used to check the orientation of the turn. If the cross product is positive, the turn is counter-clockwise (left). If negative, it’s clockwise (right). If zero, the points are collinear.

def cross_product(o, a, b):
    """Calculate the cross product of vectors OA and OB to determine the turn direction."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

Step 4: Sorting Points

Points are sorted around the pivot based on their polar angles. Sorting ensures that we process points in a circular manner, which simplifies the convex hull construction.

def sort_points_around_pivot(points, pivot):
    """Sort points around the pivot based on their polar angle."""
    return sorted(points, key=lambda p: (polar_angle(pivot, p), -p[0], p[1]))

Step 5: Building the Convex Hull

Using a stack, we construct the convex hull by maintaining only the necessary points that form the boundary. We ensure that we only include points that make a counter-clockwise turn.

def graham_scan(points):
    """Compute the convex hull using Graham Scan algorithm."""
    if len(points) <= 1:
        return points

    # Step 1: Find the pivot point
    pivot = find_pivot(points)

    # Step 2: Sort the points based on polar angle with respect to pivot
    sorted_points = sort_points_around_pivot(points, pivot)

    # Step 3: Initialize the hull with the pivot point
    hull = []

    for p in sorted_points:
        while len(hull) >= 2 and cross_product(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)

    return hull

Full Code

Let’s provide a complete example with additional comments and a more extensive test case.

import math

def find_pivot(points):
    """Find the pivot point with the lowest y-coordinate, and in case of tie, the leftmost x-coordinate."""
    return min(points, key=lambda p: (p[1], p[0]))

def polar_angle(p0, p1):
    """Calculate the polar angle of point p1 with respect to the pivot p0."""
    return math.atan2(p1[1] - p0[1], p1[0] - p0[0])

def cross_product(o, a, b):
    """Calculate the cross product of vectors OA and OB to determine the turn direction."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def sort_points_around_pivot(points, pivot):
    """Sort points around the pivot based on their polar angle."""
    return sorted(points, key=lambda p: (polar_angle(pivot, p), -p[0], p[1]))

def graham_scan(points):
    """Compute the convex hull using Graham Scan algorithm."""
    if len(points) <= 1:
        return points

    # Step 1: Find the pivot point
    pivot = find_pivot(points)

    # Step 2: Sort the points based on polar angle with respect to pivot
    sorted_points = sort_points_around_pivot(points, pivot)

    # Step 3: Initialize the hull with the pivot point
    hull = []

    for p in sorted_points:
        while len(hull) >= 2 and cross_product(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)

    return hull

# Example usage
if __name__ == "__main__":
    # Define a set of points
    points = [(0, 0), (1, 1), (2, 2), (2, 0), (1, -1), (0, 2), (3, 1), (1, 0), (0, 1)]

    # Compute the convex hull
    hull = graham_scan(points)

    # Print the result
    print("Convex Hull:")
    for point in hull:
        print(point)

Explanation of the Example

1. Points: A diverse set of points including collinear points and varying orientations.
2. Computing Hull: The graham_scan function will compute the convex boundary.
3. Output: The convex hull is printed, showing the points in counter-clockwise order.

Share on Facebook

Post on X

Follow us

Save