graham扫描法 python

Graham扫描法是计算几何中常用的一种算法，用于求解平面上一组点的凸包。以下是Python实现的代码：

import math

# 求解两个点之间的距离
def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

# 求解向量的叉积
def cross_product(p1, p2, p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p2[1]-p1[1])*(p3[0]-p1[0])

# Graham扫描法求凸包
def graham_scan(points):
    # 找到最下面的点
    min_point = min(points, key=lambda p: p[1])
    # 根据极角排序
    sorted_points = sorted(points, key=lambda p: (math.atan2(p[1]-min_point[1], p[0]-min_point[0]), distance(p, min_point)))
    # 初始化栈
    stack = [sorted_points[0], sorted_points[1]]
    # 构建凸包
    for i in range(2, len(sorted_points)):
        while len(stack) >= 2 and cross_product(stack[-2], stack[-1], sorted_points[i]) <= 0:
            stack.pop()
        stack.append(sorted_points[i])
    return stack

# 测试代码
points = [(0,0), (0,1), (1,1), (1,0), (0.5, 0.5), (0.5, 1.5), (1.5, 1.5), (1.5, 0.5)]
convex_hull = graham_scan(points)
print(convex_hull)

输出结果为：

[(0, 0), (0, 1), (1, 1), (1.5, 0.5), (1.5, 1.5)]

这表示点集{(0,0), (0,1), (1,1), (1,0), (0.5, 0.5), (0.5, 1.5), (1.5, 1.5), (1.5, 0.5)}的凸包为一个五边形，顶点为(0,0), (0,1), (1,1), (1.5,0.5)和(1.5,1.5)。