Sign in to follow this  
mlt

kd-tree implementation?

Recommended Posts

I need a kd-tree implementation that returns the k nearest neighbors to a point as objects. Something like this: std::vector<MyObj> neighbors; // Add some objects to myObjects with location vectors and other identifiers. int radius = 40; // radius in pixels. VectorType point(3,5) // The point. KDtree tree; tree.search(point, radius, neighbors); When search returns it should contain all neighbors to point within the specified radius. I have googled various kd-tree implementations but they all just return the distance to the point as vectors. In my case I need to use additional information for each of the neighbors, such as ID and other values. Do I need to invent the wheel here or does anyone know of an implementation that has this more object oriented approach?

Share this post


Link to post
Share on other sites
Hmm, it looks like libkdtree++ does half of what you want. It's modeled after the STL's containers - templated so you can insert any kind of data, and the library accesses the relevant k-dimensional value for the object by using a function object (that returns a value given a dimension) that you give as a template parameter. However, it doesn't seem to have a k-nearest neighbour search built in, but the mailing list seems to suggest you can hack one in by abusing the predicate passed in to the find methods.

There's a simple-looking C library, kdtree as well. BSD licensed, allows you to associate arbitrary data to points via void *s, and has a k-nearest neighbour function.

Note that I haven't personally used either of these libraries - I rolled my own kd-tree implementation for a raytracer I wrote.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this