使用Graham扫描算法求点组的最小凸包,返回的是一个列表的列表,子列表由线段起点和终点组成,最后打印并使用matplotlib.pyplot进行可视化

Graham扫描算法[^1]可以用来求解二维空间中一组点的凸包。以下是如何使用Python实现这一过程：

首先，我们需要导入必要的库：

import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull

然后定义一个简单的点集（这里假设为二维坐标）：

points = [(1, 1), (3, 1), (3, 3), (1, 3)]

接着，我们调用`ConvexHull`类计算凸包：

hull = ConvexHull(points)
vertices = hull.vertices

`vertices`变量现在存储了凸包的顶点索引，我们可以从原始点集中提取这些顶点来形成线段：

edges = [[points[vertex_i], points[vertex_j]] for vertex_i, vertex_j in zip(vertices, vertices[1:] + [vertices[0]])]

绘制凸包：

plt.plot([point[0] for point in points], [point[1] for point in points], 'o')
for edge in edges:
    plt.plot(*zip(edge))
plt.gca().set_aspect('equal', adjustable='box')  # 设置坐标轴比例相同
plt.show()

这段代码会生成一个图形，显示了点集及其最小凸包。