Accuracy of libkdtree

[Paul Harris]

Hi Walter,

Sorry I have been busy, I have tried out your test and yes you are right, it
returns a point that is further than 10.0

The reason for this is because kdtree takes your value of 10 and makes a box
out of it, centred on sv (the search value) with a sides of length 20 (10
"radius" from the centre).

It then finds all the points within the box.  This means that the results
are not exactly within a range of 10, but it does mean its faster as it
doesn't perform that extra distance check.

Its always been like that.  Maybe it needs to be changed, either to improve
the documentation so people don't think it'll give them perfect results, or
maybe it should be changed to add an extra check.

What do you think?

cheers,
Paul


2009/1/15 Walter Keiner <walter.keiner at googlemail.com>

> 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
>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20090123/50d39380/attachment.htm