3

アイテムが 3 次元空間で別のアイテムに十分に近いかどうかを調べる STL マップを作成したいと考えています。これまでのところ、私の "less-than-functor" は非常にうまく機能しており、次のリンクに貼り付けられています。

現在、この問題は「最近傍」問題ではありません。むしろ「少し離れたところに隣人がいるか」という問題です。

私の例は、単一の次元を示しています。わかりやすくするために、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 ツリーは非常に一般的であり、実装がそれほど難しくありません。R-treeも関連していますが、私はそれを実装しておらず、その難しさについてコメントすることはできません。

于 2012-03-26T17:41:50.090 に答える