Menu
I'm looking for a KDTree implementation in Java.
I've done a google search and the results seem pretty haphazard. There are actually lots of results, but they're mostly just little one-off implementations, and I'd rather find something with a little more "production value". Something like apache collections or the excellent C5 collection library for .NET. Something where I can see the public bug tracker and check to see when the last SVN commit happened. Also, in an ideal world, I'd find a nice well-designed API for spatial data structures, and the KDTree would be just one class in that library.
For this project, I'll only be working in either 2 or 3 dimensions, and I'm mostly just interested in a good nearest-neighbors implementation.
437
Like Octrees, k-d trees partition space and enable efficient queries on points. The key difference is that each node in a k-d tree partitons space across one plane per level of depth, leading to a binary tree. Each level generates two half spaces that contain its child nodes, which are recursively subdivided.
In order to construct a balanced k-d Tree, each node should split the space such that there are an equal number of nodes in the left subspace as the right subspace. Therefore we need to pick the median among the nodes for the current dimension and make it the subroot.
In the book Algorithms in a Nutshell there is a kd tree implementation in java along with a few variations. All of the code is on oreilly.com and the book itself also walk you through the algorithm so you could build one yourself.
168
for future seekers. Java-ml library has a kd-tree implementation that work fine. http://java-ml.sourceforge.net/
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
