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?

So this is the nearest neighbor problem with a search radius, right? Your might want to have a look at the FLANN library, it implements radius search. I guess other libraries as well. — Tim, Mar 26 '12 at 15:28
Your functor **must** define a [strict weak ordering](http://en.wikipedia.org/wiki/Strict_weak_ordering). Yours doesn't. — Oliver Charlesworth, Mar 26 '12 at 15:34
Actually, on a second look, I think it **does** define a SWO, but I don't think the multi-dimensional version will. Why not post it? — Oliver Charlesworth, Mar 26 '12 at 15:41
@OliCharlesworth His function doesn't define a SWO, since if `b - a < fudge` and `c - b < fudge`, his function may return true for `a, c`, but false for `a, b` and `b, c`. — James Kanze, Mar 26 '12 at 15:53
So is there another approach I could take, like to use an unordered map? Could I "hash" a value, even if checks for entries are approximate? — macetw, Mar 26 '12 at 16:00
@JamesKanze: I think that's ok, though. The requirement is that `(a < b) && (b < c) => (a < c)`, but not vice versa. — Oliver Charlesworth, Mar 26 '12 at 16:05
@OliCharlesworth There _is_ a requirement that it work both ways. That `!(a < b) || !(b < c)) => !(a < c)`. (Think about it for a moment, and I think you'll agree.) — James Kanze, Mar 26 '12 at 16:18
@JamesKanze: I agree that it makes sense intuitively, but I wasn't sure it necessarily followed from the requirements. But I did think about it, and I now agree! — Oliver Charlesworth, Mar 26 '12 at 16:40
@OliCharlesworth Yes. I've addressed this in the past by defining a comparison function which broke the domain up into finite areas of `mFudgeFactor` (by rounding both elements down to the nearest multiple of `mFudgeFactor`), which results in a legal operator, but I don't think it will help in his case. — James Kanze, Mar 26 '12 at 16:44
I believe the property @OliCharlesworth et al is discussing is the transitive property of Strict Weak Ordering. However, STL maps also require the comparison to be asymetric, where if a != b and a < b, it is not the case that b < a. In fact, I kind of expected to define an equality functor for the map, but I did not. The equality condition is with the unordered_map, which I am not using for this solution. Do I have my understanding correct? — macetw, Mar 26 '12 at 21:26

score 1 · Accepted Answer · answered Mar 26 '12 at 17:41

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.

answered Mar 26 '12 at 17:41

GManNickG

494,350
52
494
543

1

Using a grid of regions will go a long way _IF_ your points are somewhat evenly distributed. – Mooing Duck Mar 26 '12 at 17:44
@MooingDuck: Hm? Neither of those use grids. – GManNickG Mar 26 '12 at 17:46
No, I was just thinking of yet another option. kd-trees are definitely win if points are clumped, but grids might be better for some data. You have a good answer, I was mostly musing. – Mooing Duck Mar 26 '12 at 17:47
@MooingDuck: Oh, gotcha. A kd-tree will generate a grid if the points are uniformly distributed. :) (Though you're right, hard-coding for a grid, like an oct-tree, could save space. But the generality of a kd-tree wins to me.) – GManNickG Mar 26 '12 at 17:50
This is not an even distribution problem. – macetw Mar 26 '12 at 17:52
@macetw: That's fine, neither data structure requires it. – GManNickG Mar 26 '12 at 17:56
Kudo's to @MooingDuck. The grid of regions is our best approach, where we turn our "fudge factor" into a grid size of maps, no longer with map keys of "float" but keys of "int," where those integers are truncated by: 'int(grid/fudgefactor)'. It's not precise, but it is very close to what we already had. The KD tree approach (using "ANN" or "FLANN" would be the ideal). – macetw Mar 27 '12 at 17:31

Using an "approximate" STL map

1 Answers1