快速计算粒子接近在三维空间

Question

这似乎是一个简单的问题，但我认为我没有其他途径可以采取这个时候。省略太多不必要的细节，大致概念如下:

我有一个实体(比如粒子)的许多实例在一个包含的三维空间中。初始实例的数量可能从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
            }
        }
    }

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

谢谢你的帮助，DevenJ

Answer 1

这里需要说明的一点是，如果速度很重要，就不应该使用平方根来进行计算。更好的方法是将接近值平方并去掉平方根。

你还需要确保你没有重复计算。例如，考虑下面

的方法

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

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

Answer 2

您可以通过设置

来消除在循环中使用sqrt()的需要

proximity = proximity * proximity;

Answer 3

将您的实体存储在分区空间的数据结构中，将允许您消除不包含在包含您邻近区域的分区中的任何粒子。二叉空间划分、四叉树和八叉树在这方面很有用。

Answer 4

对于正值，如果a <= b，则a^2 <= b^2

平方根运算保留两个值之间的顺序。因此，只需在循环前将您的距离平方以匹配平方大小。