Python 计算凸包 (Convex Hull)
凸包是指包含所有给定点的最小凸多边形，以下是几种常用的 Python 实现方法：
使用 scipy.spatial.ConvexHull（推荐）
from scipy.spatial import ConvexHull
import numpy as np
import matplotlib.pyplot as plt
# 生成随机点
np.random.seed(42)
points = np.random.rand(30, 2)
# 计算凸包
hull = ConvexHull(points)
# 获取凸包顶点的索引
hull_indices = hull.vertices
# 获取凸包顶点坐标
hull_points = points[hull_indices]
# 可视化
plt.figure(figsize=(8, 8))
plt.scatter(points[:, 0], points[:, 1], c='blue', label='All Points')
# 绘制凸包边
for simplex in hull.simplices:
plt.plot(points[simplex, 0], points[simplex, 1], 'r-')
plt.plot(hull_points[:, 0], hull_points[:, 1], 'go-', label='Hull Vertices')
plt.legend()'Convex Hull using scipy')
plt.axis('equal')
plt.show()
# 凸包面积和周长
print(f"Convex Hull Area: {hull.volume}") # 2D中volume即为面积
print(f"Convex Hull Perimeter: {hull.area}") # 2D中area即为周长
使用 scipy.spatial.ConvexHull（简洁版）
from scipy.spatial import ConvexHull import numpy as np points = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0.5, 0.5]]) hull = ConvexHull(points) # 凸包顶点（按逆时针顺序排列） vertices = points[hull.vertices] print("Hull vertices:n", vertices) print("Area:", hull.volume) print("Perimeter:", hull.area)
使用 shapely
from shapely.geometry import MultiPoint
import matplotlib.pyplot as plt
import numpy as np
# 生成随机点
np.random.seed(42)
points = np.random.rand(30, 2)
# 创建 MultiPoint 并计算凸包
multi_point = MultiPoint(points)
hull = multi_point.convex_hull
# 提取凸包坐标
x, y = hull.exterior.xy
# 可视化
plt.figure(figsize=(8, 8))
plt.scatter(points[:, 0], points[:, 1], c='blue', label='All Points')
plt.plot(x, y, 'r-', label='Convex Hull')
plt.legend()'Convex Hull using shapely')
plt.axis('equal')
plt.show()
print(f"Convex Hull Area: {hull.area}")
print(f"Convex Hull Perimeter: {hull.length}")
手动实现 Graham Scan 算法
import numpy as np import matplotlib.pyplot as plt def cross(o, a, b): """计算向量OA和OB的叉积""" return (a[0] - o[0]) (b[1] - o[1]) - (a[1] - o[1]) (b[0] - o[0]) def convex_hull_graham(points): """Graham Scan 算法求凸包""" points = sorted(set(points)) if len(points) <= 1: return points # 构建下凸包 lower = [] for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # 构建上凸包 upper = [] for p in reversed(points): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) # 合并，去掉重复的端点 return lower[:-1] + upper[:-1] # 测试 np.random.seed(42) points = np.random.rand(30, 2) points_list = [tuple(p) for p in points] hull = convex_hull_graham(points_list) hull = np.array(hull) # 可视化 plt.figure(figsize=(8, 8)) plt.scatter(points[:, 0], points[:, 1], c='blue', label='All Points') # 闭合凸包 hull_closed = np.vstack([hull, hull[0]]) plt.plot(hull_closed[:, 0], hull_closed[:, 1], 'r-', label='Convex Hull') plt.legend()'Convex Hull using Graham Scan') plt.axis('equal') plt.show()
各方法对比
| 方法 | 优点 | 缺点 |
|---|---|---|
scipy.spatial.ConvexHull |
高效、稳定、返回面积/周长 | 需要安装 scipy |
shapely |
几何操作丰富、API 友好 | 需要安装 shapely |
Graham Scan |
无依赖、理解算法原理 | 代码较长、需自行处理面积/周长 |
注意事项
- 2D vs 3D：
scipy.spatial.ConvexHull支持 N 维，2D 中volume是面积，area是周长；3D 中volume是体积，area是表面积。 - 顶点顺序：
scipy返回的顶点索引按逆时针排列。 - 共线点：凸包算法通常只返回顶点,共线点不在顶点列表中。
- 性能：对于大规模点集，
scipy使用 Qhull 库，时间复杂度约为 O(n log n)。
推荐使用 scipy.spatial.ConvexHull，它是最成熟、高效的解决方案。
首发原创文章，作者：王坚，如若转载，请注明出处：https://idctop.com/article/476827.html
