algorithm - 是否需要在循环的每次迭代中重新创建 Barnes Hut Tree

Question

我正在编写一个应用程序，需要在数百个不断运动的粒子之间执行 n 体模拟。应用程序具有实时要求，因此执行仿真的算法需要快速。

我对此事进行了大量研究，得出的结论是 Barnes Hut 算法最适合我的需求，它似乎对大型粒子集非常有效。

http://arborjs.org/docs/barnes-hut对算法的工作原理给出了非常清楚的解释，但正如标题所暗示的那样，我想知道是否需要为每次迭代重新创建树，考虑到模拟中使用的粒子总是动态运动的。如果确实需要重新创建树，如何以最有效(在处理能力和内存方面)的方式进行。

Answer 1

通常对于基于移动的索引，移动发生后索引不会“更新”，您必须重建整个索引。

Barnes Hut Tree 是一样的，必须重建。这是一个 example我在网上找到了流程的代码大纲。

这是为 KD 树之类的构建优化付出如此多努力的原因之一，我相信 Barnes Hut 也是如此。另外，我确信有关于动态更新的研究，但大多数时候这些实现比简单的重建要难得多。