test_kdtree.cpp

Paul elegant_dice at yahoo.com
Tue Mar 26 14:35:58 UTC 2013


Gosh you are right, I missed the problem of ints.
Strange, I think I would've noticed the smaller numbers before...

My comments on the test are still valid, I think this kdtree uses manhattan
distance rather than euclidean distance when searching.

I adjusted the code in a similar way to what you have done, and pushed it
to my repo here:
https://github.com/paulharris/libkdtree

If someone could please check what I've done, then pull it into the main
tree, that would be great.

Note also that I don't use libkdtree anymore, I've switched to flann /
nanoflann,
but compile fixes aren't hard to do so I did this little patch.

thanks again Andros for the report, I made a note in the git commit log.

cheers,
Paul


On 24 March 2013 18:51, AB <androsb at optusnet.com.au> wrote:

>
> Greetings.
>
>
> This bug report concerns the file
>
>                 .../libkdtree/examples./test_kdtree.cpp  .
>
>
> The "triplet" structure has 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.
>
>
> **
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20130326/96a663bb/attachment-0001.html>


More information about the libkdtree-devel mailing list