如何减少Pandas DataFrame生成的ConvexHull顶点数量？

当然可以用scipy.spatial.KDTree来实现这个需求，它能高效查找凸包顶点中距离过近的点，帮你快速精简顶点数量。

实现思路 #

凸包的顶点是按顺序排列的闭合多边形顶点，我们可以利用KDTree的高效邻近查询能力，设定一个距离阈值，移除那些距离小于阈值的冗余顶点，同时需要注意处理首尾顶点的相邻关系（因为凸包是闭合的，首尾顶点也是相邻的）。

完整代码示例 #

import pandas as pd
import numpy as np
from scipy.spatial import ConvexHull, convex_hull_plot_2d, KDTree
import matplotlib.pyplot as plt

# 生成随机数据集
df = pd.DataFrame(np.random.randn(1000, 2), columns=['col1', 'col2'])
# 计算原始凸包
hull = ConvexHull(df[['col1', 'col2']])
hull_vertices = df.iloc[hull.vertices].values  # 凸包顶点坐标数组
hull_indices = hull.vertices  # 原始顶点在数据集中的索引

# 设定距离阈值（根据数据尺度调整）
distance_threshold = 0.3

# 构建KDTree用于邻近查询
tree = KDTree(hull_vertices)

# 初始化保留标记数组
keep = np.ones(len(hull_vertices), dtype=bool)

# 遍历顶点，标记冗余顶点
for i in range(len(hull_vertices)):
    if not keep[i]:
        continue
    # 查询所有距离当前顶点小于阈值的点
    distances, indices = tree.query(hull_vertices[i], k=len(hull_vertices), distance_upper_bound=distance_threshold)
    # 标记除自身外的邻近点为移除
    for idx in indices:
        if idx != i and idx < len(hull_vertices) and keep[idx]:
            keep[idx] = False

# 检查首尾顶点的相邻距离（凸包闭合特性）
first_idx, last_idx = 0, len(hull_vertices) - 1
if np.linalg.norm(hull_vertices[first_idx] - hull_vertices[last_idx]) < distance_threshold:
    keep[last_idx] = False  # 移除最后一个顶点，也可选择移除第一个

# 获取精简后的结果
pruned_indices = hull_indices[keep]
pruned_vertices = df.iloc[pruned_indices]

# 输出统计信息
print(f"原始凸包顶点数量：{len(hull_indices)}")
print(f"精简后凸包顶点数量：{len(pruned_indices)}")
print("\n精简后的顶点：")
print(pruned_vertices)

# 绘制对比图
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))
# 原始凸包
convex_hull_plot_2d(hull, ax=ax1)
ax1.set_title("原始凸包")
# 精简后凸包
ax2.scatter(df['col1'], df['col2'], s=5, alpha=0.5)
ax2.plot(
    pruned_vertices['col1'].tolist() + [pruned_vertices['col1'].iloc[0]],
    pruned_vertices['col2'].tolist() + [pruned_vertices['col2'].iloc[0]],
    'r-', lw=2
)
ax2.set_title("精简后凸包")
plt.tight_layout()
plt.show()

关键说明 #

• 距离阈值调整：distance_threshold需要根据你的数据集尺度灵活设置，值越小保留的顶点越多，值越大精简效果越明显。
• KDTree查询优化：使用distance_upper_bound参数限定搜索距离，避免不必要的计算，提升查询效率。
• 闭合多边形处理：额外检查首尾顶点的距离，确保凸包的闭合特性不会导致冗余顶点被遗漏。

内容的提问来源于stack exchange，提问作者James