algorithm - 对大量相似向量进行分组

Question

我有一个约 200,000 个三角形的 3d 网格。

为了在模型上找到所有平坦(或接近足够平坦)的表面，我想我可以尝试按三角形的法向量对三角形进行分组(给我面朝相同方向的三角形)，然后我可以在这些较小的集合中搜索那些位置相似或相连。

我想不出一个好的方法来实际做到这一点，同时又能保持相对快速。我提出了需要 n² 的解决方案，但没有一个比这更优雅和更快。

我有顶点信息和三角形信息(顶点、中心和法线)。

如有任何建议，我们将不胜感激。

Answer 1

可能是我误解了这个问题，所以我要说明我认为你需要做的事情:“给定一组向量，将平行向量组合在一起”。

您可以使用 HashMap 来解决此问题。我假设您以以下形式存储法线向量:

一个 + b + c = 0

你只需要编写一个将向量转换为整数的函数，例如，如果我知道 0 <= a, b, c <= 1000，那么我可以使用 F(a, b, c) = a + 1000b + 1000000c 这保证了每个唯一向量的唯一整数。在此之后，只需创建一个将一些整数映射到列表并将所有并行向量存储在同一个列表中的 HashMap 。