Python中点云（XYZ）点之间的最小距离

Question

我试图在点云数据集上运行基于密度的空间聚类（DBSCAN），该数据集是一系列具有x、y、z坐标的点。最小距离中的一个参数。在Python中，如何在空间中找到点与另一点之间的最小距离？非常感谢

数据样本：

Answer 1

这是对罗斯坦回答的补充。他/她的方法可行，但可以改进（主要是速度，取决于你拥有的数据量，它可能真的值得）

通过谷歌搜索“点的最小距离”，我发现了以下文章：

https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/

那里的算法应该适合你。本文中还提供了Python代码示例，这应该会有所帮助

Answer 2

首先，您可以编写一个函数来计算表示为numpy数组的两点之间的欧几里德距离：

import numpy as np

distance = lambda p1, p2: np.sqrt(np.sum((p1 - p2) ** 2, axis=0))

我想不出比天真的O（n²）更好的方法来找到最小距离：

import itertools

def min_distance(cloud):
  pairs = itertools.combinations(cloud, 2)
  return np.min(map(lambda pair: distance(*pair), pairs))

最后，您只需要从您的文件中获取点，我假设它如下所示：

cloud.csv

x, y, z
1.2, 3.4, 2.55
2.77, 7.34, 23.4
5.66, 64.3, 4.33

def get_points(filename):
  with open(filename, 'r') as file:
    rows = np.genfromtxt(file, delimiter=',', skip_header=True)
  return rows

最终代码

import itertools
import numpy as np

distance = lambda p1, p2: np.sqrt(np.sum((p1 - p2) ** 2, axis=0))


def min_distance(cloud):
  pairs = itertools.combinations(cloud, 2)
  return np.min(map(lambda pair: distance(*pair), pairs))


def get_points(filename):
  with open(filename, 'r') as file:
    rows = np.genfromtxt(file, delimiter=',', skip_header=True)
  return rows


filename = 'cloud.csv'
cloud = get_points(filename)
min_dist = min_distance(cloud)

print(min_dist)

输出

21.277006368378046

编辑

正如Amiga500所指出的，可以使用scipy.spatial.distance。然后我们可以将min_distance重写如下：

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

min_distance = lambda cloud: np.min(pdist(cloud))