3

我想创建一个 STL 映射来查找一个项目是否足够接近 3 维空间中的另一个项目。到目前为止，我的“小于函子”运行良好，粘贴到以下链接。

现在这个问题还不是“最近邻”问题。相反，这是一个“在一定距离内是否有邻居”的问题。

我的示例仅显示一个维度。为了清楚起见，我跳过了 Y/Z 尺寸。

到目前为止我的尝试：

class ApproximateLessFunctor {
 public:
  ApproximateLessFunctor( float fudgeFactor ) :
    mFudgeFactor( fudgeFactor ) {};

  bool operator()( float a, float b ) const {
    return (a < (b - mFudgeFactor) );
  }

  float mFudgeFactor;
};

typedef map<float, int, ApproximateLessFunctor> XAxisMap;

class XAxis {
 public:
  XAxisMap vMap;

  XAxis(ApproximateLessFunctor functor, float x, int v)
  : vMap( functor )
  {
    vMap.insert(make_pair(x, v));
  }
};

在极少数情况下，我的意思是——非常罕见——当位置重叠时，地图找不到匹配的条目。

仍然使用 STL 容器，我可以做些什么来更好地实现这一点？

4

1 回答 1

1

现在这个问题还不是“最近邻”问题。相反，这是一个“在一定距离内是否有邻居”的问题。

不过，后者的措辞很简单。找到最近的邻居，然后确定它是否足够近。考虑到任务可用的数据结构数量，这似乎是一条合理的路线。

也就是说，kd-tree非常常见，实现起来并不难。同样相关的是R-tree，尽管我没有实现它并且无法评论它的难度。

于 2012-03-26T17:41:50.090 回答