Using a "rough" STL map
I would like to create an STL map to see if it is close enough to another element in 3D space. So far, my "less-functor" has worked quite well, pasted in at the following link.
Now this problem is not really a "nearest neighbor" problem. Rather, it is the problem "is there a neighbor at some distance".
In my example, only one dimension is shown. I have cleared the Y / Z dimensions for clarity.
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 - very rarely - maps don't find a suitable entry when positions overlap.
Is there something I can do better to implement this while still using STL containers?
source to share
Now this problem is not really a "nearest neighbor" problem. Rather, it is the problem "is there a neighbor at some distance".
The latter is formulated quite simply from the point of view of the former. Find your nearest neighbor, then determine if it's close enough. This seems like a sane way to consider the amount of data available to you for a task.
Namely, kd-tree is extremely common and not too difficult to implement. Also relevant is the R-tree , although I have not implemented this and cannot comment on its difficulty.
source to share