c++ - KD 树仍然是用于移动物体的最佳算法之一吗？

Question

假设您有一个对象列表，每个对象都需要计算距离它最近的对象以进行拍摄。这个对象有一个 x 和一个 y 值。物体也在移动。 kd树还有用吗？我不确定，因为如果物体在移动，你必须继续创建这个 kd 树。

我可以使用什么算法以获得最佳速度(最好使用 Big O)

Answer 1

k-d 树是一种非常非常有效的数据结构，可以用坐标确定欧几里得空间中最近的邻居。
k-d 树生成(它在 O(n log²n) 中生成)需要大量对象才能产生问题，因此几乎是线性时间，搜索所有最近的邻居需要 O(n log n)，也很便宜)。所以你可能也会对程序的其余部分有问题。

从您的问题来看，似乎您需要跟踪的只是欧几里得空间中多个点的最近邻居。我建议您从 k-d 树的普通实现开始，并且在极端和不太可能的情况下，k-d 树的生成成本太高根据时间或内存，尝试找到一种方法来跟踪每个元素的多个邻居，并仅在需要时更新列表。
但老实说，我过去一直在使用 k-d 树，我记得尽管数据集非常大(二维空间中有数千万个点)，但生成和搜索速度足够快，以至于可以忽略不计其他操作。