如何查找3D图形中的连通点？基于距离阈值的三维点聚类咨询

你需要的是基于距离阈值的密度聚类，目前已经有非常成熟的算法可以直接满足需求，完全不需要自己实现暴力匹配逻辑：

首选方案：直接使用DBSCAN算法 #

DBSCAN是基于密度的聚类算法，核心逻辑就是将距离小于阈值的相邻点划入同一簇，完全匹配你的需求：

• 算法的eps参数就是你需要的最大距离阈值，直接设为1即可实现“两点欧氏距离小于1就归为同一聚类”的规则
• 不需要预先指定聚类数量，也不需要额外的调参，1000多组三维点的计算耗时可以忽略不计
• Python中可以直接调用scikit-learn库的DBSCAN实现，示例代码如下：

import numpy as np
from sklearn.cluster import DBSCAN

# 你的三维坐标数据，需转换为shape为(n, 3)的numpy数组，n为数据量
points = np.array([
    [x1, y1, z1],
    [x2, y2, z2],
    # 其余坐标点
])

# 初始化聚类器，欧氏距离阈值设为1，min_samples设为1表示单个点也可作为独立簇
# 如果需要过滤孤立噪声点，可将min_samples改为2，单个孤立点会被标记为-1
clustering = DBSCAN(eps=1, metric="euclidean", min_samples=1).fit(points)

# 输出结果：和points顺序一一对应的聚类标签，相同标签属于同一簇
cluster_labels = clustering.labels_

如果你需要自己实现的优化思路 #

如果你有自定义逻辑需要自己实现算法，可以用以下两个优化点解决暴力匹配效率低的问题：

• 空间分桶优化：按阈值1为边长划分三维网格，每个点先映射到对应的网格中，计算距离时只需要匹配当前点所在网格以及周围26个相邻网格里的点，不需要和全局所有点计算距离，可减少99%以上的距离计算量
• 并查集（Union-Find）管理簇关系：遍历所有符合要求的点对的时候，只要两点距离小于1，就用并查集把两个点的所属簇合并，最后遍历所有点就能得到每个点的聚类标签，比暴力维护簇列表的效率高很多

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