algorithm - 在网格中查找彼此之间一定距离内的顶点

Question

我有一个由一定数量的顶点组成的 3D 网格。

我知道有些顶点彼此非常接近。我想找到这些组，以便我可以将它们归一化。

我可以做一个 KD 并做基本的 NNS，但如果我没有引用点，那扩展性就不太好。

我想找到与所有点相关的这些组。

在我的搜索中，我还发现了 k-means，但我似乎无法围绕它的科学描述来确定它是否真的是我需要的。

我一般不精通空间算法。例如，对于这种情况，我知道在哪里可以应用它们，但我缺乏实际的知识，甚至无法拥有正确的关键字。

那么，是的，什么样的算法适用于此类任务？

Answer 1

可能可行的简单想法:

1. 为网格中的每个顶点计算一个稍大的边界体积。例如，如果您使用球体，请为其使用较小的半径，例如，半径可以等于网格最小边的长度。

2. 计算每个顶点的边界体积的交集。为此使用碰撞检测算法，例如 I-Collide。使用不相交集数据结构对碰撞点进行分组。

3. 合并位于同一集合中的所有点。

您可以通过更改边界体积的大小来微调算法。您也可以将此算法用作 k-means 算法或其他可靠聚类技术的起点。