KDTree Implementation in Java

Question

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.

Any tips?

---

Incidentally, here are the results I've found so far:

• http://www.savarese.com/software/SavaAlgorithms/api/java/
• http://www.koders.com/java/fid7CE62747CE902D3117625B4954D85A9A6400DFDC.aspx

Both of them seem a little dodgy to me.

Answer 1

I sort of have an implementation you can look at.

I implemented a k-d tree in C++ a couple years ago. I eventually ported it to Java. The C++ worked fine, but it wasn't optimized -- it was a pretty simple implementation. My Java implementation likewise hasn't been tested extensively or optimized, but you're welcome to look at it for ideas.

It's availabe here: KDTree.java

Answer 2

Maybe Nearest Neighbor Search and KD-trees from the Stony-Brook algorithm repository can help.

Answer 3

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.

Answer 4

I've had success with Professor Levy's implementation found here. I realize you're looking for a more production-certified implementation so this is probably not a good fit.

However note to any passers-by, I've been using it for a while now in my photomosaic project with no issues. No guarantee but better than nothing :)