Hi Damon,<br><br>It could do the nearest 50 and return the nearest, but you would implement that in the form of a custom visitor.<br><br>I'll forward you emails from the mailing list where something like this had been discussed before.<br>
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.<br><br>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).<br>
So if the visitor always returned false, it would eventually visit all the nodes in the kdtree.<br>If the visitor always returned true, it would only visit the very top few nodes of the tree.<br>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.<br>
<br>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.<br>
<br>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). <br>
called "New function: find_k_nearest()" and "find_pth_nearest or find_kth_nearest or whatever"<br><br>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.<br>
<br>see ya<br>Paul<br><br><br><div class="gmail_quote">On 19 April 2010 23:24, Damon Blanchette <span dir="ltr"><<a href="mailto:damonbla@gmail.com">damonbla@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>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!<br>
</div><div><br></div><div>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.</div>
<div><br></div><div>Is this possible with libkdtree++? I looked through the source code, and it's kind of hard to tell.</div><div>Thank you,</div><div>Damon</div>
<br>_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
<a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
<br></blockquote></div><br>