crvs / kdtree Goto Github PK
View Code? Open in Web Editor NEWSimple C++ KD-Tree implementation
License: BSD 3-Clause "New" or "Revised" License
Simple C++ KD-Tree implementation
License: BSD 3-Clause "New" or "Revised" License
Hi, thank you so much for the cool work.
I wonder is there anyway to get the list of K nearest points?
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
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?
Using nth_element instead of sort while building might be more efficient.
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
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.
is there knn search method ??
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.