graphics - 最近邻搜索

Question

我想要一个最近邻搜索（NNS）问题的算法。该问题与计算几何领域有关。我搜索了很多，但我没有找到一个算法。我认为局部敏感哈希（LSH）算法会很好地解决这个问题，但不幸的是我没有找到解决这个问题的算法。正是我想要一篇文章来学习 LSH。谁能帮我？

谢谢

Answer 1

恕我直言，LSH 很难正确实施。

wiki上有关于 NNS 的精彩文章。当将两个三角形网格合并在一起时，我正在使用NNS 的kd-tree来解决最近邻问题，它工作得非常好而且非常快。它也不难实现（谷歌可能很容易找到一些实现）。

Answer 2

如果您正在寻找 C++ 库，可以查看这个CGAL 包。还有ANN 库。

Answer 3

您需要最近邻居还是近似最近邻居？在几个维度？

我还建议在 LSH 之前尝试 kd-tree 搜索。