test_kdtree.cpp

[AB]

Greetings.


This bug report concerns the file

                 .../libkdtree/examples./test_kdtree.cpp .


The "triplet" structurehas a constructor that accepts three integers.

The problem is that the "Walter"-related test at end of main() function
uses floating point values with the "triplet" constructor.
As is, the precision of these floating point values will be lost once 
the "triplet"
constructor implicitly converts these values to integers.

This can be fixed by implementing "triplet", etc. as templates.


  Here's my solution to this problem ....


// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// Re:  template declarations

/* Andros, Sun 24 Mar 2013 09:13:42 EST
     Created a template version since need floating point support.
     Need a CTOR that takes floating point args, as realised by g++-related
     warning ...
        "implicit conversion shortens 64-bit value into a 32-bit value";
      i.e. avoid implicit [double --> int] conversion, avoid loss of 
precision.
   */



template <typename VALUE_TYPE>
struct tripletT
{
   typedef VALUE_TYPE value_type;

   value_type d[3];

   tripletT(value_type a, value_type b, value_type c)
   {
     d[0] = a;
     d[1] = b;
     d[2] = c;
     bool reg_ok = (registered.find(this) == registered.end());
     assert(reg_ok);
     registered.insert(this).second;
   }

   tripletT(const tripletT & x)
   {
     d[0] = x.d[0];
     d[1] = x.d[1];
     d[2] = x.d[2];
     bool reg_ok = (registered.find(this) == registered.end());
     assert(reg_ok);
     registered.insert(this).second;
   }

   ~tripletT()
   {
     bool unreg_ok = (registered.find(this) != registered.end());
     assert(unreg_ok);
     registered.erase(this);
   }

   void write( ostream& os ) const
   {
     assert(registered.find(this) != registered.end());
     os << '(' << d[0] << ',' << d[1] << ',' << d[2] << ')';
   }

   double distance_to(tripletT const& x) const
   {
     double dist = 0;
     for (int i = 0; i != 3; ++i)
       dist += (d[i] - x.d[i]) * (d[i] - x.d[i]);
     return sqrt(dist);
   }

   inline value_type operator[](size_t const N) const
   {
     return d[N];
   }

   bool operator == (const tripletT& rhs) const
   {
     return d[0] == rhs.d[0] && d[1] == rhs.d[1] && d[2] == rhs.d[2];
   }


   bool operator != (const tripletT& rhs) const
   {
     return( ! operator==(rhs) );
   }
};  // struct tripletT<>


// same as triplet, except with the values reversed.

template <typename VALUE_TYPE>
struct alternate_tripletT
{
   typedef VALUE_TYPE value_type;
   typedef tripletT<VALUE_TYPE> triplet;

   alternate_tripletT(const triplet & x)
   {
     d[0] = x.d[2];
     d[1] = x.d[1];
     d[2] = x.d[0];
   }

   inline value_type operator[](size_t const N) const
   {
     return d[2 - N];
   }

   value_type d[3];
};  // struct alternate_tripletT<>


typedef tripletT<int> triplet;
typedef alternate_tripletT<int> alternate_triplet;


template <typename TRIPLET_TYPE>
inline double tacT( TRIPLET_TYPE t, size_t k )
{
   return t[k];
}


template <typename T>
ostream& operator << (ostream& os, const tripletT<T>& o)
{
   o.write( os );
   return( os );
}

// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// Re:  updated code in main() using the above templates; located at end 
of main()


   // Walter reported that the find_within_range() wasn't giving results 
that were within
   // the specified range... this is the test.
   {
     typedef tripletT<double> triplet_d;


     typedef NAMESPACE_SEARCH_SORT::KDTree <
     3,
     triplet_d,
     pointer_to_binary_function<triplet_d, size_t, double> >
     tree_type_d;


     tree_type_d tree(  ptr_fun(tacT<triplet_d>)  );
     tree.insert( triplet_d(28.771200, 16.921600, -2.665970) );
     tree.insert( triplet_d(28.553101, 18.649700, -2.155560) );
     tree.insert( triplet_d(28.107500, 20.341400, -1.188940) );
     tree.optimise();

     typedef deque<triplet_d> triplet_d_deque_t;

     triplet_d_deque_t vectors;
     triplet_d sv(18.892500, 20.341400, -1.188940);
     tree.find_within_range(sv, 10.0f, back_inserter(vectors));

     cout << endl <<
          "Test find_with_range( " << sv <<  ", 10.0f) found " << 
vectors.size() << " candidates." << endl;

     // double-check the ranges
     {
      triplet_d_deque_t::iterator last(vectors.end());
double dist;
      for (triplet_d_deque_t::iterator v(vectors.begin()); v != last; ++v)
      {
       dist = sv.distance_to(*v);
       cout << "  " << *v << " dist=" << dist << endl;

       if (dist > 10.0f)
         cout << endl <<
              "This point is too far!" << endl <<
              "But that is by design, its within a 'box' with a 'radius' 
of 10, " << endl <<
              "not a sphere with a radius of 10" << endl;
       // Not a valid test, it can be greater than 10 if the point is in 
the corners of the box.
       // assert(dist <= 10.0f);
      } // v
     }
   }

// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




Regards,

Andros.


**
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20130324/92516534/attachment-0001.html>