Fix for find_nearest() with maximum distance in argument

Sylvain Bougerel sylvain.bougerel.devel at gmail.com
Sat Dec 8 04:01:14 UTC 2007


Hi,

In the last commit there is 2 things:
- A fix for find_nearest() when used with a maximum distance in
argument. In certain condition it does not work properly.
(if the max distance given is greater than the distance from the root
node to the target value, and the nearest children node is not the
node under which the best node can be found).

- The behavior for find_nearest() is very slightly modified. In the
case where there is many closest node a same distance, the algorithm
now always return the node with the smaller address in memory. This is
to preempt the iterative implementation of find_exact().

Finally, I wanted to send an apology because I forgot to mention that
find_nearest() was now returning the squared version of the distance.
So, at the moment, you will have to call sqrt() on the best distance
(i.e. iterator->second)  returned by find_nearest(). After a heated
discussion on that matter, Paul will implement a fix that restores the
previous behavior by default.

Second, I also removed the template on the search value of
find_nearest(). I wanted to stick to the standard (the STL
implementation for the trees), but I admit that it makes sense to have
a template on the searched value. I will therefore restore the
template in find_nearest() soon.

- Sylvain



More information about the libkdtree-devel mailing list