### 使用Python实现二维凸包算法 #### 卷包裹法（Gift Wrapping） 卷包裹法是一种易于理解但效率较低的构建二维凸包的方法。此方法通过逐步选择最外层的点来形成包围所有给定点集的多边形[^1]。 ```python def gift_wrapping(points): def polar_angle(p0, p1=None): if p1 is None: p1 = anchor y_span = p0[1] - p1[1] x_span = p0[0] - p1[0] return math.atan2(y_span, x_span) def distance(p0, p1=None): if p1 is None: p1 = anchor y_span = p0[1] - p1[1] x_span = p0[0] - p1[0] return y_span ** 2 + x_span ** 2 def next_point(): index = 0 for i in range(1, len(points)): if (polar_angle(points[i]) < polar_angle(points[index])) or \ ((polar_angle(points[i]) == polar_angle(points[index])) and (distance(points[i]) > distance(points[index]))): index = i return points[index] min_index = None for i in range(len(points)): if min_index is None or points[i][1] < points[min_index][1]: min_index = i elif points[i][1] == points[min_index][1]: if points[i][0] < points[min_index][0]: min_index = i anchor = points[min_index] hull = [anchor] point = next_point() while point != anchor: hull.append(point) endpoint = None for potential_next in points: side = sign(cross_product(hull[-2], hull[-1], potential_next)) if side == -1 or (side == 0 and distance(potential_next) >= distance(endpoint)): endpoint = potential_next point = endpoint return hull[:-1] points = [(0, 0), (1, 1), (1, 0), (0, 1), (0.5, 0.5)] print(gift_wrapping(points)) ``` #### 利用`QuickHull`库 对于更高效的解决方案，可以利用专门设计用于求解此类问题的第三方库——`quickhull`。安装并导入必要的模块之后，仅需几行代码即可完成操作[^2]。 ```python from quickhull import QuickHull # 示例数据集 points = [(0, 0), (1, 1), (1, 0), (0, 1), (0.5, 0.5)] qh = QuickHull() # 计算凸包 hull = qh.convex_hull(points) # 输出凸包的顶点 for vertex in hull.vertices: print(vertex) ```