convhull 源码

convhull，也被称为凸包算法，是一种计算给定点集凸包的常见算法。凸包是一个包围点集的最小凸多边形。

通常，convhull算法可以分为以下几个步骤：
1. 首先，我们需要找到点集中最左边的点，以及该点集中所有点的最右边位置。这可以通过遍历所有点并比较它们的坐标来实现。

2. 然后，我们需要根据两个极点，从最右边位置开始，在逆时针方向上对点集进行排序。这可以通过计算每个点相对于极点的极角来实现。

3. 排序后的点集根据Andrew's Monotone Chain算法进行处理，该算法用于从排序的点集中构造convex hull。该算法从最左边的点开始，移动到最右边的点，然后返回到最左边的点。

4. 在Andrew's Monotone Chain算法的第一步中，我们需要选择前k个点（其中k>1），以使其构成convex hull的一部分。第一个点是最左边的点，第二个点是排在第一点后面的最近点。此后的每个点应该在前一个点和已选择的点之间形成反向转弯。如果它不是这样，那么需要删除前一个点，并继续比较前两个点直到满足条件。

5. 最后，我们将形成的凸多边形作为结果返回。

根据以上步骤，我们可以编写convhull的源码。这段源码将实现上述步骤来计算给定点集的凸包。

import math

def orientation(p, q, r):
    """计算点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 convexHull(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
    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

以上就是convhull算法的一个简单实现。这段代码可以计算给定点集的凸包，并将结果以一个代表凸多边形的点集返回。