algorithm - 使用大规模并行算法在 3D 点数据中查找聚类

Question

我在 3D 空间 (x,y,z) 中有大量点，表示为 3 个浮点结构的数组。我还可以使用具有 CUDA 功能的强大显卡。我想要以下内容:

将数组中的点划分为簇，使得簇中的每个点与簇中的至少一个其他点之间的最大欧氏距离为 X。

二维示例:

这样做的“强力”方法当然是计算每个点与其他每个点之间的距离，看看是否有任何距离低于阈值 X，如果是，则将这些点标记为属于同一个集群。这是一个 O(n²) 算法。

这当然可以在 CUDA 中使用 n² 线程并行完成，但是有没有更好的方法？

Answer 1

通过使用binning 可以将算法减少到 O(n):

• 施加一个间隔为X的3D网格，这是一个3D格子(格子的每个单元格都是一个立方体)；
• 将空间中的每个点分配给相应的bin(几何上包含该点的bin)；
• 每次您需要评估与一个点的距离时，您只需使用该点本身的 bin 中的点和 26 个相邻 bin 中的点 (3x3x3 = 27)

其他 bin 中的点比 X 更远，因此您根本不需要评估距离。

这样，假设点中的密度恒定，您只需计算恒定数量的点对/点总数的距离。

将点分配给 bins 也是 O(n)。

如果点分布不均匀，则 bin 可以更小(并且您必须考虑超过 26 个邻居来评估距离)并最终变得稀疏。

这是用于分子动力学、光线追踪、网格划分等的典型技巧，但是我从分子动力学模拟中知道了分箱这个术语:名称可以更改(link-cell、kd-trees 也使用相同的原理，即使更加明确)，算法保持不变!

而且，好消息是，该算法非常适合并行实现。

引用:

https://en.wikipedia.org/wiki/Cell_lists