检测物体间距离的最快方法？

Question

我有一些未知数量的3D空间对象，我想知道检测两个或多个对象之间距离是否小于阈值的最快方法是什么。 我认为这是一个n！问题，但我希望有更好的解决方法。

我尝试了以下伪代码，并需要您的意见。

 for (int y=0; y<blobList.size();y++){
       for (int x =1; x<blobList.size();x++)
       {
           CvPoint *blob_a = new CvPoint();
           CvPoint *blob_b = new CvPoint();
           blob_a->x = blobList[x].second->maxx;
           blob_a->y = blobList[x].second->maxy;
           blob_b->x = blobList[y].second->maxx;
           blob_b->y = blobList[y].second->maxy;

           double dist = distance(blob_a,blob_b);
           cout<< " distance between blob "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           cout<<dist<<endl;

           if( dist<ParamMgr.fDistance)
           {

           cout<< " Collision between "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           }
           else {
               cout<< " "<<endl;
           }
       }

- Ahmed Saleh

---

用N^2的比较，你就完成了。 - CapelliC

对于每个物体，遍历所有其他物体并计算它们之间的距离，这需要进行N*N-1次计算。 - CapelliC

如何检测其他对象？ - andre_lamothe

@Ahmed Saleh - 你有办法计算任意两个给定对象之间的距离吗？ - Adam Matan

@AhmedSaleg 请看下面我更新的答案。 - Adam Matan

Answer 1

我能想到三种解决方案，每种都有不同的时间和空间权衡。

n x n 数组

如果您有一小组包含n个对象和一个距离函数D(n₁, n₂)，可以预先计算距离。

创建一个二维n X n数组。在array[i,j]中存储D(n_i, n_j)的结果。

优点：

• 初始计算后，任何两个对象的答案都以O(1)给出。
• 简单易懂

缺点：

• 大数据集效率低
• 无法轻松添加新对象

Memoization

记忆化距离函数以记住以前的调用。

R-Tree

用于存储二维/三维对象（如点和多面体）的标准数据结构是R 树。简而言之，将您的对象分组为附近项目的3D立方体。它提供了log(n)时间的高效插入和查找时间，且阈值距离查找非常高效，特别是当答案为负数时。

引用Wikipedia文章：

在R树的常见现实世界应用可能是存储...典型地制作地图的多边形：街道、建筑物、湖泊轮廓线、海岸线等，然后快速查询如“查找所有博物馆距离我的当前位置2公里以内”，“检索到我位置以内2公里的所有路段”等问题的答案

并且：

数据结构的关键思想是将附近的对象分组，并在树的下一个更高级别中使用它们的最小边界矩形来表示； "R"代表矩形。

大多数现代编程语言都有R-Tree实现。

- Adam Matan

Answer 2

如果3D空间有限，我们可以将空间分成小立方体。每个边的长度是值阈值。我们假设它为d。然后，我们只需将对象放入立方体中。挑选包含对象的立方体B(x_i, y_j, z_k)，然后我们只需检查相邻的立方体。对于每个立方体，最多会有27个立方体，包括自身。我们可以忽略其他立方体，因为它们肯定距离大于一个阈值。

这种解决方案仅在节点稀疏的情况下有效。如果所有节点都在空间3d * 3d * 3d中，则算法将处于最坏情况。您可能无法过滤任何节点。

- Edward Zhu

---

有26个相邻的立方体。你还需要检查当前选择的立方体中的所有对象。否则，这是一个好的简单解决方案。 - sl0815

Answer 3

与寻找一种非“蛮力”算法来移除一组矩形的相交区域的已接受解决方案类似，您可以在x、y或z维度中对对象进行排序，并对于每个对象，只需通过阈值（可能缩放以考虑额外维度）向前搜索排序列表。这将至少为您提供所有明显不接近的对象。对于剩余的对象，您可以检查它们的距离并做出决策，或者更好的方法是将其他维度分成若干个相等大小的部分，并将每个对象分类为其j维值在该部分中。您可以更快地得出是否超出阈值的决定。总体而言，对于给定的对象，此方法将减少实际距离计算的数量，并且问题将高效地扩展。

- martino