给定二维空间中的大量点（float64）...
有没有办法使用 OpenGL 或 DirectX 的功能来确定最近的邻居？
我已经实现了一个 kd-tree，它仍然不够快。
问问题
195 次
1 回答
3
kd-tree应该可以正常工作。但这里有一些提示。
我为一百万点数据集实现了一次 kd-tree。这是我从中学到的：
您是否尝试分析您的代码？您可能会发现可以进行一些简单的优化，例如需要强制内联的常用辅助函数。
您是否真的测试过您的代码以验证它是否正在剔除易于识别为“太远”的分区的树枝。如果您不小心，您很容易遇到一个错误，该错误会在太远的点上进行不必要的距离计算。
最简单的事情：在比较点之间的线性距离时，您不需要采用 (x2-x1)*(y2-y1) 的 SQRT。
在我的代码中花费的大部分时间只是从原始数据集构建树，包括每次迭代中的多个完整排序，以决定哪个轴是最好的分区。一个更简单的算法是在每个树分支的 x 轴和 y 轴上的分区之间交替，并缓存每个轴的排序顺序。它可能无法构建最优化的搜索树，但总体节省可能是巨大的。
于 2013-03-15T09:28:12.467 回答