graphics - 最近邻搜索

Question

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

谢谢

score 1 · Accepted Answer

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

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

score 0 · Accepted Answer

0

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

于 2012-12-12T07:06:24.727 回答

score 0 · Accepted Answer

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

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

3 回答 3