c++ - 图形硬件上的最近邻搜索

Question

给定二维空间中的大量点 (float64)...

有没有办法使用 OpenGL 或 DirectX 的功能来确定最近的邻居？

我已经实现了一个 kd-tree，它仍然不够快。

Answer 1

kd-tree 应该工作得很好。但这里有一些提示。

我为百万点数据集实现了一次 kd-tree。这是我从中学到的东西:

您是否尝试分析您的代码？您可能会发现可以轻松进行优化，例如需要强制内联的常用辅助函数。

您是否实际测试了您的代码以验证它是否正在为那些很容易被识别为“距离太远”的分区剔除 Twig 。如果您不小心，很容易出现错误，对太远的点进行不必要的距离计算。

最简单的事情:在比较点之间的线性距离时，您不需要采用 (x2-x1)*(y2-y1) 的 SQRT。

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