凸包算法可视化

步骤	复杂度	说明
找基点	O(n)	遍历所有点
极角排序	O(n log n)	决定整体复杂度
栈处理	O(n)	每个点最多入栈出栈各一次
总时间	O(n log n)	排序主导
空间复杂度	O(n)	存储栈

代码实现

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;
    }
}

Graham Scan 步骤

时间与空间复杂度

应用场景

代码实现