Using an “approximate” STL map

Question

I would like to create an STL map to find whether an item is close enough to another item in 3 dimensional space. So far, my "less-than-functor" has worked quite well, pasted to the following link.

Now this problem isn't quite the "nearest neighbor" problem. Rather it is a problem of "is there a neighbor within some distance."

My example just shows a single dimension. I've skipped the Y/Z dimensions for clarity.

My attempt so far :

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

On rare occasions, and I mean- really rare- the maps don't find a matching entry when positions overlap.

Is there something I can do better to implement this, still using STL containers?

Answer 1

Now this problem isn't quite the "nearest neighbor" problem. Rather it is a problem of "is there a neighbor within some distance."

The latter is phrased pretty simply in terms of the former, though. Find the nearest neighbor, then determine if it's close enough. This seems like a reasonable route to go considering the number of data structures available to you for the task.

Namely, a kd-tree is extremely common and not too hard to implement. Also relevant is an R-tree, though I haven't implemented that and cannot comment on its difficulty.