Accuracy of libkdtree

[Walter Keiner]

Hello,

I used libkdtree (ver 0.7.0) with floating point values and the function
find_within_range() to get all values within a specified range.
Unfortunately, the accuracy of the results have been poor. I used two set of
points. The first one:

x=18.892500 y=20.341400 z=-1.188940
x=18.446899 y=18.649700 z=-2.155560
x=18.228800 y=16.921600 z=-2.665970

And the second one:

x=28.771200 y=16.921600 z=-2.665970
x=28.553101 y=18.649700 z=-2.155560
x=28.107500 y=20.341400 z=-1.188940

If you insert the second set into the kdtree and check all points of the
first one with find_within_range(sv, 10.0f, std::back_inserter(vectors));
you get the following result:

info: distance = 10.557716 with :

info: x=18.892500 y=20.341400 z=-1.188940

Info: x=28.771200 y=16.921600 z=-2.665970


Info: distance = 9.855121 with :

Info: x=18.892500 y=20.341400 z=-1.188940

Info: x=28.553101 y=18.649700 z=-2.155560


Info: distance = 9.215000 with :

Info: x=18.892500 y=20.341400 z=-1.188940

Info: x=28.107500 y=20.341400 z=-1.188940


Info: distance = 9.855121 with :

Info: x=18.446899 y=18.649700 z=-2.155560

Info: x=28.107500 y=20.341400 z=-1.188940

The distance is calculated by the norm of the difference vector between the
two provided. As you can see the there is a value with a distance >10, also
find_within_range was provided with 10.0f.

The Tree was defined:

struct sVECTOR
{
        float v[3];
        //some other values
 };

 typedef KDTree::KDTree<3, sVECTOR, std::pointer_to_binary_function<sVECTOR,
size_t, float> > tTreeType;

The tree was allocated with:

tree = new tTreeType(std::ptr_fun(tac));

where tac is:

inline float KDTreeHandler::tac( KDTreeHandler::sVECTOR t, size_t k )
{
    return t.v[k];
}

The variable vectors provided for find_within_range is a
std::deque<sVECTOR>.

Can anyone give me some advices or recommendations?

Grettings,
Walter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20090115/dca69672/attachment.htm