[Insight-users] Kd-tree implementation in ITK is buggy and unreliable

[Ali -]

Ah, forgot the attachment!

---------------------------

Kevin,

As you know, testing algorithms like nearest neighbour search on some specific datasets do not provide the sufficient condition for the health of the code. At the moment, I cannot think of a more general solution than this trial-error approach.

The bug I mentioned seems to be different to the one reported. In the attached point-sets p1 and p2, if you try to find out the nearest neighbours of each point in p1 in p2 by the implementation of kd-tree in ITK, one of them is assigned to a wrong neighbour. By visualising the result it is easy to spot the problem.

Hope this helps.


-Ali

>
> Please describe when the problem occurs, or better yet give some example
> code that demonstrates the error.
>
> I notice that there is an open bug in the bugtracker about kd trees :
>       http://www.paraview.org/Bug/bug_view_advanced_page.php?bug_id=5082
>
> I notice that there is a test for the kdtrees :
>       Insight/Testing/Code/Numerics/Statistics/itkKdTreeGeneratorTest.cxx
>
> Are these anything like the problem you are seeing?

_________________________________________________________________
Bag extra points with the Walkers Brit Trip Game 
http://www.walkersbrittrips.co.uk/game
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: p1.txt
URL: <http://www.itk.org/pipermail/insight-users/attachments/20080422/2aa9eea3/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: p2.txt
URL: <http://www.itk.org/pipermail/insight-users/attachments/20080422/2aa9eea3/attachment-0001.txt>