find_pth_nearest or find_kth_nearest or whatever!

[Paul Harris]

here is a brainstorm i did a while ago on the find_pth_nearest ...

this may not work at all, but it may give some food for thought until i get
the visitor patterns going...


if you were to do it with the find_nearest_if() in libkdtree, I think all
you need to do is force kdtree to look for the second nearest point... that
is, ignore all the points that are less than the nearest (so far) and accept
all the other points.

So I think if you did (for the find 2nd nearest case)...


struct compare_2nd
{
struct State
{
State( Point const& t ) :
  target(t), initialised(false)
{}
Point target, p_best, p_second_best;
bool initialised;
double best, second_best;
};

State * state;
compare_2nd(State * s) : state(s) {}

bool operator()( Point const& n ) const
{
double dist = distance_between(n,state->target);

/* first look at a point... */
if ( ! state->initialised)
{
  state->best = state->second_best = dist;
  state->p_best = state->p_second_best = n;
  state->initialised = true;
  return true;
}

if (dist < state->best) /* better than our best? */
{
  /* shuffle best to second best */
  state->second_best = state->best;
  state->p_second_best = state->p_best;
  /* we have a new king */
  state->best = dist;
  state->p_best = n;
  /* pretend we weren't interested so it won't reduce the search space to
this point
     this is the key to making kdtree keep looking for 2nd best */
  return false;
}

if (dist < state->second_best)  /* better than our second-best? */
{
  state->second_best = dist;
  state->p_second_best = n;
}

/* allow 2nd best points and worse to be used for refining the region in
libkdtree */
return true;
}

};


i THINK that would work.   there are unit tests in kdtree, adapt those to
check that this will double-check the correct 2nd best point and test that
way.


to run, you would do...

typedef kdtree<etc> Tree;
Tree tree(points.begin(),points.end());  // fill the tree

compare_2nd::State state(target_point); // create the state

/* run the find with the functor and its state. */
tree.find_nearest_if( target_point, max_range, compare_2nd(&state));

your_result = state.p_second_best;
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20081111/da271855/attachment.htm