find_kth_nearest

[Paul Harris]

Hi,

I'm travelling so I hope my holiday message is not bothering everyone
at the mailing list.

IIRC, for each decent into the tree, it checks whether the branch's
region will get nearer to the target or not, compared with the current
best.

To adapt this, you would need to have find_nearest (now find_pth) keep
a list of the last P nearest nodes, and compare against the P'th node,
not the nearest.

If this change were to be made, let me suggest we make it more
flexible...  This isn't properly thought out, but hopefully it will
fire a spark in someone's brain?

So instead, you could have a function find_nearest_somename(), which
accepts a functor which has a signature like...

void push(value_type const& x);
bool compare_lt(dimension x) const;
and some function to extract the result, eg
void iterate_results(Iterator it) const;

so to make find_nearest_pth(), the functor would keep a list of the
last P nodes, and compare against the Pth one.
At the same time, a functor could be made to implement find_nearest()
and find_within_range().  So with kdtree could come at least 3
ready-made functors, and the handy find_nearest() etc functions would
simply call find_generic(appropriate_functor());

know what I mean?

see ya
Paul


On 18/10/2007, Renaud Detry <renaudjdetry at airpost.net> wrote:
> Hi all,
>
> I'd like to have you opinion on the implementation effort and
> performance of a `find_pth_nearest' method (pth-nearest, k being the
> number of dimensions of the tree..). Would it be hard to adapt
> _M_find_nearest to offer this functionality? Does it simply amount to
> keeping a p-node history in each recursion?
>
> Thanks,
> Renaud.
>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>