有没有一种有效的方法来确定距离?
这个问题更多的是关于算法和功能的正确使用,而不是实际的代码。有没有一种有效的方法来确定距离?
在我的代码中,我使用map来模拟盒子。地图元素由作为键的vector<int>
和作为值的set<shared_ptr<foo> >
组成。
我做一个嵌套循环去了所有的箱子:
mit1 = boxes.begin(); //mit1 is an appropriate iterator
int edge = 10;//represnd periodic boundary conditions
while (mit1 != boxes.end()){
vector<t> = mit1->first;
mit2 = mit1++;
while (mit2 != boxes.end()){
vector<int> u = (mit2++)->first;
bool good = true;
for (int i = 0; i < 3 && good; i++){
u[i] = (int)fabs(u[i] - t[i]);
good = u[i] == 0 || u[i] == 1 || u[i] == edge;
}
if (!good) continue;
}
}
我所关注的是整个循环嵌套还有for
循环。 你认为用函数来计算所有相邻的盒子会更有效吗?你知道任何更好的方法来做循环测试吗?
与每次碰撞检测相同的建议:使用一些算法或数据结构,允许您根据空间距离对环路的候选进行预过滤,并允许在O(n)中执行预过滤。想到四叉树或粗粒度的空间映射。
编辑:为了让整个想法更清楚一点,请考虑以下算法:在3D空间中有N个粒子,并且想要找出哪个粒子比距离D更近。您可以构建一个3D阵列,每个仓代表您的目标空间的立方体积,并且每个体积的大小必须至少为D.要查找所有可能比D更接近给定粒子X的粒子,请确定阵列单元格其中X是当前的Ax,并选择Ax和周围所有单元格中的所有粒子。你只需要检查这个小子集的冲突。
当使用M个阵列单元时,整个距离检查的平均计算复杂度现在是O(N * N/M)而不是O(N^2),然而以O(M^2 ) 空间。
如果您的目标空间不受限制,请使用四叉树(2D)或八叉树(3D)。
取决于你的程序在做...
但它是可以计算的距离,当一个框移动。 然后它优化一些如果不是所有的盒子都在移动。
这是一般碰撞/心智问题的简化版本。当你有一堆物体时,这些问题会变得特别讨厌,每个物体都被许多多边形面所描述。没有一个适合所有这些问题的解决方案。有很多启发式方法可以帮助解决这个问题。其中几个:
使用边界球以及边界框。一对球体之间的距离比一对球体之间的距离更容易计算,并且一对球体之间的距离不会超过一对边界框之间的距离。这可以让您快速排除大量计算。
使用对象的层次结构。如果对象A,B,C和D总是彼此靠近,创建一个包含A,B,C和D的元对象通常很有用。如果您可以排除将此元对象视为候选对象,只是排除考虑任何内部对象作为候选人。
如果物体移动缓慢,下一步最近的邻居通常是当前步骤中最近的邻居。从第一次猜测开始,然后搜索其他附近的物体,然后再向外走。最终(通常早于晚)你将排除所有剩余的物体。
肯定有一个更好的办法! – Arunmu
你想要计算什么?你确定你没有在mit2和u之间混淆(或换句话说 - 你在第二次没有无限循环)? – Ofir
谢谢,我已经改变了循环,现在应该没问题了......我想消除所有情况,其中两个盒子都是这样,因此盒子内的粒子没有机会互动。箱子的大小固定为这样的距离,但我剩下箱子的距离计算 – Yotam