begeekmyfriend / kdtree

Absolute balanced kdtree for fast kNN search.

kdtree

This is a (nearly absolute) balanced kdtree for fast kNN search. It does not support dynamic insertion and removal. Actually we adopt quick sort to rebuild the whole tree after changes of nodes. We cache the added or the deleted nodes which will not be actually mapped into the tree until the rebuild method to be invoked. The good thing is we can always keep the tree balanced, and the bad thing is we have to wait some time for the finish of tree rebuild. Moreover, duplicated samples are allowed to be added.

The thought of the implementation is posted here.

kdtree's Issues

kdtree_knn_search only works once

Hi,

It seems that research in the kdtree is only possible once.

see the attached test file below who results to

3 nearest neighbors of sample(-1.00, -5.00):
(1.24, -2.86) Distance:3.097935
(-2.96, -0.50) Distance:4.908319
(-6.88, -5.40) Distance:5.893590
3 nearest neighbors of sample(-8.00, -7.00):
(1.24, -2.86) Distance:3.097935
(-2.96, -0.50) Distance:4.908319
(-6.88, -5.40) Distance:5.893590

Whatever the next values you add in the code for searching, the result is the same.

kdtree_test.c.zip

Regards