c++ - 快速计算 3 维空间中的粒子接近度

Question

这似乎是一个简单的问题，但我目前看不出有其他方法可以选择。没有太多不必要的细节，大致的概念如下:

我在包含的 3 维空间中有许多实体(想想粒子)实例。初始实例的数量可能从 10 到 1000 个不等，每个粒子都用它的标识号和它自己的 x、y 和 z 坐标进行初始化。粒子可能会随着时间移动，因此这里的目标是能够尽快检查是否有任何两个粒子彼此处于预设的接近距离内(在任何方向上)。我能想到的最简单但不幸的是不够优雅/缓慢的方法是嵌入 for 循环，如下所示:

    for(int i = 0; i < upper; i++)
    {
        for(int j = 0; j < upper; j++)
        {
            //If within proximity
            if(sqrt( ((entity1.x[i] - entity2.x[j])*(entity1.x[i] - entity2.x[j])) + ((entity1.y[i] - entity2.y[j])*(entity1.y[i] - entity2.y[j])) + ((entity1.z[i] - entity2.z[j])*(entity1.z[i] - entity2.z[j])) ) <= proximity )
            {
                //Perform function
            }
        }
    }

这是我代码中的实际循环。我在 3 Dimensions 中使用距离公式，查看所述距离是否小于预定义的接近度。如果他们在那个距离之内，那么我执行一个功能。目前我有什么都不做的功能，所以我可以只观察循环本身的时间，而不用担心里面的算法。我知道每个系统的时间不同，但我的系统至少是平均水平的上限，如果不是更好的话，这个循环大约需要 5 秒才能完成，并且上限设置为 100 个循环。有没有更快的算法来做到这一点？或者我在这个循环中做了一些非常低效的事情？我做得越快越好。

感谢帮助，德文杰

Answer 1

这里要提到的一件事是，如果速度很重要，您不应该使用平方根来进行计算。更好的方法是对接近值求平方并去掉平方根。

您还需要确保不重复计算。例如，考虑下面的方法

for(int i = 0; i < upper; i++)
{
    for(int j = 0; j < upper; j++)
    {
        if(i < j)
        {
            //do stuff
        }
    }
}

但是二叉八叉树是更好的解决方案，尽管它们需要更多的算法知识。