凸包操作是图像处理中的一种重要技术，尤其在轮廓分析和目标识别中具有广泛应用。在不使用 OpenCV 的前提下，可以通过实现 Graham 扫描法或 Jarvis 步进法（Gift Wrapping Algorithm）来手动计算一组点的凸包。 ### 实现原理 凸包的计算通常基于二维点集，目标是找到包围所有点的最小凸多边形。Graham 扫描法是一种高效的凸包计算方法，其基本步骤如下： 1. 找出点集中最下方（或最左方）的点作为起始点； 2. 将其余点按照相对于起始点的极角排序； 3. 使用栈结构依次处理点，确保每三个连续点构成非右转（非凹角）关系，否则弹出栈顶点； 4. 最终栈中保存的点即为凸包顶点。 该方法的时间复杂度为 $ O(n \log n) $，适用于中等规模的点集处理。 ### 代码实现 以下是一个基于 Graham 扫描法实现凸包计算的 Python 示例： ```python import math def cross_product(o, a, b): # 计算向量 OA 和 OB 的叉积 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def distance(p1, p2): # 计算两点之间的欧氏距离 return math.hypot(p2[0] - p1[0], p2[1] - p1[1]) def graham_scan(points): # 找到最左下角的点作为基准点 start_point = min(points, key=lambda p: (p[1], p[0])) # 按照极角排序 sorted_points = sorted(points, key=lambda p: (math.atan2(p[1] - start_point[1], p[0] - start_point[0]), distance(start_point, p))) # 构建上下两个凸链 lower = [] upper = [] for p in sorted_points: while len(upper) >= 2 and cross_product(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) while len(lower) >= 2 and cross_product(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # 合并上下链，去除首尾重复点 full_hull = upper + lower[:-1][::-1] return full_hull ``` 上述代码中，`cross_product` 函数用于判断三点之间的转向关系，`distance` 函数用于计算两点之间的距离，`graham_scan` 函数实现了完整的凸包计算流程。 ### 应用场景 该算法可以用于图像处理中从轮廓点集中提取凸包，例如手势识别中的手部轮廓分析。通过获取轮廓点集，可以使用上述方法计算凸包，并进一步分析凹陷区域，从而判断手指数量等信息。 ###