1

这似乎是一个简单的问题，但我目前看不到其他路线。没有太多不必要的细节，大致的概念如下：

我在包含的 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 维中的距离公式，查看所述距离是否小于预定义的接近度。如果它们在那个距离内，那么我执行一个功能。目前我有什么都不做的功能，所以我可以只观察循环本身的时间，而不用担心里面的算法。我知道每个系统的时间各不相同，但我的系统至少是平均上限，如果不是更好的话，这个循环大约需要 5 秒才能完成，而上限设置为 100 个循环。有没有更快的算法来做到这一点？还是我在这个循环中做了一些非常低效的事情？我能做的越快越好。

感谢您的帮助，DevenJ

4

4 回答 4

3

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

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

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

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

于 2013-04-25T03:16:31.677 回答
2

您可以通过设置消除在循环内使用 sqrt() 的需要

proximity = proximity * proximity;

在循环之前。

于 2013-04-25T03:13:24.823 回答
1

将您的实体存储在对您的空间进行分区的数据结构中将允许您消除任何未包含在包含您的邻近区域的分区中的粒子。二进制空间分区、四叉树和八叉树对此很有用。

于 2013-04-25T03:14:11.887 回答
1

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

平方根运算保留两个值之间的顺序。因此，只需在循环之前平方您的接近度以匹配平方幅度。

于 2013-04-25T03:15:39.600 回答