Convex Hull Visualization - Graham Scan

Convex Hull is the smallest convex polygon containing all given points. Graham Scan uses polar angle sorting and stack operations to efficiently compute the convex hull in O(n log n) time.

Click canvas to add points, or generate automatically

Graham Scan Steps

Find point P0 with minimum y-coordinate (then minimum x if tie)
Sort all other points by polar angle relative to P0
Initialize stack with P0 and first sorted point
Process remaining points:
If new point causes 'right turn' with top two stack elements, pop top
Repeat until 'left turn', then push new point
Stack contains convex hull vertices

Time and Space Complexity

Step	Complexity	Description
Find Base Point	O(n)	Traverse all points
Polar Angle Sort	O(n log n)	Dominates overall complexity
Stack Processing	O(n)	Each point pushed/popped at most once
Total Time	O(n log n)	Dominated by sorting
Space Complexity	O(n)	Store stack

Applications

Collision detection in graphics
Boundary computation in GIS
Robot path planning
Object contours in image processing
Minimum bounding box computation
Outlier detection in statistics

Collision Detection GIS Robotics Image Processing

Implementation

def cross(o, a, b):
    """叉积判断转向方向"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def convex_hull(points):
    """Graham Scan算法计算凸包"""
    points = sorted(set(map(tuple, points)))
    
    if len(points) <= 1:
        return points
    
    # 构建下凸壳
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    
    # 构建上凸壳
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    
    # 合并（去除重复端点）
    return lower[:-1] + upper[:-1]


# 使用示例
points = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0)]
hull = convex_hull(points)
print(hull)  # [(0, 0), (2, 0), (2, 2), (0, 2)]

import java.util.*;

public class ConvexHull {
    
    /**
     * 叉积判断转向
     */
    private static long cross(int[] o, int[] a, int[] b) {
        return (long)(a[0] - o[0]) * (b[1] - o[1]) 
             - (long)(a[1] - o[1]) * (b[0] - o[0]);
    }
    
    /**
     * Graham Scan算法计算凸包
     */
    public static List<int[]> convexHull(int[][] points) {
        int n = points.length;
        if (n < 3) return Arrays.asList(points);
        
        // 按坐标排序
        Arrays.sort(points, (a, b) -> 
            a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        List<int[]> hull = new ArrayList<>();
        
        // 下凸壳
        for (int[] p : points) {
            while (hull.size() >= 2 && 
                   cross(hull.get(hull.size()-2), 
                        hull.get(hull.size()-1), p) <= 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }
        
        // 上凸壳
        int lowerSize = hull.size();
        for (int i = n - 2; i >= 0; i--) {
            while (hull.size() > lowerSize && 
                   cross(hull.get(hull.size()-2),
                        hull.get(hull.size()-1), points[i]) <= 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(points[i]);
        }
        
        hull.remove(hull.size() - 1);
        return hull;
    }
}