search for a specific number of nodes?

[Paul]

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 graduate student at WPI in Worcester, Massachusetts,
> working towards my master's degree in computer science.  I hope this is the
> right place to email!
>
> I'm currently taking an advanced graphics class, and I'm trying to
> implement photon mapping in a ray tracer.  Photon mapping works well when
> used with kd-trees, hence my looking around for a library that implements
> them.  What I need to be able to do is search the kd-tree for a specific
> number of nodes.  I can see that libkdtree++ does range searches, which is
> fine, but is there a way to give it a point in 3D space and a number of
> nodes to return, for example 50, and it just returns the closest 50 nodes to
> that point?  If it sent back the distance from the farthest node, that would
> also be fantastic.
>
> Is this possible with libkdtree++?  I looked through the source code, and
> it's kind of hard to tell.
> Thank you,
> Damon
>
> _______________________________________________
> 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/20100420/2d8edc52/attachment.htm>