Hi Jason,<br><br><div class="gmail_quote">2009/11/18 Jason Remillard <span dir="ltr"><<a href="mailto:remillard.jason@gmail.com">remillard.jason@gmail.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;">
Hi,<br>
<br>
I am using 0.7.0 with visual studio 2005. I usually don't do a "use<br>
namespace std" until I am in my C++ files. This patch adds in the<br>
std:: namespace, and fixes a warning about the compiler not knowing if<br>
it should call the float, double, or long of sqrt. I included it<br>
because I hope that it is not related to the problem I am having with<br>
find_within_range.<br>
<br></blockquote><div><br>Thank you for that, I had forgotten that if you #include <cmath> it puts all the math functions (like sqrt) into the std namespace. I'll make the changes on the git HEAD.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The included test program makes a set or random 3D points, sets up the<br>
kdtree on them, then picks a random search point with a random range.<br>
It then calculates the points that should be returned by<br>
find_within_range, nd compares them to what actually comes back. I am<br>
seeing both extra points and missing points. Bug, or I am doing<br>
something wrong?<br>
<br></blockquote><div><br>I'm afraid that you are technically doing something wrong.<br>Only find_nearest bothers to sqrt() the distances. find_within_range converts the 'limit' into a square region (or bounding box) with sides=limit and then searches and returns all points within that box.<br>
<br>This is how it has always been - all of the _within_range() functions work this way. I don't think this is ideal, and it should certainly be more obvious. I myself had forgotten that it does this.<br><br>I can't really change the way it works as people possibly rely on this behaviour. Personally I'd prefer it sqrt'd to find the distance, but the change is not as simple as just wacking in a sqrt somewhere. Plus people don't always want to use euclidean distances so its not really a step in the right direction.<br>
<br>I've added your test (with corrections and comments) to git-head, and also added extra comments to kdtree.hpp, so people won't be caught out as easily when 0.7.2 comes out.<br><br><br><br>There are a few things you could do:<br>
<br>a) adjust what you expect from kdtree. see below, i've adjusted your test so that it runs without failing.<br><br>b) use visit_within_range() to test the distance properly before adding it to the vector, or double-check the distances in the result vector.<br>
<br>c) try out my git branch paulharris/region ... i've templated the Region that you can search on, and so you could implement a Region of your own that does the sqrt() test in the encloses() method. this could eventually be incorporated into the standard kdtree so that we can then call eg tree.find_within_range_accurate() or whatever.<br>
<br><br>cheers,<br>Paul<br><br><br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Thanks, Jason.<br>
<br>
#include <kdtree++/kdtree.hpp><br>
#include <vector><br>
#include <map><br></blockquote><div>#include <set> <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
#include <stdio.h><br>
<br>
using namespace std;<br>
<br>
struct kdtreeNode<br>
{<br>
typedef double value_type;<br>
<br>
double xyz[3];<br>
size_t index;<br>
<br>
value_type operator[](size_t n) const<br>
{<br>
return xyz[n];<br>
}<br>
<br>
double distance( const kdtreeNode &node)<br>
{<br>
double x = xyz[0] - node.xyz[0];<br>
double y = xyz[1] - node.xyz[1];<br>
double z = xyz[2] - node.xyz[2];<br>
</blockquote><div> </div>// this is not correct return sqrt( x*x+y*y+z*z);<br><div><br>// this is what kdtree checks with find_within_range()<br>// the "manhattan distance" from the search point.<br>// effectively, distance is the maximum distance in any one dimension.<br>
return max(fabs(x),max(fabs(y),fabs(z)));<br><br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
}<br>
};<br>
<br>
int main(int argc,char *argv[])<br>
{<br>
vector<kdtreeNode> pts;<br>
<br>
typedef KDTree::KDTree<3,kdtreeNode> treeType;<br>
<br>
treeType tree;<br>
<br>
// make random 3d points<br>
for ( size_t n = 0; n < 10000; ++n)<br>
{<br>
kdtreeNode node;<br>
node.xyz[0] = double(rand())/RAND_MAX;<br>
node.xyz[1] = double(rand())/RAND_MAX;<br>
node.xyz[2] = double(rand())/RAND_MAX;<br>
node.index = n;<br>
<br>
tree.insert( node);<br>
pts.push_back( node);<br>
}<br>
<br>
for (size_t r = 0; r < 1000; ++r)<br>
{<br>
kdtreeNode refNode;<br>
refNode.xyz[0] = double(rand())/RAND_MAX;<br>
refNode.xyz[1] = double(rand())/RAND_MAX;<br>
refNode.xyz[2] = double(rand())/RAND_MAX;<br>
<br>
double limit = double(rand())/RAND_MAX;<br>
<br>
// find the correct return list by checking every single point<br>
set<size_t> correctCloseList;<br>
<br>
for ( size_t i= 0; i < pts.size(); ++i)<br>
{<br>
double dist = refNode.distance( pts[i]);<br>
if ( dist < limit)<br>
correctCloseList.insert( i );<br>
}<br>
<br>
// now do the same with the kdtree.<br>
vector<kdtreeNode> howClose;<br>
tree.find_within_range(refNode,limit,back_insert_iterator<vector<kdtreeNode><br>
>(howClose));<br>
<br>
// make sure no extra points are returned, and the return has no<br>
missing points.<br>
for ( size_t i = 0; i < howClose.size(); ++i)<br>
{<br>
set<size_t>::iterator hit = correctCloseList.find( howClose[i].index);<br>
<br>
if ( hit != correctCloseList.end())<br>
{<br>
correctCloseList.erase(hit);<br>
}<br>
else<br>
{<br>
// point that is too far away - fail!<br>
assert(false);<br>
printf("fail, extra points.\n");<br>
}<br>
}<br>
<br>
// fail, not all of the close enough points returned.<br>
assert( correctCloseList.size() == 0);<br>
if ( correctCloseList.size() > 0)<br>
{<br>
printf("fail, missing points.\n");<br>
}<br>
}<br>
}<br>
<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>