search for a specific number of nodes?

[Sylvain Bougerel]

Hi Damon,

My implementation is not ready yet so you better off with libkdtree at the
moment.

The point is neighboring iterators are definitely writteable. In fact the
function in libkdtree to find the nearest neighbor is a very good start for
such iterator.

The library currently does not permit to find the furthest. But finding the
furthest is basically the same process of finding nearest with some operator
reversed. With a bit of time you should be able to write it by copy-pasting
the find nearest and reverting some of its comparisions.

Regards,
Sylvain

On 20 Apr 2010 08:04, "Paul" <elegant_dice at yahoo.com> wrote:

Hi Damon,

It could do the nearest 50 and return the nearest, but you would implement
that in the form of a custom visitor.

I'll forward you emails from the mailing list where something like this had
been discussed before.
Basically, instead of searching for the nearest point via incrementally
reducing the search space, you only reduce the search space if its smaller
than the 50th currently found point.

The basic idea is that the visitor remembers the last 50 nearest events, and
returns true if the node it just visited should be culled due to the
distance (so nodes further away in the current search dimension won't be
visited in the future).
So if the visitor always returned false, it would eventually visit all the
nodes in the kdtree.
If the visitor always returned true, it would only visit the very top few
nodes of the tree.
And if the visitor always returned true where X > 10, it would visit all the
nodes where X <= 10, and a few (at least one) nodes where X > 10.

I'm not sure if it would be very efficient as the search space wouldn't be
reduced at all until you'd visited 50 points!  To improve the performance,
your visitor could tell kdtree to reduce the search space if it visits a
node that is further than X distance.

I'll forward you two emails from the mailing list that discussed and had
some code in regards to this issue (one is a patch, one is an example).
called "New function: find_k_nearest()" and "find_pth_nearest or
find_kth_nearest or whatever"

I'm not sure how other implementations might do it.  Sylvain was talking
about an iterator that could walk the tree starting from the nearest, but I
don't know if he ever finished that idea.

see ya
Paul


On 19 April 2010 23:24, Damon Blanchette <damonbla at gmail.com> wrote:

> >
> > Hi, my name is Damon Blanchette, and I found libkdtree++ through some
> google searches.  I'm a gr...
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>

_______________________________________________
libkdtree-devel mailing list
libkdtree-devel at lists.alioth.debian.org
http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20100421/cd1b658f/attachment.htm>