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