基于边界的目标表达凸包算法python

以下是一个基于边界的目标表达凸包算法的 Python 实现：

def orientation(p, q, r):
    """
    计算三个点的方向。
    如果斜率为正，则返回1；
    如果斜率为负，则返回2；
    否则返回0。
    """
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else 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

        # 如果我们回到了起点，那么凸包已经完成。
        if q == l:
            break

        p = q

    return hull

这个算法的时间复杂度为 $O(n\log n)$，其中 $n$ 是点的数量。