So now you can be lazy too by not having to search around further for the "Hello World" usage of libkdtree++. After installing libkdtree++ on your system, here are the basics. I'm going to create a typedef a 3 dimensional kd-tree, because I need it to hold Vector3 objects. The typedef just makes it coding easier.

#include <kdtree++/kdtree.hpp>

#define DIMS 3 // dimensions of the kdtree.

// This typedef is just for ease

typedef KDTree::KDTree< DIMS, Vector3, std::pointer_to_binary_function<vector3,size_t,float> > tree_type;

DIMS means the number of dimensions in the tree, which is also the number of dimensions each node has. Vector3 is the data type the tree is holding. This is my own custom datatype (but it's just a 3d vector). The last parameter defines the function signature that can be used when sorting and searching. Tip: google "pointer_to_binary_function" if you don't know what it is.

Then you need a function that will return a node's kth dimension. In this example, I need a function to return a Vector3's X, Y, or Z component.

// Get nodes kth dimension value

inline float getDimension(Vector3 v, size_t k)

{

// k is either 0,1,2

if (k == 0) // x axis

return v.x;

else if (k == 1) // y axis

return v.y;

else // z axis

return v.z;

}

Now I'm finally going to declare my tree.

int main()

{

tree_type t(std::ptr_fun(getDimension));

t.insert(Vector3(0,3,0));

t.insert(Vector3(1,0,1));

t.insert(Vector3(2,0,3));

t.insert(Vector3(3,1,1));

t.insert(Vector3(1,2,4));

Vector3 target(1.5,2,0);

// Find the node nearest to the target

std::pair<tree_type::const_iterator, float> = t.find_nearest(target);

cout << "nearest is: " << *found.first << endl;

cout << " dist is: " << found.second << endl;

}

This code will find the nearest node to the target. The look-ups here are amazingly fast. I create a tree with 10 million random points. While the tree creation took more than two minutes (125s) , the lookup was near instantaneous, less than clock_t's resolution anyway (which I understand to be around 15 ms.)

That's it for now. I'm still playing with it.