Fix for find_nearest() with maximum distance in argument

[Sylvain Bougerel]

Paul Harris wrote:
> On 10/12/2007, Sylvain Bougerel <sylvain.bougerel.devel at gmail.com> wrote:
>   
>> Paul Harris wrote:
>>     
>>> Hi Sylvain,
>>>
>>> On 08/12/2007, Sylvain Bougerel <sylvain.bougerel.devel at gmail.com> wrote:
>>>
>>>       
>>>> 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).
>>>>
>>>>         
>>> So it wasn't checking all the potential branches?
>>>
>>>       
>> Yes, particularly the entire left side from the root node (if the target
>> value is on the right side), or the entire right side of the root node
>> (if the target value is on the left side). Only happen when the given
>> distance is bigger than the distance from the root to the node.
>>     
>
>
> sorry mate, i think its still not quite right.
>
> see attached.  the kdtree sources are from the latest git sources.
> i've add a perf_find_items() to perf_kdtree.cpp which simply looks for
> the items that are in the tree, BUT it looks by specifying the max as
> zero.
>
> this is the same technique you mentioned you wanted to try for find_exact().
>
> anyway, if you set the max to zero, it won't find the item.  if you
> set it to 1, then it will.
>
> if you change triplet's value_type to double, and set the max to 0.1
> or 0.001 it'll find the item.   set the max to zero and it will not
> find it.
>
> this is a bug, right?
>   
Yes, this should be a bug. We are looking for every node whose distance 
from "val" is at most "max", right? Which would mean a "less or equal 
to" relationship. I can already imagine why it happens in the code. I'll 
fix this tonight.

- Sylvain