python 凸包算法

凸包算法是计算给定点集的最小凸多边形的一种算法，通常有多种实现方式，其中常用的有 Jarvis 算法、Graham 算法和 QuickHull 算法。

以下是 Python 语言中的几种凸包算法实现：

1. Jarvis 算法：

def orientation(p, q, r):
    # 计算叉乘
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # 三点共线
    elif val > 0:
        return 1  # 顺时针
    else:
        return 2  # 逆时针

def convex_hull(points):
    n = len(points)
    if n < 3:
        return []  # 无法构成凸包
    hull = []
    l = 0
    for i in range(1, n):
        if points[i][0] < points[l][0]:
            l = i
    p = l
    while True:
        hull.append(points[p])
        q = (p + 1) % n
        for i in range(n):
            if orientation(points[p], points[i], points[q]) == 2:
                q = i
        p = q
        if p == l:
            break
    return hull

2. Graham 算法：

def orientation(p, q, r):
    # 计算叉乘
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # 三点共线
    elif val > 0:
        return 1  # 顺时针
    else:
        return 2  # 逆时针

def convex_hull(points):
    n = len(points)
    if n < 3:
        return []  # 无法构成凸包
    hull = []
    l = 0
    for i in range(1, n):
        if points[i][0] < points[l][0]:
            l = i
    hull.append(points[l])
    hull.append(points[(l + 1) % n])
    for i in range(2, n):
        while len(hull) >= 2 and orientation(hull[-2], hull[-1], points[i]) != 2:
            hull.pop()
        hull.append(points[i])
    return hull

3. QuickHull 算法：

def distance(p, q, r):
    # 计算点到直线距离
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

def find_hull(points, p1, p2, side):
    if not points:
        return []
    else:
        # 找到距离直线距离最大的点
        max_dist = -1
        max_point = None
        for point in points:
            dist = abs(distance(p1, p2, point))
            if dist > max_dist and side(p1, p2, point):
                max_dist = dist
                max_point = point
        if not max_point:
            return [p1, p2]
        # 递归寻找凸包
        left_points = [point for point in points if distance(p1, max_point, point) > 0]
        right_points = [point for point in points if distance(max_point, p2, point) > 0]
        left_hull = find_hull(left_points, p1, max_point, lambda a, b, c: distance(a, b, c) > 0)
        right_hull = find_hull(right_points, max_point, p2, lambda a, b, c: distance(a, b, c) < 0)
        return left_hull + right_hull

def convex_hull(points):
    n = len(points)
    if n < 3:
        return []  # 无法构成凸包
    # 找到最左和最右的点
    left_point = min(points, key=lambda point: point[0])
    right_point = max(points, key=lambda point: point[0])
    # 递归寻找凸包
    left_points = [point for point in points if distance(left_point, right_point, point) > 0]
    right_points = [point for point in points if distance(left_point, right_point, point) < 0]
    left_hull = find_hull(left_points, left_point, right_point, lambda a, b, c: distance(a, b, c) > 0)
    right_hull = find_hull(right_points, right_point, left_point, lambda a, b, c: distance(a, b, c) < 0)
    return left_hull + right_hull