平面点集凸包平面点集凸包代码

平面点集的凸包（Convex Hull）是指在一个平面上，所有点集中点的最小子集，构成一个不包含内部点的凸多边形。这个概念在计算机图形学、几何算法和数据分析中非常常见。要编写一个计算凸包的代码，通常会使用诸如 Graham 扫描法、快速 hull 算法（如 Jarvis March 或 Andrew 算法）或 Gift Wrapping 算法等高效的算法。

这里提供一个基于 Gift Wrapping 算法的简单 Python 示例，它假设你有一个二维列表（二维数组）存储了点集：

def convex_hull(points):
    if len(points) < 3:  # 凸包至少需要3个点
        return points

    # 将点按 X 坐标排序
    points.sort(key=lambda x: x)

    hull = [points, points]  # 初始化凸包，包含第一个点和第二个点
    for i in range(2, len(points)):
        while len(hull) >= 2 and cross_product(hull[-2], hull[-1], points[i]) <= 0:
            hull.pop()  # 如果当前点在凸包内部，则移除最后一个点
        hull.append(points[i])

    # 因为最后两个点可能共线，所以需要再次检查并添加最后一个点
    if hull and cross_product(hull[-2], hull[-1], points) <= 0:
        hull.pop()

    return hull


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

# 使用示例
points = [[1, 1], [2, 2], [3, 3], [4, 4], [1, 4]]
convex_hull_points = convex_hull(points)
print("凸包为:", convex_hull_points)

这个代码定义了一个 `convex_hull` 函数，其中包含 `cross_product` 函数用于计算向量的叉积，这在判断三点是否构成凸包方向上很重要。