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

Question

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

数据样本：

Answer 1

首先，您可以编写一个函数来计算表示为 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))

最后，你只需要从你的文件中获取点，我假设它看起来像这样：

云.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))

Answer 2

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

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

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

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

Answer 3

附加到罗斯坦的回答，回答马克西姆斯在评论中的问题。

import numpy as np
from scipy.spatial.distance import pdist
    
min_distance = lambda cloud: np.min(pdist(cloud))
print(min_distance(cloud))

lambda 函数返回一个函数。您需要用数据调用它才能获得结果。

（我没有足够的声誉点来发表评论，所以添加此作为答案。）

对于大量点

查找到最近邻居的距离并返回最小距离。

import numpy as np
from scipy.spatial import cKDTree

# assume data stored as [x, y, z] numpy array called 'cloud'

tree = cKDTree(cloud) 
nn1_dist = tree.query(cloud, k=2, workers=-1)[0][:,1]
nn1_dist = nn1_dist[nn1_dist != 0]  # remove 0s
np.min(nn1_dist)