Python 中点云 (XYZ) 点之间的最小距离

Question

我正在尝试运行点云数据集上的基于密度的空间聚类 (DBSCAN)，该数据集是一系列具有 x、y、z 坐标的点。最小距离的参数之一。如何在 space 和 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))

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

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

Answer 2

这是对 Rostan 回答的补充。 His/her 方法有效，但它可以改进（主要是速度，取决于您拥有的数据量，这可能真的值得）。

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

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

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

Python 中点云 (XYZ) 点之间的最小距离

Min distance between Point Cloud (XYZ) Points in Python

python

distance

point-clouds

最终代码

编辑