Python计算XYZ格式点云点间最小距离 适配DBSCAN参数需求

适用于DBSCAN聚类前的eps参数参考场景，点云数据格式为shape=(N, 3)的Numpy数组，每行对应一个点的x、y、z坐标。

方法1：Numpy广播实现（适合点数<10000的小数据集） #

直接利用Numpy的广播机制计算所有点对的欧氏距离，再取最小值：

import numpy as np

def calc_min_distance_numpy(point_cloud: np.ndarray) -> float:
    # 扩展维度做广播计算坐标差
    diff = point_cloud[:, np.newaxis, :] - point_cloud[np.newaxis, :, :]
    # 计算欧氏距离
    dist_matrix = np.sqrt(np.sum(diff ** 2, axis=2))
    # 排除自身距离（对角线为0），取最小值
    np.fill_diagonal(dist_matrix, np.inf)
    return np.min(dist_matrix)

注意：该方法时间复杂度为O(N²)，点数过大会出现内存不足、计算缓慢的问题

方法2：Scipy优化实现（适合中等规模数据集） #

调用Scipy内置的pdist接口，底层做了计算优化，比手动实现效率高3~5倍：

import numpy as np
from scipy.spatial.distance import pdist

def calc_min_distance_scipy(point_cloud: np.ndarray) -> float:
    # 直接计算所有非重复点对的欧氏距离，返回一维数组
    all_dist = pdist(point_cloud, metric="euclidean")
    return np.min(all_dist)

方法3：KD树优化实现（适合点数>100000的大规模点云） #

无需计算所有点对距离，通过KD树为每个点找最近邻，再取所有最近邻距离的最小值，时间复杂度可降至O(NlogN)：

import numpy as np
from sklearn.neighbors import NearestNeighbors

def calc_min_distance_kdtree(point_cloud: np.ndarray) -> float:
    # 初始化最近邻查找器，找每个点的第2近邻（第1近邻是自身）
    nbrs = NearestNeighbors(n_neighbors=2, algorithm="kd_tree").fit(point_cloud)
    distances, _ = nbrs.kneighbors(point_cloud)
    # 取所有点的最近邻距离的最小值
    return np.min(distances[:, 1])

注意事项 #

• 计算得到的最小距离仅作为DBSCAN的eps参数的下界参考，实际使用时可结合业务需要的聚类粒度适当调大该值，避免所有点被识别为噪声点。
• 如果点云存在大量重复点，计算出的最小距离为0，建议先做去重预处理再计算。

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