Hi Walter,<br><br>Sorry I have been busy, I have tried out your test and yes you are right, it returns a point that is further than 10.0<br><br>The reason for this is because kdtree takes your value of 10 and makes a box out of it, centred on sv (the search value) with a sides of length 20 (10 "radius" from the centre).<br>
<br>It then finds all the points within the box. This means that the results are not exactly within a range of 10, but it does mean its faster as it doesn't perform that extra distance check.<br><br>Its always been like that. Maybe it needs to be changed, either to improve the documentation so people don't think it'll give them perfect results, or maybe it should be changed to add an extra check.<br>
<br>What do you think?<br><br>cheers,<br>Paul<br><br><br><div class="gmail_quote">2009/1/15 Walter Keiner <span dir="ltr"><<a href="mailto:walter.keiner@googlemail.com">walter.keiner@googlemail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello,<br><br>I used libkdtree (ver 0.7.0) with floating point values and the function find_within_range() to get all values within a specified range. Unfortunately, the accuracy of the results have been poor. I used two set of points. The first one:<br>
<br>x=18.892500 y=20.341400 z=-1.188940<br>x=18.446899 y=18.649700 z=-2.155560<br>x=18.228800 y=16.921600 z=-2.665970<br><br>And the second one:<br><br>x=28.771200 y=16.921600 z=-2.665970<br>x=28.553101 y=18.649700 z=-2.155560<br>
x=28.107500 y=20.341400 z=-1.188940<br><br>If you insert the second set into the kdtree and check all points of the first one with find_within_range(sv, 10.0f, std::back_inserter(vectors)); you get the following result:<br>
<br>info: distance = 10.557716 with :
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">info: x=18.892500 y=20.341400 z=-1.188940</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=28.771200 y=16.921600 z=-2.665970</p><p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);"><br></p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: distance = 9.855121 with :</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=18.892500 y=20.341400 z=-1.188940</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=28.553101 y=18.649700 z=-2.155560</p><p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);"><br></p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: distance = 9.215000 with :</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=18.892500 y=20.341400 z=-1.188940</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=28.107500 y=20.341400 z=-1.188940</p><p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);"><br></p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: distance = 9.855121 with :</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=18.446899 y=18.649700 z=-2.155560</p>
<p style="margin: 0px; text-indent: 0px; color: rgb(0, 0, 0);">Info: x=28.107500 y=20.341400 z=-1.188940</p><br>The distance is calculated by the norm of the difference vector between the two provided. As you can see the there is a value with a distance >10, also find_within_range was provided with 10.0f.<br>
<br>The Tree was defined:<br><br>struct sVECTOR<br>{<br> float v[3];<br> //some other values<br> };<br> <br> typedef KDTree::KDTree<3, sVECTOR, std::pointer_to_binary_function<sVECTOR, size_t, float> > tTreeType;<br>
<br>The tree was allocated with:<br><br>tree = new tTreeType(std::ptr_fun(tac));<br><br>where tac is:<br><br>inline float KDTreeHandler::tac( KDTreeHandler::sVECTOR t, size_t k )<br>{<br> return t.v[k];<br>}<br><br>The variable vectors provided for find_within_range is a std::deque<sVECTOR>.<br>
<br>Can anyone give me some advices or recommendations?<br><br>Grettings,<br><font color="#888888">Walter<br><br>
</font><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>