problem with find_within_range

[Jason Remillard]

Hi,

I am using 0.7.0 with visual studio 2005. I usually don't do a "use
namespace std" until I am in my C++ files. This patch adds in the
std:: namespace, and fixes a warning about the compiler not knowing if
it should call the float, double, or long of sqrt. I included it
because I hope that it is not related to the problem I am having with
find_within_range.

The included test program makes a set or random 3D points, sets up the
kdtree on them, then picks a random search point with a random range.
It then calculates the points that should be returned by
find_within_range, and compares them to what actually comes back. I am
seeing both extra points and missing points.  Bug, or I am doing
something wrong?

Thanks, Jason.

#include <kdtree++/kdtree.hpp>
#include <vector>
#include <map>
#include <stdio.h>

using namespace std;

struct kdtreeNode
{
  typedef double value_type;

  double xyz[3];
  size_t index;

  value_type operator[](size_t n) const
  {
    return xyz[n];
  }

  double distance( const kdtreeNode &node)
  {
    double x = xyz[0] - node.xyz[0];
    double y = xyz[1] - node.xyz[1];
    double z = xyz[2] - node.xyz[2];

    return sqrt( x*x+y*y+z*z);
  }
};

int main(int argc,char *argv[])
{
  vector<kdtreeNode> pts;

  typedef KDTree::KDTree<3,kdtreeNode> treeType;

  treeType tree;

  // make random 3d points
  for ( size_t n = 0; n < 10000; ++n)
  {
    kdtreeNode node;
    node.xyz[0] = double(rand())/RAND_MAX;
    node.xyz[1] = double(rand())/RAND_MAX;
    node.xyz[2] = double(rand())/RAND_MAX;
    node.index = n;

    tree.insert( node);
    pts.push_back( node);
  }

  for (size_t r = 0; r < 1000; ++r)
  {
    kdtreeNode refNode;
    refNode.xyz[0] = double(rand())/RAND_MAX;
    refNode.xyz[1] = double(rand())/RAND_MAX;
    refNode.xyz[2] = double(rand())/RAND_MAX;

    double limit = double(rand())/RAND_MAX;

    // find the correct return list by checking every single point
    set<size_t> correctCloseList;

    for ( size_t i= 0; i < pts.size(); ++i)
    {
      double dist = refNode.distance( pts[i]);
      if ( dist < limit)
        correctCloseList.insert( i );
    }

    // now do the same with the kdtree.
    vector<kdtreeNode> howClose;
    tree.find_within_range(refNode,limit,back_insert_iterator<vector<kdtreeNode>
>(howClose));

    // make sure no extra points are returned, and the return has no
missing points.
    for ( size_t i = 0; i < howClose.size(); ++i)
    {
      set<size_t>::iterator hit = correctCloseList.find( howClose[i].index);

      if ( hit != correctCloseList.end())
      {
        correctCloseList.erase(hit);
      }
      else
      {
        // point that is too far away - fail!
        assert(false);
        printf("fail, extra points.\n");
      }
    }

    // fail, not all of the close enough points returned.
    assert( correctCloseList.size() == 0);
    if ( correctCloseList.size() > 0)
    {
      printf("fail, missing points.\n");
    }
  }
}
-------------- next part --------------
Index: kdtree++/kdtree.hpp
===================================================================
--- kdtree++/kdtree.hpp	(revision 792)
+++ kdtree++/kdtree.hpp	(working copy)
@@ -512,7 +512,7 @@
 	      std::pair<size_type, typename _Acc::result_type> >
 	      best = _S_node_nearest (__K, 0, __val,
 				      _M_get_root(), &_M_header, _M_get_root(),
-				      sqrt(_S_accumulate_node_distance
+              std::sqrt(_S_accumulate_node_distance
 				      (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val)),
 				      _M_cmp, _M_acc, _M_dist,
 				      always_true<value_type>());
@@ -531,8 +531,8 @@
         bool root_is_candidate = false;
 	    const _Node<_Val>* node = _M_get_root();
        { // scope to ensure we don't use 'root_dist' anywhere else
-	    distance_type root_dist = sqrt(_S_accumulate_node_distance
-	      (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
+         distance_type root_dist = std::sqrt(double(_S_accumulate_node_distance
+	      (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val)));
 	    if (root_dist <= __max)
 	      {
             root_is_candidate = true;
@@ -564,8 +564,8 @@
 	    if (__p(_M_get_root()->_M_value))
 	      {
             { // scope to ensure we don't use root_dist anywhere else
-	    distance_type root_dist = sqrt(_S_accumulate_node_distance
-		  (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
+              distance_type root_dist = std::sqrt(double(_S_accumulate_node_distance
+		  (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val)));
 		if (root_dist <= __max)
 		  {
            root_is_candidate = true;
Index: kdtree++/node.hpp
===================================================================
--- kdtree++/node.hpp	(revision 792)
+++ kdtree++/node.hpp	(working copy)
@@ -213,7 +213,7 @@
 	    typename _Dist::distance_type d = 0;
 	    for (size_t i=0; i != __k; ++i)
 	      d += _S_node_distance(i, __dist, __acc, __val, static_cast<const _Node<_Val>* >(cur)->_M_value);
-       d = sqrt(d);
+      d = std::sqrt(double(d));
 	    if (d <= __max)
           // ("bad candidate notes")
           // Changed: removed this test: || ( d == __max && cur < __best ))
@@ -245,7 +245,7 @@
       near_node = probe->_M_left;
     if (near_node
 	// only visit node's children if node's plane intersect hypersphere
-	&& (sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max))
+  && (std::sqrt(double(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value))) <= __max))
       {
 	probe = near_node;
 	++probe_dim;
@@ -271,7 +271,7 @@
 		    typename _Dist::distance_type d = 0;
 		    for (size_t i=0; i < __k; ++i)
 		      d += _S_node_distance(i, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value);
-          d = sqrt(d);
+        d = std::sqrt(double(d));
           if (d <= __max)  // CHANGED, see the above notes ("bad candidate notes")
 		      {
 			__best = static_cast<const _Node<_Val>* >(probe);
@@ -287,7 +287,7 @@
 		  }
 		else if (far_node &&
 			 // only visit node's children if node's plane intersect hypersphere
-			 sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max)
+       std::sqrt(double(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value))) <= __max)
 		  {
 		    probe = far_node;
 		    ++probe_dim;
@@ -302,7 +302,7 @@
 	      {
 		if (pprobe == near_node && far_node
 		    // only visit node's children if node's plane intersect hypersphere
-		    && sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max)
+        && std::sqrt(double(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value))) <= __max)
 		  {
 		    pprobe = probe;
 		    probe = far_node;
@@ -330,7 +330,7 @@
 	      near_node = cur->_M_left;
 	    if (near_node
 		// only visit node's children if node's plane intersect hypersphere
-		&& (sqrt(_S_node_distance(cur_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(cur)->_M_value)) <= __max))
+    && (std::sqrt(double(_S_node_distance(cur_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(cur)->_M_value))) <= __max))
 	      {
 		probe = near_node;
 		++probe_dim;