QuickHull 算法

QuickHull算法是一种用于计算凸包的分治算法。它的基本思想是在点集中找到距离凸包最远的点，然后将点集分成两个子集，分别递归地处理这两个子集。最终，将所有的凸包合并起来就得到了完整的凸包。以下是QuickHull算法的步骤：

1. 找到距离凸包最远的点，将其加入凸包中。
2. 将点集分成两个子集，分别在凸包的左侧和右侧。
3. 对于每个子集，重复步骤1和步骤2，直到没有点可以加入凸包为止。
4. 将两个子集的凸包合并起来，得到完整的凸包。

以下是Python实现QuickHull算法的代码：

def quickHull(points):
    if len(points) < 3:
        return points
    leftmost = min(points, key=lambda x: x[0])
    rightmost = max(points, key=lambda x: x[0])
    hull = [leftmost, rightmost]
    points.remove(leftmost)
    points.remove(rightmost)
    leftSet = []
    rightSet = []
    for p in points:
        if crossProduct(hull[-1], leftmost, p) > 0:
            leftSet.append(p)
        elif crossProduct(hull[-1], rightmost, p) < 0:
            rightSet.append(p)
    buildHull(leftSet, hull, leftmost, hull[-1])
    buildHull(rightSet, hull, hull[-2], rightmost)
    return hull

def buildHull(points, hull, p1, p2):
    if not points:
        return
    farthest = max(points, key=lambda x: distance(p1, p2, x))
    hull.insert(hull.index(p2), farthest)
    points.remove(farthest)
    leftSet = []
    rightSet = []
    for p in points:
        if crossProduct(hull[-1], p2, p) > 0:
            leftSet.append(p)
        elif crossProduct(p1, hull[-1], p) > 0:
            rightSet.append(p)
    buildHull(leftSet, hull, p1, farthest)
    buildHull(rightSet, hull, farthest, p2)

def crossProduct(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

def distance(p1, p2, p3):
    return abs(crossProduct(p1, p2, p3)) / ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** 0.5