crvs/kdtree

Simple C++ KD-Tree implementation

KDTree

Simple C++ static KD-Tree implementation with minimal functionality.

• points are given as STL vectors (and inserted in their own STL vector) so supports n-dimensional points for any n
• makes full trees, (i.e. does not cut-off the branching at some arbitrary level) giving the nearest neighbor query have (strong) logarithmic complexity.
• builds the tree in one go (does not support adding nodes, the tree is built from a list of points and cannot be altered afterwards)
• points are assumed to be STL vectors
• it provides the following queries:
  • nearest neighbor
  • neighbors within a given distance
  • k nearest neighbours

News

Version 2.0.0

• Added K nearest neighbours query.

License and copyright

© J. Frederico Carvalho Licensed under the BSD3 License

kdtree's Issues

efficiency for building: nth_element instead of sort

Using nth_element instead of sort while building might be more efficient.

knn search ?

is there knn search method ？？

Declared function dist not implemented

KDTree.hpp declares

inline double dist(const point_t &, const point_t &);
inline double dist(const KDNodePtr &, const KDNodePtr &);

but KDTree.cpp implements

inline double dist2(const point_t &, const point_t &);
inline double dist2(const KDNodePtr &, const KDNodePtr &);

istead.

Either declare dist2 in header file or implement dist implementation file.

how can i get k-nearest points

Hi, thank you so much for the cool work.
I wonder is there anyway to get the list of K nearest points?

will nth_element make some bug?

when build the tree, if the nth number(middle nuumber) have other same member, the seperation of the left/right sub tree will have some error, right?
because this will not fit the condition, which in one dim, left subtree is <= father node, and right subtree is > father node, when the condition occur, i think it will effect query operation.
thank you

Create License

I enjoyed this project. I wanted to use your code for commercial purposes but you have no license attached to it. I'm wondering if you would be able to attach a license with something reasonable?

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

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