KDTree is not reliably returning nearest neighbor 100% of the time.

[sushil-bharati]

My colleague and I have been using your KDTree implementation. However, we've found that, contrary to the definition of KDTree, this implementation does not produce the nearest neighbor 100% of the time.

We're attaching some code we used to show this, the link is at the bottom of this Issue. Here are the results that we obtained when running the code:

Total number of iterations ran: 50

Accuracy (tested with 50 datasets per iter) = 96.84 %. Avg. Total Number Correct: 48 / 50

Accuracy (tested with 100 datasets per iter) = 97.24 %. Avg. Total Number Correct: 97 / 100

Accuracy (tested with 200 datasets per iter) = 95.93 %. Avg. Total Number Correct: 191 / 200

Accuracy (tested with 300 datasets per iter) = 98.2267 %. Avg. Total Number Correct: 294 / 300

Accuracy (tested with 400 datasets per iter) = 96.9 %. Avg. Total Number Correct: 387 / 400

Accuracy (tested with 500 datasets per iter) = 99.744 %. Avg. Total Number Correct: 498 / 500

Accuracy (tested with 600 datasets per iter) = 98.4433 %. Avg. Total Number Correct: 590 / 600

Accuracy (tested with 700 datasets per iter) = 97.6029 %. Avg. Total Number Correct: 683 / 700

Accuracy (tested with 800 datasets per iter) = 97.6375 %. Avg. Total Number Correct: 781 / 800

Accuracy (tested with 900 datasets per iter) = 98.92 %. Avg. Total Number Correct: 890 / 900

Accuracy (tested with 1000 datasets per iter) = 99.822 %. Avg. Total Number Correct: 998 / 1000

Accuracy (tested with 2000 datasets per iter) = 99.641 %. Avg. Total Number Correct: 1992 / 2000

KDTreeErrorTest.cpp.txt

[crvs]

Thanks for the bug report! I fixed the code and it now passes the test, so I'm closing the issue.