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

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;
           }
       }

Answer 1

我可以想到三个解决方案,每个解决方案都有不同的时间\空间权衡.

nxn数组

如果您有少量n个对象和距离函数D(n ₁,n ₂),则可以提前计算距离.

创建一个2D n X n数组.在数组[i,j]中存储D(n _i,n _j)的结果.

优点:

• 在初始计算之后,任何两个对象的答案在O(1)中给出.
• 简单

缺点:

• 大数据集效率低下
• 无法在运行中轻松添加新对象

记忆化

记住您的距离功能以记住之前的通话.

R-树

用于在诸如点和多面体的 2D\3D对象中存储对象的标准数据结构是R树.简而言之,您的对象被分组为附近项目的3D立方体.它提供了log(n)时间的有效插入和查找时间,并且阈值距离查找非常有效,尤其是当答案为负时.

引用维基百科的文章:

R树常见的实际用途可能是存储...典型地图由以下组成的多边形:街道,建筑物,湖泊轮廓,海岸线等,然后快速查找答案,例如"查找全部"距离我当前位置2公里范围内的博物馆","检索距离我所在位置2公里范围内的所有路段"

和:

数据结构的关键思想是对附近的对象进行分组,并在树的下一个更高级别用最小的边界矩形表示它们; R树中的"R"表示矩形.

您在大多数现代编程语言中都有R-Tree实现.