用python写一个凸包算法

凸包算法是计算一个点集的最小凸包（最小外接多边形）的算法。下面是用 Python 实现的一个简单的凸包算法：

首先，我们需要先导入一个名为 `math` 的库，它包含了一些常用的数学函数：

import math

接下来，我们需要定义一个叫 `orientation()` 的函数，它用来计算点集中的三个点的方向：

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
    return 1 if val > 0 else 2

然后，我们需要定义一个叫 `convex_hull()` 的函数，它用来计算点集的凸包：

def convex_hull(points):
    n = len(points)
    if n < 3:
        return []
    hull = []
    l = 0
    for i in range(n):
        if points[i][0] < points[l][0]:
            l = i
    p = l
    q = 0
    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

这个函数的参数 `points` 是一个点集，它应该是一个列表，列表中的每个元素都是一个长度为 2 的元组，表示平面中的一个点。

这个函数首先判断点集中的点数是否小于 3，如果是的话直接返回一个空列表。

然后找到点集中 x 坐标最小的点，并将其保存到变量 `l` 中。

接下来，我们定义两个变量 `p` 和 `q`，它们分别表示当前的起点和终点。一开始，它们的值都是 `l`。

然后进入一个无限循环，每次循环都将起点 `p` 添加到凸包中。然后我们找到一个点 `q`，这个点是点集中与起点 `p` 连线所在直线向右（在计算机屏幕上，向下是正方向，所以这里是“向右”）的下一个点。具体来说，我们遍历点集中的每个点，如果这个点在当前的直线的右边，我们就将 `q` 更新为这个点。这个操作实际上是在寻找凸包上的下一个点。

然后将终点 `p` 更新为新的 `q`。如果 `q` 的值等于起点 `l` 的值，说明我们已经遍历完了整个凸包，退出循环。最后返回保存凸包点的列表 `hull`。