有没有一种有效的方法来确定距离？

这个问题更多的是关于算法和功能的正确使用，而不是实际的代码。有没有一种有效的方法来确定距离？

在我的代码中，我使用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循环。你认为用函数来计算所有相邻的盒子会更有效吗？你知道任何更好的方法来做循环测试吗？

来源

2011-09-18 Yotam

肯定有一个更好的办法！ – Arunmu

你想要计算什么？你确定你没有在mit2和u之间混淆（或换句话说 - 你在第二次没有无限循环）？ – Ofir

谢谢，我已经改变了循环，现在应该没问题了......我想消除所有情况，其中两个盒子都是这样，因此盒子内的粒子没有机会互动。箱子的大小固定为这样的距离，但我剩下箱子的距离计算 – Yotam

与每次碰撞检测相同的建议：使用一些算法或数据结构，允许您根据空间距离对环路的候选进行预过滤，并允许在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）。

来源

2011-09-18 13:20:01 thiton

这就是箱子在那里的原因。每个盒子都包含粒子，盒子是过滤器。但是，我仍然想找到一种既易于理解又高效的方法... – Yotam

阅读您的编辑......这正是我正在做的。唯一的区别是，音量正在变化，我不能简单地创建一个表格，在那里我写下所有的音符对。此外，大部分数量都是空的，并且它不会有效地覆盖所有的盒子... – Yotam

a）四/八叉树对于这样的空卷是非常好的。 b）与比较所有物体之间的距离相比，检查26个空箱子是非常便宜的。 c）再次，随着音量的变化，使用八叉树来达到同样的效果。 – thiton

取决于你的程序在做...

但它是可以计算的距离，当一个框移动。然后它优化一些如果不是所有的盒子都在移动。

来源

2011-09-18 13:15:50 Nir

这是一般碰撞/心智问题的简化版本。当你有一堆物体时，这些问题会变得特别讨厌，每个物体都被许多多边形面所描述。没有一个适合所有这些问题的解决方案。有很多启发式方法可以帮助解决这个问题。其中几个：

使用边界球以及边界框。一对球体之间的距离比一对球体之间的距离更容易计算，并且一对球体之间的距离不会超过一对边界框之间的距离。这可以让您快速排除大量计算。
使用对象的层次结构。如果对象A，B，C和D总是彼此靠近，创建一个包含A，B，C和D的元对象通常很有用。如果您可以排除将此元对象视为候选对象，只是排除考虑任何内部对象作为候选人。
如果物体移动缓慢，下一步最近的邻居通常是当前步骤中最近的邻居。从第一次猜测开始，然后搜索其他附近的物体，然后再向外走。最终（通常早于晚）你将排除所有剩余的物体。

来源

2011-09-18 14:25:40

有没有一种有效的方法来确定距离？

回答

相关问题