1

So I'm working on simulating a large number of n-dimensional particles, and I need to know the distance between every pair of points. Allowing for some error, and given the distance isn't relevant at all if exceeds some threshold, are there any good ways to accomplish this? I'm pretty sure if I want dist(A,C) and already know dist(A,B) and dist(B,C) I can bound it by [dist(A,B)-dist(B,C) , dist(A,B)+dist(B,C)], and then store the results in a sorted array, but I'd like to not reinvent the wheel if there's something better.

I don't think the number of dimensions should greatly affect the logic, but maybe for some solutions it will. Thanks in advance.

4

2 回答 2

2

如果问题只是关于计算所有对之间的距离，那么这将是一个O(n^2)没有任何机会找到更好解决方案的问题。但是，您是说如果距离大于某个阈值D，那么您对它不感兴趣。这为更好的算法打开了机会。

例如，在二维情况下，您可以使用扫描线技术。按字典顺序对您的点进行排序，首先y按x. 然后用一条宽度为 的条纹从下到上扫过飞机D。当条带在平面上移动时，新点将通过其顶部边缘进入条带并通过其底部边缘退出。活动点（即当前在条带内的点）应保存在一些按其x坐标排序的可增量修改的线性数据结构中。

现在，每次新点进入条带时，您都必须检查左侧和右侧不超过D（沿x轴测量）的当前活动点。就这样。

该算法的目的（因为它通常是扫描线方法的情况）是将实际复杂度推离O(n^2)和推向O(m)，这里m是我们实际感兴趣的交互次数。当然，最坏情况下的性能将是O(n^2).

以上适用于二维情况。对于 n 维情况，我会说使用不同的技术会更好。某种空间分区在这里应该可以很好地工作，即利用这样一个事实，即如果已知分区之间的距离大于D，那么没有理由考虑这些分区中的特定点相互对抗。

于 2012-11-03T18:14:06.907 回答
0

如果超出某个阈值的距离不相关，并且该阈值不太大，则有一些常用技术可以提高效率：使用空间分区数据结构限制对相邻点的搜索。可能的选项是：

  • 装箱。
  • 树：四叉树（2d），kd-trees。
  • 使用空间散列进行分箱。

此外，由于从 A 点到 B 点的距离与从 B 点到 A 点的距离相同，因此该距离应该只计算一次。因此，您应该使用以下循环：

for point i from 0 to n-1:
     for point j from i+1 to n:
        distance(point i, point j)

结合这两种技术对于 n 体模拟非常常见，例如，如果粒子足够接近，粒子就会相互影响。以下是 2d 中的一些有趣示例：http: //forum.openframeworks.cc/index.php?topic =2860.0

这是对分箱（和散列）的解释： http ://www.cs.cornell.edu/~bindel/class/cs5220-f11/notes/spatial.pdf

于 2012-11-03T17:59:28.817 回答