图形硬件上的最近邻搜索

Question

3

给定一个二维空间中的大量点（float64），有没有使用OpenGL或DirectX的功能来确定最近的邻居？

我已经实现了kd树，但速度仍然不够快。

- user1983276

你已经对现有解决方案与最先进的非GPU解决方案进行基准测试了吗？（例如http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN ?）另外，速度慢多少？一个数量级？几个数量级？ - Andrew Walker

没有，我还没有与FLANN进行比较，但我会在周一第一时间这样做。感谢您的建议。是的，慢了大约100倍。 - user1983276

1

https://dev59.com/GlnUa4cB1Zd3GeqPZlt- - user149100

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- selbie · Accepted Answer

kd-tree可以很好地解决问题。但是以下是一些提示。

我曾经为一个包含一百万个点的数据集实现过kd-tree。以下是我的经验教训：

您尝试过对代码进行剖析吗？您可能会发现有易于优化的常见帮助函数需要被强制内联。

您是否真正测试了您的代码以验证它是否消除了易于识别为“太远”的分区的树枝？如果不小心，您可能会有一个错误，会在距离太远的点上进行不必要的距离计算。

最简单的事情：在比较点之间的线性距离时，您不需要对(x2-x1)*(y2-y1)进行平方根运算。

我的代码中大部分时间都花费在从原始数据集构建树上，包括在每次迭代中进行多次完整排序，以决定最佳的分区轴。更简单的算法是仅在x轴和y轴之间交替分区，并缓存每个轴的排序顺序。它可能无法构建最优的搜索树，但总体节省可以是巨大的。